-
プログラム
-
すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
-
UPLIFTで広告なしで体験しましょう！快適な閲覧ライフをお約束します！
チューリングマシンは可算個しかないからすべての言語は判定できないという。
じゃあチューリングマシンを拡張して濃度を増やせばいいんじゃね？
そのような拡張を考えたときどのようなものが出来上がるか？あるいは無意味なのか？
そんなことを考えるスレ。 - コメントを投稿する
-
どういうこと？
オラクルテープの内容は所与だよね？ -
すまん、所与の意味が分からんｗ
オラクルテープの内容の扱いは状態遷移表の内容の扱いに近い。
通常テープの入力の扱いとはまったく違う。 -
すまん、そろそろ寝るわ。
これでも平日は朝６時に起きなきゃならん。 -
えーと、前提知識として与えられているものと仮定できるんだよね？っていう事
そのテープの内容は、勿論テープを媒体として与えられているとここでは仮定して、
>>70は「オラクルテープ」と言う名のテープからテープ1へ転写してる。 -
そう、オラクルテープは前提の知識として与えられていると仮定できる。
そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
オラクルテープは可算無限ビットの情報を所与に出来る。
だから拡張チューリングマシンは通常のチューリングマシンと本質的に異なる。 -
> そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
違う。
そのオラクルテープの「内容」が所与なんだから
その内容がテープ上に記述された状態で計算を開始するものとすれば
可算無限長の情報を所与とする事は出来る。
1936年の論文の236ページに、可算無限個の情報による初期化の例が載ってる。
https://www.cs.virgi...uring_Paper_1936.pdf -
何でも良いから
拡張チューリングマシンで計算できて普通のチューリングマシンで計算出来ないようなプログラムを
オラクルテープの内容の計算方法含めて書いてみてくれない？ -
例えばチューリングマシンの停止問題。
チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
オラクルテープにH(x)を書き込んで置き、入力でxが与えられたら
オラクルテープのx番地を読み込んで1なら受理、0なら拒否する。
こうすることでチューリングマシンの停止問題を判定する拡張チューリングマシンが構成できる。
もちろん我々は具体的にこのオラクルテープを構成することは不可能だろう。
しかしチューリングマシンの停止問題を判定する拡張チューリングマシンは確かに存在するのである。 -
やっぱ「所与」のところにすれ違いがあるのかな？
-
つか本屋行けてないわ。
マイナー分野だしでかい本屋で探しても見つかるかどうか… -
>>80
どうやってH(x)を計算するの？
H(x)を計算できる前提で拡張チューリングマシンが存在するのなら
Aならば(=>)BでいうところのAが偽なのでBはなんでも言えるんだがw
例えばH(x)が計算できるならば1+1=3であるも真になるぞ -
具体的にH(x)は「計算」では求められない。
しかし拡張チューリングマシンは存在する。
そういうことだ。 -
一点目:
> チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
・プログラムの個数は非可算無限個。辞書順に並べることは出来ないし、「x番目」という言い方も出来ない。
・マシンへの入力を考慮していない。
・問題解決の前提知識として、その問題の答えを要求している; 拡張チューリングマシンが存在する為には、拡張チューリングマシンが必要である。
どう回避する？
二点目:
Nビットで表現できる全てのプログラム・入力対について判定する問題に置き換える。
つまり、プログラムは有限個であり、辞書順に並べることが出来る。
又、そのプログラム・入力対が有限時間で停止するかどうかは、つまりH(x)の値は既知であると仮定する。
この時、プログラムxが停止するかどうかを判定する>>80による拡張チューリングマシン上のプログラムの
時間計算量はO(2^N)である。
ところで、例えば世界最小のインタプリタは98バイト、そのインタプリタが停止しない最小の入力は3バイトなのでN=808について考えると、
拡張チューリングマシンが1秒間に10^100ステップ計算出来たとしても、終了までに平均2.7*10^135年掛かる。
もう少し現実的なプログラムは無いの？ -
>プログラムの個数は非可算無限個。
は？
今問題にしているのは通常のチューリングマシンの停止問題であって
拡張チューリングマシンの停止問題ではないぞ？
>問題解決の前提知識として、その問題の答えを要求している
もちろんそうだが。
そういう見方をすれば確かにこれはつまらない。
しかし真に興味深いのは２つのオラクルテープの関係を調べることなのである。
一方のオラクルテープは他方のオラクルテープより真に強力、ということがあり得る。
そのような関係が美しい数学的構造を成すのである。
>もう少し現実的なプログラムは無いの？
お前のような知識のあるやつがこんなセコイ因縁を吹っかけてくるとは失望したぞ。 -
>>86
もちろんそうだが、じゃねぇよ。
三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
ついでで悪いんだけど、
プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？
俺には非可算無限個にしか思えないんだ。 -
>プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？
うん？
チューリングマシンが可算個、入力が可算個で可算の直積集合になると思ったがなにか勘違いしてるだろうか？
>三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
意味わからんどんな例えだ。 -
ごめんよ、よーく考えたらプログラムは高々可算無限個だったわ。
(えーと、状態集合Qの大きさをq、入力集合Γの大きさをγとすると、O(q^γ)パターン存在する。
とすると、状態の集合Qの大きさがqであるようなチューリングマシンはO(q^γ x log q)ビットの情報と等価に変換できる。
んでもって、qとγは有限の値を取るからー)
実数の濃度みたいに対角線論法で非可算個になる気がしてた。
喩えについてはユークリッド幾何学の第五公理に関する歴史と論争について知ってれば分かるかと
https://ja.wikipedia...9A%E5%85%AC%E6%BA%96 -
本題に戻るけど
計算不能なテープをどうやって用意するの？ -
>喩えについてはユークリッド幾何学の第五公理に関する歴史と論争について知ってれば分かるかと
すまん、知らん。
>計算不能なテープをどうやって用意するの？
実際に用意はできないがあると仮定して推論を進めるのである。 -
思わず議論が白熱して張り付いてしまったがこれはいかんなｗ
張り付くの自重せねばｗ -
仮定して推論を進めるのが有効なのは背理法の時だけかと
-
詳しくはしらんがリーマン予想が真ならば〜と仮定して推論を進めた論文が結構あるそうだぞ。
-
それは、証明はされていないけど正しいと思われているから。
P≠NPを仮定すれば現代の暗号は安全だっていうのも同じだね。
一方で、君は計算することが出来ないという事が証明されている数が所与であるという
無茶苦茶な仮定を置いてる。
特技：イオナズンとか言っちゃう厨二病患者と似たり寄ったり。 -
読んでないが>>78の論文とやらが計算することが出来ない状態を所与にした論文とちゃうの？
-
持ちネタも尽きたし新しいネタを仕入れないとな。
暫くこのスレはお休みかな。 -
チューリングマシンの停止問題を解けるオラクルテープを使うとビジービーバー関数が計算出来きるとか
通常のチューリングマシンの停止問題を解けるオラクルテープをもつ拡張チューリングマシンの停止問題を解けるオラクルテープは
通常のチューリングマシンの停止問題を解けるオラクルテープよりさらに強力だとか、そんな感じのネタを仕入れたい。 -
テープ自体に差はないんじゃないのかな。
結局テープにH(x)とかを書き込むんでしょ？
それともオラクルテープの内容が違うだけで別クラスの拡張チューリングマシンになるのだろうか -
もっと下位のオートマトンをより上位に拡張する方法を一般化したほうが早いんじゃないかな
FSMでは何が計算できて、何が計算出来ないのか。それは何故か。
PDAやLBAだとどうだろうか。 -
FSM＝正規表現
PDA＝文脈自由文法
終了 -
チューリングマシンの停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシン…
と可算無限回繰り返した時のオラクルテープの内容は如何なるものか。 -
チューリングマシンの停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシンは
チューリングマシンの停止問題を解けるや否や？ -
HALT(TM, x)が解ければAccept(TM, x)もとけるので
入力x∈Σ^*を受け取って∃y∈Σ^*.Accept(y,x)を返す拡張チューリングマシンMを考えた時
その言語L(M)は「あるチューリングマシンM'(=y)によって判定されうる言語」の集合なはず -
よく考えたらAccept(y, x)とかいちいち構築しなくても
オラクルテープあるんだから「i番目の入力xはあるTMによって判定されるか」を0、1で書き込んでおけば一発だね
オラクルテープ万能すぎじゃないかい？ -
エミール・ポストのwikiに
停止性問題よりもチューリング次数が低い計算不可能な帰納的可算集合が存在するかという問題を提起した。
これは1950年代に肯定的に解決
てのがあるんだけどだれか詳しいこと知らない？ -
うお英語か
まあ、サンクス -
チューリング次数について書かれた良和書が欲しい。
英語分からん。 -
NP問題周辺の話題に多項式階層というのがあるが
チューリング次数と何か繋がっているのだろうか -
wikipediaで会話するスレ
-
お前らって本当に浅い知識で語りたがるよな
-
>>117
お前の深い知識を披露してくれてもいいんだぜ？ -
巨大数探索スレ
http://wc2014.2ch.ne...cgi/math/1448211924/
の497に面白そうなのがあった。
http://projecteuclid...d.pl/1235415519#info
でも英語か〜 -
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』
5E8RY -
SQ1
↑今すぐ読める無料コミック大量配信中！↑
