停止性問題は解決可能では？

ある入力に対して有限時間内にあるプログラムが停止するかどうか判定する
チューリング機械のアルゴリズムは作成不可能だとする結論がすでに出ている。
しかしそれはチューリング機械に限っての話である。
我々か普段目にするパソコンなどの一般的な機械はチューリング機械などではなく
ノイマン型の機械である。
しかもその内部に保持できる状態は高々有限個である。よって、停止しないときは、
必ず開始から有限時間内に無限ループ状態に突入する。そして無限ループ中のあるときに現れた状態は
必ず有限時間内に再び現れる。それを検出すれば無限ループ＝停止しないと結論できる。
また、有限時間内に停止するなら、そのプログラムを順に追っていけば有限時間内に停止するか判定でき、
判定アルゴリズムもまた有限時間で停止する。
つまりこのようなアルゴリズムなら停止問題を解けるはずである。
空のリスト空間Ｌを作成＝＞�@作成プログラムＡを1ステップ実行=>その状態と同一のものがＬにあるか判定し結果をＢとする|||
If(Bが真）｛
結果「停止しない」を返す。
｝else{
Ｌに現在の状態を追加し�@に戻る。
}
この過程の途中、�@の結果Ａが終了したとき結果「停止する」を返す｜｜｜｜
よって停止問題を解くアルゴリズムはコンピュータアーキテクチャ（しかも現在広く使われているものも）によって
は可能となることがある。
===========================＝＝＝＝＝＝＝＝
個の考えは今さっき思いついたものなのですが正しいですか？
大学でチューリングの機械でできないものはノイマン型でもできないと教わった（ようなきがするだけで間違いかもしれませんがが）
のですが。
プログラムというのは直前の状態と最初に与えられた処理手続きだけで次の状態が決定する
（オートマトンの拡張）のでたぶん間違ってはいないと思うのですが。

>>1
ふむ，有限性の仮定か．
その場合，保持するリスト空間 L の有限性はどう議論する？

実現しうる状態が有限個しかないなら、それを保持するＬの要素数
も有限で良いのでは？

>>3 = >>1 ？

>>4
>>3 = >>1 ？
そうだけど、なにか？

>>5 了解した。俺と同じ事をコメントした人かな、と思ってね。
L が有限なら、それを超える状態を取りうる場合はどういうアルゴリズムを適用して L を簡約すればいいんだ？
もちろんそのアルゴリズムの説明には、どの段階でループ検出できる状態となるか予測が必要となるわけだが。

また偽科学の類か。2種の永久機関は作れるとかいうのと同じだろ。
相対性理論は間違いだらけ、みたいなのもあるな。
作れないと数学的に証明されてるから絶対作れない。相手にする必要なし。
”はいはいわろすわろすで”終わるすれだよ！！

Ｌは際限なく増えてもいいが、Ａの状態の有限性によって「結果として」有限個の要素しか持つ必要が
ないというのじゃ駄目ですか？
リストというのはポインタでつなげて自由に要素数を変えられるあのリスト構造を意識して使った言葉なのですが。

>>3 の言いたいことを勘違いしたことに書いた後気付いた。
つまり、状態が有限なんだから「それに合わせた」ストレージ L を用意せよと言うことだな。
例えば、B の状態が N ビット利用するなら、全ての状態を保持しうる 2^N ビットを理論上用意すれば
ループ検出は可能かもしれない、と。

というか、スレのタイトルが紛らわしいと思うのだが。
「状態数有限ならば」が欲しい。

9>>
そういうこと！！
7>>
まじめなんだが...

>>7
とりあえずsage進行で。
断定した言い方じゃなく、一応質問してるからいいんじゃないですか。

>>8
それは分かるよ。
ただ有限性の仮定の問題で、有限個の状態しか持ち得ないあらゆるプログラム、というのが一体どういうものか、というのが難しいんです。
N 個の状態を持つ場合に 2^N のストレージが必要になるから任意の N に対して成立するにはストレージ無限性が必要になる。
つまりは L の無限性が必要だと思うんだが。

Ａが有限であるという仮定のもとでは十分大きな有限数Ｎ’を仮定しておけばいいのでは？
いや、仮定を強くしてＡの状態数をＮ’’以下であるとするとどうだろう。
>>1で書いたことからだいぶ外れるけど。

>>11 自己レス。
N 個の状態を持つ場合に 2^N のストレージが必要になる
↓
N 個の状態を持つ場合に N のストレージが必要になる

Ａが有限であるという仮定
↓
Ａが有限個の状態を取るという仮定
煮変更。

>>12
そう思うよね？
でも、問題の定義として停止性判定アルゴリズムができるか、という問題なんだから
そのアルゴリズムには

1.ストレージがあってそれを利用するアルゴリズムがあって
2.任意の有限個の状態しか取り得ないプログラムの停止性が判定できる。

という順番になるので、この場合のストレージが有限では困るんだが。

>>任意の有限個の状態しか取り得ないプログラム
というのは>>1ではＡにあたるプログラムのこと？
Ａが何通りの状態を取りうるのかの最大値が分かってても駄目？

>>16
その場合は問題設定の最初に「高々N個の状態しか取り得ないプログラムに対して」が必要。
つまり、アルゴリズムがその条件を要求してしまうので、「有限個の状態しか取り得ない任意のプログラム」には適用できない。

あなるほど。

いや待てよ。ある有限個の状態しか持たないことが分かっているプログラムをＡとして
Ａを解析すればそれが取りうる状態数の最大値が分かって高々Ｎ個の状態しかとりえないことが分かる。
よって「有限個の状態しか取り得ない任意のプログラム」の停止問題は
「高々N個の状態しか取り得ないプログラム」の停止問題に帰着するかも。

例えば、Ａを解析してＡがｎ bitの領域を使用することが分かれば高々2＾ｎこの状態しかとらないことが分かるのでは？

>>19
帰着させる事ができるか、という問題か。
じゃぁ、次のプログラムは止まるか判定できるかな？

MAX : 定数
m ← 1
loop { m ← m+1 mod MAX }

mod MAX は MAX で割った余り。
まぁ、普通に考えれば状態数は MAX で済む。

>>20
ううむ、そこは不明瞭な発言だらけになってきてるな。
「解析」アルゴリズムは停止するのか？ｗ

>>21
> loop { m ← m+1 mod MAX }
自分で止まらないことを宣言してるorz
while(m<MAX+1) { m ← m+1 mod MAX }

>>1　この辺をとっかかりに文献探して読んだ方が早いぞ
http://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

> 大学でチューリングの機械でできないものはノイマン型でもできないと教わった（ようなきがするだけで間違いかもしれませんがが）
あと、ここでこれが出てくるのは何か勘違いしてるんじゃないかな

>>23
ううんと...
ｍ＝１、　ｍ＝２、...ｍ＝ＭＡＸ-1、ｍ＝０、ｍ＝１、ｍ＝２　ー＞
初期化｜ここからwhile文　　　　　　　　　　　　　　↑二回目
ここでｍ＝２というデータの状態と処理するステップの位置
が完全に一致（つまりプログラムの状態が完全に一致）したことになって無限ループと判明。
しかしこれに理論の飛躍があるといいたいのでしょうね。
見落としはないだろうか？
まず、プログラムの処理ステップは明らかに有限だし、
ｍ＝１からはじまってて．.
ううん、そのプログラムなら判定できるのでは？

＞ここでｍ＝２というデータの状態と処理するステップの位置
＞が完全に一致（つまりプログラムの状態が完全に一致）
分かりにくい表現だっだ。

ここでｍ＝２というデータの状態と処理するステップの位置
が過去のある状態のものと完全に一致（つまりプログラムの状態が過去のものと完全に一致）

>>25
N << MAX の場合はどうやってNに還元する？

ちょっと話がずれるけど、ε-δ論法は知ってる？
あれも、条件の順序が違うと話が全然違うので今回のことと近いと思うよ。

「任意のεに対して、あるδがあって」→各点連続
「あるδがあって、任意のεに対して」→一様連続

今回も一様に示せるアルゴリズムがあるかどうかって問題になると思うよ。

>>27
そもそもＮというのはなんですか？
Ｎは状態数として23が示したプログラムの状態はデータの状態だけでも
MAX個あるからN << MAXはありえないんじゃない？

>>29
N は命題の「高々 N 個の状態しか取り得ない」に対するもの。
データ状態はMAX個だけど、それはプログラム上は保持する必要がないからな。

Reply:>>28 お前は念の盗み見による人への関与を排除して来い。

>>30
自分で書いてて言い方が悪いな。
>>19 に対する発言ですよ。

というか、>>19自体が少し変だな。
「ある有限個の状態しか持たないことが分かっているプログラム」って何だ？

>>31 どちらさん？スレ違い？

停止性判定が不可能であることの証明に状態という概念は不要。
よって状態が有限だろうが不可能であることに変わりはない。
お前らまず元の問題を理解してから議論しろよ。

「今さっき思いついたもの」程度でわざわざスレ立てんなよ。
せめてどっかのスレで自分の考えが正しいかどうか確かめてからスレ立てしろよな。

なんかスレが立つことに無駄に敏感になっとる奴がいるな

調べてみたけど、チューリングの機械のテープが有限だったら
停止判定可能という説が濃厚みたいだが。

>>36 たしかに。
このスレはまだ内容があるほうだろ。

停止するプログラムがとりうる状態の数の上限を知りたければビジービーバー関数とか調べて見れ。

内容あるかねえ
>>1がチューリング機械の初歩を勉強するスレになってるだけだが
チューリング機械のテープが有限だったら停止判定可能とか当たり前だろ・・・

プログラムの状態ってなんですか？
TMの状態のことを言っているのではなく、状態＋テープに書かれた記号列のことを指してるの？
プログラムは状態とテープ（メモリ）直前の状態と最初に与えられた処理手続きだけで次の状態と次のテープ（メモリ）上の文字列が決定するんだけど、
テープ（メモリ）を忘れたらもちろんオートマトンと一致するから、停止問題とか考える意味ないけど。

>>38
ビジービーバーって、与えられたnに対して、状態数nの全てのTMを考えて
そのうちで一番大きい出力のものを出す関数ではなかった？

>>1の言ってる話は、現実のコンピュータは状態数もテープ長（メモリ）も有限だから、停止判定ができるってこと？
もちろんずっとその有限から増やさないというなら、
そういうコンピュータたちだけを局所的に停止判定するプログラムは存在するというのは正しい。

ただし、停止性判定の決定不可能性という話の言っていることは、
もし、その状態数とテープ長の上界がnであるようなコンピュータたちの停止性判定をするプログラムをP(n)としたとき、
nからP(n)を求めるプログラムが存在しないということ。

教育的に配慮された良スレですな。
ＴＭとＬＢＡについての停止性判定問題についての差異が
理解できるよう工夫してあって実に良くできてますな。
わしはこれ以上口出しませんわ。
アク禁を最近よく食らうことが多いので。

>>42じゃないが勉強中の>>1のために補足しておくと
LBA = 線形境界付きオートマトン
>>1
線形境界付きオートマトンの停止性判定の証明乙
計算論を勉強中のちょうどいい練習問題だったろう

>>39
そこまでしてスレに立ってほしくないのか
その望みが叶った所でなんの意味があるのか分からんが

>チューリング機械の初歩を勉強するスレになってる

他のクソスレの類に比べれば、遙かに有意義で内容があると言えよう。

は？
個の板って学問版だよね?
>>41
>>停止判定するプログラムは存在する
は？存在しないよね。
「第二種の永久機関は作れる」
「相対性理論は間違い」
「地球は間もなくフォトンベルトに入る」
そういうのの類の糞釣りスレになぜここまで付く？
数学的にできないと証明されてることも知らずに何議論してる?
レベル低すぎ。

まぁそういう人は課題出されたときに「こんなのは既に解決されている問題だ！
そんなものは学問では無いから俺はやらない！」と言って認められるか試してみればいいんじゃね？

46はなんでそんな必死なん

>>46
大丈夫じゃないのはお前だな。

スレタイに「ノイマンマシンの」と入れ忘れてるだけ、というのは
>>1 を読めばわかる。

それすら解んないから大騒ぎしてるわけで
解っているなら初学者の勉強会に
参加こそしないまでも
邪魔してまわるようなことはしないだろう

幾つかのスレで
>基礎論のスレでやれ
>twitterでやれ
>質問スレを探せない阿呆に読ませる雑誌はない
とか誘導してる書き込みも>46も全部同じ人が風紀委員として書き込んでるのかね

>>スレタイに「ノイマンマシンの」と入れ忘れてるだけ、
それを入れると、「サブジェクトが長すぎます」って。

半角を使われると良い
しかし偽科学って言い方は何だったんじゃろう…

だが、手順不足は否めない
幾つかのスレに回って、それでも尚有意義な問題である場合に
スレ立てに至るべきじゃったのう

事後にならなんとでも言える

>>46とかの風紀委員さんは、単に数学の結果を暗記してるだけで
停止問題の決定不可能性証明も実際にはできないんだろうなあ。

>>41-43が言ってるような限定された停止判定が決定可能だというのは、
停止問題関連の話をかじればすぐに証明できる定理で、よく知られた数学的事実なのに、
よくぞ自信満々に>>46のような発言をできるものだ。

あ、一応言っておくと、俺もこういうスレが乱立するのはどうかと思っているんだが、
それ以上に>>46の発言はおかしいと思っただけな

補足。限定された停止判定ってのは、>>1や>>41-43のような、
チューリング完全でない一部の計算モデルに関する停止問題のことな

667

チューリングマシンで停止判定できる計算モデルの中で一番強力な計算モデルって何？

age

>>56
それだけ俄かって事だろ

あげてみるか

散れ

ビジービーバー関数をBB(n)とする。
ある計算モデルMに対して定数Cが存在し、
任意の自然数nにおいてBB(n)より大きい値を返すサイズC*n以下のMのプログラムが存在するなら、
Mはチューリング完全といえるか？

age

フェルマーの最終定理程度には単発質問から離れたスレに見えるが

>>51-58 >>62