停止性問題は解決可能では？
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2008/12/26(金) 11:05:10チューリング機械のアルゴリズムは作成不可能だとする結論がすでに出ている。
しかしそれはチューリング機械に限っての話である。
我々か普段目にするパソコンなどの一般的な機械はチューリング機械などではなく
ノイマン型の機械である。
しかもその内部に保持できる状態は高々有限個である。よって、停止しないときは、
必ず開始から有限時間内に無限ループ状態に突入する。そして無限ループ中のあるときに現れた状態は
必ず有限時間内に再び現れる。それを検出すれば無限ループ＝停止しないと結論できる。
また、有限時間内に停止するなら、そのプログラムを順に追っていけば有限時間内に停止するか判定でき、
判定アルゴリズムもまた有限時間で停止する。
つまりこのようなアルゴリズムなら停止問題を解けるはずである。
空のリスト空間Ｌを作成＝＞①作成プログラムＡを1ステップ実行=>その状態と同一のものがＬにあるか判定し結果をＢとする|||
If(Bが真）｛
結果「停止しない」を返す。
｝else{
Ｌに現在の状態を追加し①に戻る。
}
この過程の途中、①の結果Ａが終了したとき結果「停止する」を返す｜｜｜｜
よって停止問題を解くアルゴリズムはコンピュータアーキテクチャ（しかも現在広く使われているものも）によって
は可能となることがある。
===========================＝＝＝＝＝＝＝＝
個の考えは今さっき思いついたものなのですが正しいですか？
大学でチューリングの機械でできないものはノイマン型でもできないと教わった（ようなきがするだけで間違いかもしれませんがが）
のですが。
プログラムというのは直前の状態と最初に与えられた処理手続きだけで次の状態が決定する
（オートマトンの拡張）のでたぶん間違ってはいないと思うのですが。
0002１３２人目の素数さん
2008/12/26(金) 11:10:34ふむ，有限性の仮定か．
その場合，保持するリスト空間 L の有限性はどう議論する？
0003１３２人目の素数さん
2008/12/26(金) 11:14:07も有限で良いのでは？
00062
2008/12/26(金) 11:30:56L が有限なら、それを超える状態を取りうる場合はどういうアルゴリズムを適用して L を簡約すればいいんだ？
もちろんそのアルゴリズムの説明には、どの段階でループ検出できる状態となるか予測が必要となるわけだが。
0007１３２人目の素数さん
2008/12/26(金) 11:35:17相対性理論は間違いだらけ、みたいなのもあるな。
作れないと数学的に証明されてるから絶対作れない。相手にする必要なし。
”はいはいわろすわろすで”終わるすれだよ！！
0008１３２人目の素数さん
2008/12/26(金) 11:41:53ないというのじゃ駄目ですか？
リストというのはポインタでつなげて自由に要素数を変えられるあのリスト構造を意識して使った言葉なのですが。
00092
2008/12/26(金) 11:41:54つまり、状態が有限なんだから「それに合わせた」ストレージ L を用意せよと言うことだな。
例えば、B の状態が N ビット利用するなら、全ての状態を保持しうる 2^N ビットを理論上用意すれば
ループ検出は可能かもしれない、と。
というか、スレのタイトルが紛らわしいと思うのだが。
「状態数有限ならば」が欲しい。
00101ですけど．
2008/12/26(金) 11:48:06そういうこと！！
7>>
まじめなんだが...
0011１３２人目の素数さん
2008/12/26(金) 11:54:26とりあえずsage進行で。
断定した言い方じゃなく、一応質問してるからいいんじゃないですか。
>>8
それは分かるよ。
ただ有限性の仮定の問題で、有限個の状態しか持ち得ないあらゆるプログラム、というのが一体どういうものか、というのが難しいんです。
N 個の状態を持つ場合に 2^N のストレージが必要になるから任意の N に対して成立するにはストレージ無限性が必要になる。
つまりは L の無限性が必要だと思うんだが。
00121ですけど．
2008/12/26(金) 11:59:16いや、仮定を強くしてＡの状態数をＮ’’以下であるとするとどうだろう。
>>1で書いたことからだいぶ外れるけど。
0013１３２人目の素数さん
2008/12/26(金) 11:59:57N 個の状態を持つ場合に 2^N のストレージが必要になる
↓
N 個の状態を持つ場合に N のストレージが必要になる
00141ですけど．
2008/12/26(金) 12:01:04↓
Ａが有限個の状態を取るという仮定
煮変更。
0015１３２人目の素数さん
2008/12/26(金) 12:05:08そう思うよね？
でも、問題の定義として停止性判定アルゴリズムができるか、という問題なんだから
そのアルゴリズムには
1.ストレージがあってそれを利用するアルゴリズムがあって
2.任意の有限個の状態しか取り得ないプログラムの停止性が判定できる。
という順番になるので、この場合のストレージが有限では困るんだが。
00161ですけど．
2008/12/26(金) 12:15:07というのは>>1ではＡにあたるプログラムのこと？
Ａが何通りの状態を取りうるのかの最大値が分かってても駄目？
0017１３２人目の素数さん
2008/12/26(金) 12:23:28その場合は問題設定の最初に「高々N個の状態しか取り得ないプログラムに対して」が必要。
つまり、アルゴリズムがその条件を要求してしまうので、「有限個の状態しか取り得ない任意のプログラム」には適用できない。
00181ですけど．
2008/12/26(金) 12:28:1600191ですけど．
2008/12/26(金) 12:33:59Ａを解析すればそれが取りうる状態数の最大値が分かって高々Ｎ個の状態しかとりえないことが分かる。
よって「有限個の状態しか取り得ない任意のプログラム」の停止問題は
「高々N個の状態しか取り得ないプログラム」の停止問題に帰着するかも。
00201ですけど．
2008/12/26(金) 12:37:290021１３２人目の素数さん
2008/12/26(金) 12:40:08帰着させる事ができるか、という問題か。
じゃぁ、次のプログラムは止まるか判定できるかな？
MAX : 定数
m ← 1
loop { m ← m+1 mod MAX }
mod MAX は MAX で割った余り。
まぁ、普通に考えれば状態数は MAX で済む。
0022１３２人目の素数さん
2008/12/26(金) 12:41:49ううむ、そこは不明瞭な発言だらけになってきてるな。
「解析」アルゴリズムは停止するのか？ｗ
0023１３２人目の素数さん
2008/12/26(金) 12:44:01> loop { m ← m+1 mod MAX }
自分で止まらないことを宣言してるorz
while(m<MAX+1) { m ← m+1 mod MAX }
0024１３２人目の素数さん
2008/12/26(金) 12:46:59http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96
> 大学でチューリングの機械でできないものはノイマン型でもできないと教わった（ようなきがするだけで間違いかもしれませんがが）
あと、ここでこれが出てくるのは何か勘違いしてるんじゃないかな
00251ですけど．
2008/12/26(金) 13:05:03ううんと...
ｍ＝１、 ｍ＝２、...ｍ＝ＭＡＸ-1、ｍ＝０、ｍ＝１、ｍ＝２ ー＞
初期化｜ここからwhile文 ↑二回目
ここでｍ＝２というデータの状態と処理するステップの位置
が完全に一致（つまりプログラムの状態が完全に一致）したことになって無限ループと判明。
しかしこれに理論の飛躍があるといいたいのでしょうね。
見落としはないだろうか？
まず、プログラムの処理ステップは明らかに有限だし、
ｍ＝１からはじまってて．.
ううん、そのプログラムなら判定できるのでは？
00261ですけど．
2008/12/26(金) 13:07:21＞が完全に一致（つまりプログラムの状態が完全に一致）
分かりにくい表現だっだ。
ここでｍ＝２というデータの状態と処理するステップの位置
が過去のある状態のものと完全に一致（つまりプログラムの状態が過去のものと完全に一致）
0027１３２人目の素数さん
2008/12/26(金) 13:17:03N << MAX の場合はどうやってNに還元する？
0028１３２人目の素数さん
2008/12/26(金) 13:24:58あれも、条件の順序が違うと話が全然違うので今回のことと近いと思うよ。
「任意のεに対して、あるδがあって」→各点連続
「あるδがあって、任意のεに対して」→一様連続
今回も一様に示せるアルゴリズムがあるかどうかって問題になると思うよ。
00291ですけど．
2008/12/26(金) 13:29:53そもそもＮというのはなんですか？
Ｎは状態数として23が示したプログラムの状態はデータの状態だけでも
MAX個あるからN << MAXはありえないんじゃない？
0030１３２人目の素数さん
2008/12/26(金) 13:33:14N は命題の「高々 N 個の状態しか取り得ない」に対するもの。
データ状態はMAX個だけど、それはプログラム上は保持する必要がないからな。
0031KingMind ◆KWqQaULLTg
2008/12/26(金) 13:35:150032１３２人目の素数さん
2008/12/26(金) 13:36:51自分で書いてて言い方が悪いな。
>>19 に対する発言ですよ。
というか、>>19自体が少し変だな。
「ある有限個の状態しか持たないことが分かっているプログラム」って何だ？
0033１３２人目の素数さん
2008/12/26(金) 13:38:240034１３２人目の素数さん
2008/12/26(金) 16:12:13よって状態が有限だろうが不可能であることに変わりはない。
お前らまず元の問題を理解してから議論しろよ。
0035１３２人目の素数さん
2008/12/26(金) 17:43:07せめてどっかのスレで自分の考えが正しいかどうか確かめてからスレ立てしろよな。
0036１３２人目の素数さん
2008/12/26(金) 21:10:270037１３２人目の素数さん
2008/12/26(金) 21:39:34停止判定可能という説が濃厚みたいだが。
0038１３２人目の素数さん
2008/12/26(金) 21:49:20このスレはまだ内容があるほうだろ。
停止するプログラムがとりうる状態の数の上限を知りたければビジービーバー関数とか調べて見れ。
0039１３２人目の素数さん
2008/12/27(土) 00:19:25>>1がチューリング機械の初歩を勉強するスレになってるだけだが
チューリング機械のテープが有限だったら停止判定可能とか当たり前だろ・・・
0040１３２人目の素数さん
2008/12/27(土) 00:33:34TMの状態のことを言っているのではなく、状態＋テープに書かれた記号列のことを指してるの？
プログラムは状態とテープ（メモリ）直前の状態と最初に与えられた処理手続きだけで次の状態と次のテープ（メモリ）上の文字列が決定するんだけど、
テープ（メモリ）を忘れたらもちろんオートマトンと一致するから、停止問題とか考える意味ないけど。
004140
2008/12/27(土) 00:55:25ビジービーバーって、与えられたnに対して、状態数nの全てのTMを考えて
そのうちで一番大きい出力のものを出す関数ではなかった？
>>1の言ってる話は、現実のコンピュータは状態数もテープ長（メモリ）も有限だから、停止判定ができるってこと？
もちろんずっとその有限から増やさないというなら、
そういうコンピュータたちだけを局所的に停止判定するプログラムは存在するというのは正しい。
ただし、停止性判定の決定不可能性という話の言っていることは、
もし、その状態数とテープ長の上界がnであるようなコンピュータたちの停止性判定をするプログラムをP(n)としたとき、
nからP(n)を求めるプログラムが存在しないということ。
0042自転車操業
2008/12/27(土) 02:37:39ＴＭとＬＢＡについての停止性判定問題についての差異が
理解できるよう工夫してあって実に良くできてますな。
わしはこれ以上口出しませんわ。
アク禁を最近よく食らうことが多いので。
0043１３２人目の素数さん
2008/12/27(土) 03:26:25LBA = 線形境界付きオートマトン
>>1
線形境界付きオートマトンの停止性判定の証明乙
計算論を勉強中のちょうどいい練習問題だったろう
0044１３２人目の素数さん
2008/12/27(土) 07:36:48そこまでしてスレに立ってほしくないのか
その望みが叶った所でなんの意味があるのか分からんが
0045１３２人目の素数さん
2008/12/28(日) 17:05:43他のクソスレの類に比べれば、遙かに有意義で内容があると言えよう。
0046１３２人目の素数さん
2008/12/28(日) 22:00:58個の板って学問版だよね?
>>41
>>停止判定するプログラムは存在する
は？存在しないよね。
「第二種の永久機関は作れる」
「相対性理論は間違い」
「地球は間もなくフォトンベルトに入る」
そういうのの類の糞釣りスレになぜここまで付く？
数学的にできないと証明されてることも知らずに何議論してる?
レベル低すぎ。
0047１３２人目の素数さん
2008/12/29(月) 06:19:09そんなものは学問では無いから俺はやらない！」と言って認められるか試してみればいいんじゃね？
0048１３２人目の素数さん
2008/12/29(月) 07:45:430049１３２人目の素数さん
2008/12/29(月) 14:38:08大丈夫じゃないのはお前だな。
スレタイに「ノイマンマシンの」と入れ忘れてるだけ、というのは
>>1 を読めばわかる。
0050１３２人目の素数さん
2008/12/29(月) 17:50:55解っているなら初学者の勉強会に
参加こそしないまでも
邪魔してまわるようなことはしないだろう
0051１３２人目の素数さん
2008/12/29(月) 20:45:28>基礎論のスレでやれ
>twitterでやれ
>質問スレを探せない阿呆に読ませる雑誌はない
とか誘導してる書き込みも>46も全部同じ人が風紀委員として書き込んでるのかね
0052１３２人目の素数さん
2008/12/31(水) 08:18:44それを入れると、「サブジェクトが長すぎます」って。
0053粋蕎<ｲｯｷｮｳ>
2008/12/31(水) 15:03:24しかし偽科学って言い方は何だったんじゃろう…
0054粋蕎<ｲｯｷｮｳ>
2008/12/31(水) 15:05:29幾つかのスレに回って、それでも尚有意義な問題である場合に
スレ立てに至るべきじゃったのう
0055１３２人目の素数さん
2008/12/31(水) 23:26:270056１３２人目の素数さん
2009/01/04(日) 23:02:44停止問題の決定不可能性証明も実際にはできないんだろうなあ。
>>41-43が言ってるような限定された停止判定が決定可能だというのは、
停止問題関連の話をかじればすぐに証明できる定理で、よく知られた数学的事実なのに、
よくぞ自信満々に>>46のような発言をできるものだ。
0057１３２人目の素数さん
2009/01/04(日) 23:15:40それ以上に>>46の発言はおかしいと思っただけな
0058１３２人目の素数さん
2009/01/04(日) 23:21:03チューリング完全でない一部の計算モデルに関する停止問題のことな
0059１３２人目の素数さん
2009/01/29(木) 07:31:050060１３２人目の素数さん
2009/02/04(水) 22:40:150061１３２人目の素数さん
2009/02/08(日) 10:12:220062１３２人目の素数さん
2009/02/09(月) 08:00:29それだけ俄かって事だろ
00631
2009/03/16(月) 12:21:490064１３２人目の素数さん
2009/03/16(月) 12:28:260065１３２人目の素数さん
2009/04/09(木) 00:17:55ある計算モデルMに対して定数Cが存在し、
任意の自然数nにおいてBB(n)より大きい値を返すサイズC*n以下のMのプログラムが存在するなら、
Mはチューリング完全といえるか？
0066１３２人目の素数さん
2009/04/09(木) 23:05:580067１３２人目の素数さん
2009/04/09(木) 23:13:120068１３２人目の素数さん
2009/04/10(金) 01:24:31■ このスレッドは過去ログ倉庫に格納されています