すべての言語を判定する計算機構
じゃあチューリングマシンを拡張して濃度を増やせばいいんじゃね？
そのような拡張を考えたときどのようなものが出来上がるか？あるいは無意味なのか？
そんなことを考えるスレ。
この時Mは有限個なのでLはdecidableであり、対応するEnumerator Eが存在する
この時次のように動くチューリングマシンM'を考える
入力xに対して、すべてのアルファベットの組み合わせにおけるj番目=xを計算する
前述のEを用いてMjを取り出し、Mjに入力xをシミュレートさせる
もしMjがxを受理したらM'は拒否する、あるいはその逆を行う
すべてのMはdeciderなのでM'もdeciderであり
その言語L(M')もdecidableであるがL(M')はL内にあるどのL(M1...i)とも一致しない
つまり言語を判定できるチューリングマシンがいくつあろうとも
その集合によって判定できない言語L(M')を常に作り上げることができる
つまりすべての言語を判定できるチューリングマシンは存在しない
証明終わり
なんで有限個なの？今考えている拡張は有限とかいう縛りは考えてないぞ。
とにかく判定対象の言語Lはdecidableだというのが肝
すると結局LのEnumerator EとLを判定するマシンMで同じことができる
ここもダウト。
今考えてる拡張はアルファベットを基にしたものとは限らない。
例えば実数を扱えるようにするとか。
実数自体はuncountableなのが問題だけど
実数を扱えるチューリングマシンを”仮定”するならEnumeratorは作れる
ところでEnumeratorって日本語だとなんていうの？列挙？
話を無理矢理な方向にもって行き過ぎ。
uncountable なのは本質なのに。
濃度が増えなきゃ意味ない。
もう寝る。
このオラクル・ストリングに例えばチャイティンのΩのような実数を書き込めばチューリングマシンの停止問題を判定する
拡張チューリングマシンが構成できるだろう。
オラクル・ストリングに任意の実数を書き込めるなら任意の言語を判定する拡張チューリングマシンが構成できると思う。
まあ、これはほとんどトートロジーだよね。
じゃあ、最強のオラクル・ストリングは存在するのか？しないのか？とかそんなことを考えている。
最強のオラクル・ストリングはまさに>>3の議論によって存在しないのか？
よくわからなくなってきたｗ
言語に含まれるなら１含まれないなら０という風に数値を並べ実数を構成する。
ある実数aをオラクル・ストリングにもつ拡張チューリングマシンから生成できる実数の集合をL(a)とする。
Not(a∈L(b)) And Not(b∈(L(a))を満たすような実数の組(a,b)は存在するか？
まず文字列の長さでならべてそれぞれの長さに対して辞書順でならべたほうがいいかな。
濃度より明らか
ゆえに最強のオラクル・ストリングは存在しない。
よくわからん。
>>16って正しい？
自信なくなってきたｗｗｗ
誰かツッコミ頼む。
かな
拡張して濃度を上げるってんならその拡張をどうやるかについて最初に話すべきじゃない？
俺よりいいアイディア持ってるやつがひょっとしたらいるかと思ってな。
遅まきながら俺のアイディアは>>11で示した。
まあ当たり前かな。
相対計算可能性
チューリング次数
チューリング還元可能
ただの趣味。
本でも買うか…
形式的に書くと、こんな感じかな。
拡張したチューリングマシン = {Tape, State, Position, Delta, Lambda, Mu}
Tape: Array of Number
State: Integer
Head-Position: Integer
Delta = State * Tape[Position] -> Number
Lambda = State * Tape[Position] -> State
Mu = State * Position -> {-1, 0, 1}
Transition = {Tape(n), State(n), Position(n)} ->
{
Tape(n)[-Infinity .. Position(n) - 1] .. Delta(State(n), Tape(n)[Position(n)]) .. Tape(n)[Position(n) + 1 .. Infinity],
Lambda(State(n), Tape(n)[Position(n)]),
Position(n) + Mu(State(n), Position(n))
}
但しIntegerは可算無限集合、Numberは非可算無限集合、Arrayは高々可算無限長の配列とする。
とすると
初期状態{Tape(0), State(0), Position(0)}が与えられていると仮定する。
補題1
Tape(0)[-Infinity .. Infinity]に含まれる値の個数は高々加算無限個なので、
ある関数fが存在し、Tape(0)に存在する全ての値rは、ある整数iが存在し、f(i) = rを満たす。
補題2
整数は自然数に一対一対応可能なため、ある関数gが存在し、Tape(0)に存在する全ての値rは、
ある自然数nが存在し、g(n) = rを満たす。
定理3
g(-n-1) = Delta(State(n), Tape(n)[Position(n)])を満たすように関数gを選ぶ。この時
任意の非負整数nに対し、Tape(0..n)に含まれる値の個数は可算無限個である。
証明3
帰納法による。
n = 0の時、Tape(0..n)に含まれる値の個数は可算無限個である。
n = kの時にTape(0..k)に含まれる値の個数が可算無限個であると仮定する。
n = k + 1の時、Tape(k)に含まれず、かつTape(k + 1)に含まれるような値が存在するとすれば、
その値はDelta(State(k), Tape(k)[Potision(k)])と等しい。
その値をg(-k-1)と置くと、Tape(0..k+1)に含まれる値は全て
ある関数gを用いて整数と一対一対応可能である為
Tape(0..n)に含まれる値の個数は加算無限個である。
よって、以下の定理が成り立つ
定理4
この方法により拡張されたチューリングマシンの計算能力は、
元のチューリングマシンと等価である。
証明4
高々加算無限回の演算によってテープに出力可能な値の集合の濃度がN0に等しい事から、
それらの値を適切に符号化する事によって
元のチューリングマシンで高々可算無限回の演算をエミュレート出来る為自明。
>>21って>>11のと違うやつだよね？
>>21だと濃度も増えてないっしょ？多分。
よければ>>11のも形式的に書いてくれんか？
その結果得られた拡張だと上手く行かないよって事を言った。
>>11をもうちょっと分かりやすく書きなおしてくれない？
もしかしたら俺が勘違いして>>1が意図したのとは違う拡張をしてるかも知れんから。
拡張チューリングマシンは以下の要素からなる
１．状態の集合Q
２．オラクルテープの内容O
３．入力アルファベットΣ
４．テープ・アルファベットГ
５．遷移関数δ:Q x Г x {0,1} -> Q x Г x {L,R} x {L,R}
６．q_0∈Qは開始状態
７．q_accept∈Qは受理状態
８．q_reject∈Qは拒否状態
拡張チューリングマシンは以下のように動作する。
通常のテープとオラクルテープがあり、
それぞれのテープの上に通常ヘッド、オラクルヘッドが載っている。
オラクルテープには可算無限長の0,1のデータが書き込まれている。
初期状態では通常のテープには入力が書き込まれていて、
通常ヘッド、オラクルヘッドはともにそれぞれのテープの左端にあり、
状態はq_0である。
拡張チューリングマシンは１ステップで通常ヘッドの記号とオラクルヘッドの記号を読み込み、
それと状態にしたがって通常テープの書き換え、通常ヘッドの移動、オラクルヘッドの移動、状態の遷移を行う。
状態がq_acceptになればその入力を受理する。
状態がq_rejectになればその入力を拒否する。
オラクルテープの存在によって拡張チューリングマシンの濃度は可算を超える。
Γが有限集合であると仮定すると、
それは単にテープが2つあるチューリングマシンって事になると思うんだけど
テープが2つあるチューリングマシンはテープ1つのチューリングマシンと等価。
テープ上の記号の集合をΓ∪{0, 1}とする。
初期状態として、4*i番地と4*i+1番地は非負整数iに対し0で初期化し、負の整数iに対し1で初期化する。
また、4*i+2番地は入力テープ上の添字iのデータで、4*i+3番地はオラクルテープ上の添字iのデータで初期化する。
また、初期状態でテープヘッドは添字0にあるものとする。
状態集合は、エミュレート先の状態集合Qに対しQ x Γ x {0, 1} x Γ x {L, R} x {L, R}の高々定数倍となる。
以下ループ
・手続きS1を呼び出す
・更に2回右へ移動し、テープの値を読み込み、保持する。この値を値(1)とする。
・1回左に移動する
・手続きS1を呼び出す
・更に2回右へ移動し、テープの値を読み込み、保持する。この値を値(2)とする。
・値(1)と値(2)、現状態から次状態と出力するべき値(3)、二つの移動(1)(2)を計算し、それを保持する
・3回左へ移動する
・手続きS1を呼び出す
・更に2回右へ移動し、テープへ値(3)を出力し、2回左へ移動する
・移動(1)がLの場合、4回左へ移動し、テープへ0を出力する。
・移動(1)がRの場合、テープへ1を出力する。
・1回右へ移動する
・手続きS1を呼び出す
・移動(2)がLの場合、4回左へ移動し、テープへ0を出力する。
・移動(2)がRの場合、テープへ1を出力する。
・1回左へ移動する
手続きS1の定義:
・現在の値が0と等しい場合、4回左へ移動し、もう一度この行を実行する
・現在の値が1と等しい場合、4回右へ移動し、もう一度この行を実行する
定義修了
s/修了/終了/
あと、S1での「現在の値」は現在のテープヘッドから読み込んだ時の値って読み替えて。
>>37はその拡張を踏まえてるって事。
例えば、チューリングマシンで足し算をするアルゴリズムは
初期状態として1進数で2つの数がテープに書かれていると仮定する場合が殆ど。
そもそもは無限長のテープを仮定するんだから、
可算無限個のデータ列がそのテープ上に記述されているとするのは自然な発想だと思うんだけど。
オラクルテープの内容は入力ではなくてチューリングマシンの一部。
状態とかと似たようなもんかな？
「入力」は何を指してる？
俺は全てのテープ上に存在するデータの集合を指して「入力」って言ってるけど、
君はそうでないように思える。
オラクルテープの内容が計算開始時点で所与であると仮定するならば、
テープとヘッダをもう一組追加するのと何ら変わりはない。
複数のテープがある時に、遷移前にテープへデータを書き込まないようなヘッダの存在を許す拡張は至って普通。
ついでに言うと、通常テープに対する任意の入力列xに対してそのプログラムが有限時間で停止すると仮定するならば、
その停止時刻をT(x)とした時に、オラクルテープの添字T(x)の右側は無視できる。
何故ならそこまでヘッダを動かすのに最低でもT(x)時間掛かるから。
とするならば、オラクルテープが可算無限長であろうが有限長であろうが同じ議論が成り立つと思うのだけど。
>その停止時刻をT(x)とした時に、オラクルテープの添字T(x)の右側は無視できる。
これはそうはならない。
なぜなら停止時刻は入力によって左右されるものだから。
入力が大きくなれば停止時刻も大きくなり、
結果、オラクルテープが可算無限長もつのは本質的である。
ふぅむ
> なぜなら停止時刻は入力によって左右されるものだから。
その入力によって左右される値を関数形でT(x)と書いたのだけど・・・・・・
今、有限長入力列xが与えられたとしよう。
但し、有限時間T(x)でプログラムは終了するものとする。
さて、任意の正の整数aに対し、添字T(x)+aにヘッダを移動するのには最低でも時間T(x)+aだけ掛かるから
時刻T(x)の時点で添字T(x)+a上の値を読み取ることは不可能である。
よって、任意の有限長入力列xに対し、ある値T(x)が存在し、位置T(x)より右側は無効である。
この議論が問題ないとするならば、系として
どのような有限長入力列を用意したとしても、それがプログラムを必ず有限時間内に停止させるのであれば、
オラクルテープ上の有限個の要素しか扱う事は出来ない。
つまり、オラクルテープ上の要素数は本質的に有限個である。
という事が言えると思うのだけど。
上限がない入力に対応するために無限のオラクルテープが必要になるの
長さに上限がない入力に対応するために、非常に長いオラクルテープが必要になりうる
じゃない？
一定時間あたり有限個の要素しか扱うことができず、
有限時間で停止するならば
停止するまでに有限個の要素しか扱うことが出来ない
というだけの、掛け算レベルの話なんだけど。
すべての入力に対して無限のオラクルテープが必要になることは矛盾しない。
何故なら、計算開始時点でオラクルヘッドは常に左端にあって
任意の正の整数iに対し、オラクルヘッドを添字iに移動するのに最低でもiステップ掛かり
そしてどんな入力を与えても有限時間で動作を停止するから。
入力記号の集合Γの要素数は有限だよね？
お前の言ってるのは通常のチューリングマシンのテープ長も有限でいいって言ってるようなもんだぞ。
もしも、任意の入力に対して常に停止するプログラムだって事が保証されてるなら
通常のチューリングマシンのテープ長も有限で良い。
もしプログラムが停止しないような入力が存在するなら、
その時に限り、無限長のテープが必要になる。
>>37は
オラクルテープの長さが無限であろうが、
入力長が無限であろうが、
有限時間で止まらなかろうが、正しく動くんだけど
これは常に停止するな？
テープ長が有限でいいならこのプログラムに対してどれだけのテープがあればいいのだ？
俺は
全ての入力列xに対し、ある有限の整数Nが存在し、プログラムは高々N個の要素を使用する
って言ってるのに対し、君は多分
ある有限の整数Nが存在し、全ての入力列xに対し、プログラムは高々N個の要素を使用する
と受け取ってるんじゃないかな。
後者は明らかに偽だ。
定数個しか使わないということは、
チューリングマシンどころか有限状態オートマトンでも計算できるという事になる。
どの言語を判定するかという話をするとき、マシンの構成というのは入力によって構成を変えたりしないのだ。
お前がチューリングマシンのテープが有限でいいとか抜かすのは
入力によってマシンの構成（使えるテープの長さ）を無意識のうちにこっそり変えているのだ。
マシンの構成を入力によって変えてはいけないということが了承できるなら、
チューリングマシンのテープ長が可算無限必要なことも了承できるはずだ。
よくわからなくなってきたｗｗ
どっちにしろテープが有限てことはあり得ないが。
まさに入力長に対してテープ長を変化させるシステムなんだが。
あと、>>57に書いてあるけど、
>>37はそのオラクルテープとやらが無限長だろうがなんだろうが問題なく動くぞ？
オラクルテープは可算無限長だから通常のチューリングマシンでは>>37の
「4*i+3番地はオラクルテープ上の添字iのデータで初期化する。」
てのは無理なの。
>>37の議論はオラクルテープの存在を認めており、
オラクルテープと通常のテープを一本にまとめてヘッドを一つに出来るという議論であって
通常のチューリングマシンでオラクルテープをエミュレートできるという議論ではない。
本質はオラクルテープがあるかないかだから。
そこんとこ間違えないで。
テープ上に「情報」を乗っけることとは全く関係ないんよ？
じゃあ、オラクルテープのない通常のチューリングマシンでどうやって
「4*i+3番地はオラクルテープ上の添字iのデータで初期化する。」
を実現するんだよ。
オラクルテープの内容は所与なんだろ？
したらば、テープ1を使うチューリングマシン1の他に、
テープ1とオラクルテープを使うチューリングマシン2を使って
並列計算すれば良い。
オラクルテープを使うチューリングマシン2を使ってってなんだよ？
オラクルテープ使うんじゃん。
そうじゃなくてオラクルテープなしでオラクルテープをエミュレートしろっつってんの。
オラクルテープの内容は所与だよね？
オラクルテープの内容の扱いは状態遷移表の内容の扱いに近い。
通常テープの入力の扱いとはまったく違う。
これでも平日は朝６時に起きなきゃならん。
そのテープの内容は、勿論テープを媒体として与えられているとここでは仮定して、
>>70は「オラクルテープ」と言う名のテープからテープ1へ転写してる。
行ける行ける
3時間寝れれば余裕
そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
オラクルテープは可算無限ビットの情報を所与に出来る。
だから拡張チューリングマシンは通常のチューリングマシンと本質的に異なる。
違う。
そのオラクルテープの「内容」が所与なんだから
その内容がテープ上に記述された状態で計算を開始するものとすれば
可算無限長の情報を所与とする事は出来る。
1936年の論文の236ページに、可算無限個の情報による初期化の例が載ってる。
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
拡張チューリングマシンで計算できて普通のチューリングマシンで計算出来ないようなプログラムを
オラクルテープの内容の計算方法含めて書いてみてくれない？
チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
オラクルテープにH(x)を書き込んで置き、入力でxが与えられたら
オラクルテープのx番地を読み込んで1なら受理、0なら拒否する。
こうすることでチューリングマシンの停止問題を判定する拡張チューリングマシンが構成できる。
もちろん我々は具体的にこのオラクルテープを構成することは不可能だろう。
しかしチューリングマシンの停止問題を判定する拡張チューリングマシンは確かに存在するのである。
マイナー分野だしでかい本屋で探しても見つかるかどうか…
どうやってH(x)を計算するの？
H(x)を計算できる前提で拡張チューリングマシンが存在するのなら
Aならば(=>)BでいうところのAが偽なのでBはなんでも言えるんだがw
例えばH(x)が計算できるならば1+1=3であるも真になるぞ
しかし拡張チューリングマシンは存在する。
そういうことだ。
> チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
・プログラムの個数は非可算無限個。辞書順に並べることは出来ないし、「x番目」という言い方も出来ない。
・マシンへの入力を考慮していない。
・問題解決の前提知識として、その問題の答えを要求している; 拡張チューリングマシンが存在する為には、拡張チューリングマシンが必要である。
どう回避する？
二点目:
Nビットで表現できる全てのプログラム・入力対について判定する問題に置き換える。
つまり、プログラムは有限個であり、辞書順に並べることが出来る。
又、そのプログラム・入力対が有限時間で停止するかどうかは、つまりH(x)の値は既知であると仮定する。
この時、プログラムxが停止するかどうかを判定する>>80による拡張チューリングマシン上のプログラムの
時間計算量はO(2^N)である。
ところで、例えば世界最小のインタプリタは98バイト、そのインタプリタが停止しない最小の入力は3バイトなのでN=808について考えると、
拡張チューリングマシンが1秒間に10^100ステップ計算出来たとしても、終了までに平均2.7*10^135年掛かる。
もう少し現実的なプログラムは無いの？
は？
今問題にしているのは通常のチューリングマシンの停止問題であって
拡張チューリングマシンの停止問題ではないぞ？
>問題解決の前提知識として、その問題の答えを要求している
もちろんそうだが。
そういう見方をすれば確かにこれはつまらない。
しかし真に興味深いのは２つのオラクルテープの関係を調べることなのである。
一方のオラクルテープは他方のオラクルテープより真に強力、ということがあり得る。
そのような関係が美しい数学的構造を成すのである。
>もう少し現実的なプログラムは無いの？
お前のような知識のあるやつがこんなセコイ因縁を吹っかけてくるとは失望したぞ。
もちろんそうだが、じゃねぇよ。
三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
ついでで悪いんだけど、
プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？
俺には非可算無限個にしか思えないんだ。
うん？
チューリングマシンが可算個、入力が可算個で可算の直積集合になると思ったがなにか勘違いしてるだろうか？
>三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
意味わからんどんな例えだ。
(えーと、状態集合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
計算不能なテープをどうやって用意するの？
すまん、知らん。
>計算不能なテープをどうやって用意するの？
実際に用意はできないがあると仮定して推論を進めるのである。
張り付くの自重せねばｗ
P≠NPを仮定すれば現代の暗号は安全だっていうのも同じだね。
一方で、君は計算することが出来ないという事が証明されている数が所与であるという
無茶苦茶な仮定を置いてる。
特技：イオナズンとか言っちゃう厨二病患者と似たり寄ったり。
暫くこのスレはお休みかな。
通常のチューリングマシンの停止問題を解けるオラクルテープをもつ拡張チューリングマシンの停止問題を解けるオラクルテープは
通常のチューリングマシンの停止問題を解けるオラクルテープよりさらに強力だとか、そんな感じのネタを仕入れたい。
結局テープにH(x)とかを書き込むんでしょ？
それともオラクルテープの内容が違うだけで別クラスの拡張チューリングマシンになるのだろうか
FSMでは何が計算できて、何が計算出来ないのか。それは何故か。
PDAやLBAだとどうだろうか。
100〜のスレッドの続きを読む