- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
78 ：デフォルトの名無しさん[sage]：2016/05/24(火) 09:40:53.38 ID:TtTF6uFS - > そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
違う。
そのオラクルテープの「内容」が所与なんだから
その内容がテープ上に記述された状態で計算を開始するものとすれば
可算無限長の情報を所与とする事は出来る。
1936年の論文の236ページに、可算無限個の情報による初期化の例が載ってる。
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
79 ：デフォルトの名無しさん[sage]：2016/05/24(火) 09:43:11.68 ID:TtTF6uFS - 何でも良いから
拡張チューリングマシンで計算できて普通のチューリングマシンで計算出来ないようなプログラムを
オラクルテープの内容の計算方法含めて書いてみてくれない？
|
- スレを勃てるまでもないC/C++の質問はここで 24 [転載禁止]©2ch.net
793 ：デフォルトの名無しさん[sage]：2016/05/24(火) 18:14:10.60 ID:TtTF6uFS - >>792
環境依存。
実際に使ってみて、駄目だったら使うな。
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
85 ：デフォルトの名無しさん[sage]：2016/05/24(火) 20:39:04.50 ID:TtTF6uFS - 一点目:
> チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
・プログラムの個数は非可算無限個。辞書順に並べることは出来ないし、「x番目」という言い方も出来ない。
・マシンへの入力を考慮していない。
・問題解決の前提知識として、その問題の答えを要求している; 拡張チューリングマシンが存在する為には、拡張チューリングマシンが必要である。
どう回避する？
二点目:
Nビットで表現できる全てのプログラム・入力対について判定する問題に置き換える。
つまり、プログラムは有限個であり、辞書順に並べることが出来る。
又、そのプログラム・入力対が有限時間で停止するかどうかは、つまりH(x)の値は既知であると仮定する。
この時、プログラムxが停止するかどうかを判定する>>80による拡張チューリングマシン上のプログラムの
時間計算量はO(2^N)である。
ところで、例えば世界最小のインタプリタは98バイト、そのインタプリタが停止しない最小の入力は3バイトなのでN=808について考えると、
拡張チューリングマシンが1秒間に10^100ステップ計算出来たとしても、終了までに平均2.7*10^135年掛かる。
もう少し現実的なプログラムは無いの？
|
- C言語なら俺に聞け！ Part 135©2ch.net
228 ：デフォルトの名無しさん[sage]：2016/05/24(火) 20:51:45.36 ID:TtTF6uFS - 間違ってc++スレに迷い込んだ気がした
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
87 ：デフォルトの名無しさん[sage]：2016/05/24(火) 20:59:57.89 ID:TtTF6uFS - >>86
もちろんそうだが、じゃねぇよ。
三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
ついでで悪いんだけど、
プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？
俺には非可算無限個にしか思えないんだ。
|
- スレを勃てるまでもないC/C++の質問はここで 24 [転載禁止]©2ch.net
796 ：デフォルトの名無しさん[sage]：2016/05/24(火) 21:06:09.03 ID:TtTF6uFS - _allocaなんかはどこかのクソ環境だと被るよね。
|
- スレを勃てるまでもないC/C++の質問はここで 24 [転載禁止]©2ch.net
800 ：デフォルトの名無しさん[sage]：2016/05/24(火) 21:15:34.18 ID:TtTF6uFS - 1000 < 500はfalseだよね
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
89 ：デフォルトの名無しさん[sage]：2016/05/24(火) 21:54:01.44 ID:TtTF6uFS - ごめんよ、よーく考えたらプログラムは高々可算無限個だったわ。
(えーと、状態集合Qの大きさをq、入力集合Γの大きさをγとすると、O(q^γ)パターン存在する。
とすると、状態の集合Qの大きさがqであるようなチューリングマシンはO(q^γ x log q)ビットの情報と等価に変換できる。
んでもって、qとγは有限の値を取るからー)
実数の濃度みたいに対角線論法で非可算個になる気がしてた。
喩えについてはユークリッド幾何学の第五公理に関する歴史と論争について知ってれば分かるかと
https://ja.wikipedia.org/wiki/%E5%B9%B3%E8%A1%8C%E7%B7%9A%E5%85%AC%E6%BA%96
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
90 ：デフォルトの名無しさん[sage]：2016/05/24(火) 21:56:05.64 ID:TtTF6uFS - 本題に戻るけど
計算不能なテープをどうやって用意するの？
|