-
プログラム
-
すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
-
UPLIFTで広告なしで体験しましょう！快適な閲覧ライフをお約束します！
チューリングマシンは可算個しかないからすべての言語は判定できないという。
じゃあチューリングマシンを拡張して濃度を増やせばいいんじゃね？
そのような拡張を考えたときどのようなものが出来上がるか？あるいは無意味なのか？
そんなことを考えるスレ。 - コメントを投稿する
-
< ｀∀´>ﾆﾀﾞｰ
-
言語Lをdecider M(1..i)の集合とする
この時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')を常に作り上げることができる
つまりすべての言語を判定できるチューリングマシンは存在しない
証明終わり -
>この時Mは有限個なので
なんで有限個なの？今考えている拡張は有限とかいう縛りは考えてないぞ。 -
別に有限じゃなくても大丈夫だよ。有限だと言語Lがdecidableなのは自明というだけのこと
とにかく判定対象の言語Lはdecidableだというのが肝
すると結局LのEnumerator EとLを判定するマシンMで同じことができる -
>すべてのアルファベットの組み合わせにおけるj番目=xを計算する
ここもダウト。
今考えてる拡張はアルファベットを基にしたものとは限らない。
例えば実数を扱えるようにするとか。 -
マシンは拡張するけど言語は拡張しないからね？言っとくけど。
-
実数だって一緒だよ。{0-9.+-}というアルファベットの組み合わせなんだから
実数自体はuncountableなのが問題だけど
実数を扱えるチューリングマシンを”仮定”するならEnumeratorは作れる
ところでEnumeratorって日本語だとなんていうの？列挙？ -
可算の動きしか通常仮定しないチューリングマシンにおいて実数を取り扱うって自体
話を無理矢理な方向にもって行き過ぎ。
uncountable なのは本質なのに。 -
だからチューリングマシンを拡張して濃度を増やすっつってんだろ。
濃度が増えなきゃ意味ない。
もう寝る。 -
今のところ通常のチューリングマシンにオラクル・ストリングという名前の実数を一つ書き込めるテープを追加したものを考えている。
このオラクル・ストリングに例えばチャイティンのΩのような実数を書き込めばチューリングマシンの停止問題を判定する
拡張チューリングマシンが構成できるだろう。
オラクル・ストリングに任意の実数を書き込めるなら任意の言語を判定する拡張チューリングマシンが構成できると思う。
まあ、これはほとんどトートロジーだよね。 -
オラクル・ストリングに書き込む実数のパワーによって拡張チューリングマシンのパワーも変わってくると思う。
じゃあ、最強のオラクル・ストリングは存在するのか？しないのか？とかそんなことを考えている。 -
拡張チューリングマシンが判定する言語に対して文字列を辞書順に並べ
言語に含まれるなら１含まれないなら０という風に数値を並べ実数を構成する。
ある実数aをオラクル・ストリングにもつ拡張チューリングマシンから生成できる実数の集合をL(a)とする。
Not(a∈L(b)) And Not(b∈(L(a))を満たすような実数の組(a,b)は存在するか？ -
辞書順だとちょっとまずいかな。
まず文字列の長さでならべてそれぞれの長さに対して辞書順でならべたほうがいいかな。 -
すべてのa∈Rに対してNot(b∈L(a))となるb∈Rが存在する。
濃度より明らか
ゆえに最強のオラクル・ストリングは存在しない。 -
>>14も濃度から存在が言えるかな？
よくわからん。 -
なんだよレスがまったくねーな。
誰かツッコミ頼む。 -
(a∈L(b))=>(L(a)⊂L(b))
かな -
既存のチューリングマシンが全ての言語を認識できないなんて誰でも知ってるんだから
拡張して濃度を上げるってんならその拡張をどうやるかについて最初に話すべきじゃない？ -
任意の実数aに対してa∈L(a)
まあ当たり前かな。 -
L(a)=L(b)というaとbの同値関係によって実数を同値類に分類したらなにか出てくるかな？
-
キーワードはこの辺やな
相対計算可能性
チューリング次数
チューリング還元可能 -
学校の宿題かなんか？
-
>>26
ただの趣味。 -
ネットだといまいち、いい情報が見つからないな。
本でも買うか… -
>>1
形式的に書くと、こんな感じかな。
拡張したチューリングマシン = {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は高々可算無限長の配列とする。 -
(>>29の続き)
とすると
初期状態{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)に含まれる値の個数は加算無限個である。 -
(>>30の続き)
よって、以下の定理が成り立つ
定理4
この方法により拡張されたチューリングマシンの計算能力は、
元のチューリングマシンと等価である。
証明4
高々加算無限回の演算によってテープに出力可能な値の集合の濃度がN0に等しい事から、
それらの値を適切に符号化する事によって
元のチューリングマシンで高々可算無限回の演算をエミュレート出来る為自明。 -
上手く定義できてるか不安だが以下のような感じかな。
拡張チューリングマシンは以下の要素からなる
１．状態の集合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つのチューリングマシンと等価。 -
次のようにすればテープ1つのチューリングマシンでテープ2つのチューリングマシンをエミュレート出来る:
テープ上の記号の集合をΓ∪{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回右へ移動し、もう一度この行を実行する
定義修了 -
sage忘れスマソ
s/修了/終了/
あと、S1での「現在の値」は現在のテープヘッドから読み込んだ時の値って読み替えて。 -
テープ二本のチューリングマシンと違うのはオラクルテープに可算無限の情報をあらかじめ書き込めるってことかな。
-
テープ2本のチューリングマシンも予め可算無限個の情報を書き込めるけど・・・・・・？
-
ん？どゆこと？
-
初期状態として、テープに可算無限個の列を与えることはよくある拡張だし
>>37はその拡張を踏まえてるって事。
例えば、チューリングマシンで足し算をするアルゴリズムは
初期状態として1進数で2つの数がテープに書かれていると仮定する場合が殆ど。 -
通常のチューリングマシンの入力は有限長でしょ？
-
それは計算が有限ステップで終了することを前提にした場合の話だよね？
そもそもは無限長のテープを仮定するんだから、
可算無限個のデータ列がそのテープ上に記述されているとするのは自然な発想だと思うんだけど。 -
ちょっと待った。
「入力」は何を指してる？
俺は全てのテープ上に存在するデータの集合を指して「入力」って言ってるけど、
君はそうでないように思える。
オラクルテープの内容が計算開始時点で所与であると仮定するならば、
テープとヘッダをもう一組追加するのと何ら変わりはない。
複数のテープがある時に、遷移前にテープへデータを書き込まないようなヘッダの存在を許す拡張は至って普通。
ついでに言うと、通常テープに対する任意の入力列xに対してそのプログラムが有限時間で停止すると仮定するならば、
その停止時刻をT(x)とした時に、オラクルテープの添字T(x)の右側は無視できる。
何故ならそこまでヘッダを動かすのに最低でもT(x)時間掛かるから。
とするならば、オラクルテープが可算無限長であろうが有限長であろうが同じ議論が成り立つと思うのだけど。 -
入力は計算開始時に通常テープに書かれてるものだけを指している。
>その停止時刻をT(x)とした時に、オラクルテープの添字T(x)の右側は無視できる。
これはそうはならない。
なぜなら停止時刻は入力によって左右されるものだから。
入力が大きくなれば停止時刻も大きくなり、
結果、オラクルテープが可算無限長もつのは本質的である。 -
>>47
ふぅむ
> なぜなら停止時刻は入力によって左右されるものだから。
その入力によって左右される値を関数形で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ステップ掛かり
そしてどんな入力を与えても有限時間で動作を停止するから。 -
>>52
入力記号の集合Γの要素数は有限だよね？ -
だから入力一つにたいして有限ステップなのは認めるよ。
お前の言ってるのは通常のチューリングマシンのテープ長も有限でいいって言ってるようなもんだぞ。 -
>>55
もしも、任意の入力に対して常に停止するプログラムだって事が保証されてるなら
通常のチューリングマシンのテープ長も有限で良い。
もしプログラムが停止しないような入力が存在するなら、
その時に限り、無限長のテープが必要になる。 -
じゃあ入力に対してそれを２倍にするプログラムを考えよう。
これは常に停止するな？
テープ長が有限でいいならこのプログラムに対してどれだけのテープがあればいいのだ？ -
入力の倍の長さのテープがあれば良い。
-
すまん、今日は落ちる。ノシ
-
おやすみ
-
うーん
俺は
全ての入力列xに対し、ある有限の整数Nが存在し、プログラムは高々N個の要素を使用する
って言ってるのに対し、君は多分
ある有限の整数Nが存在し、全ての入力列xに対し、プログラムは高々N個の要素を使用する
と受け取ってるんじゃないかな。
後者は明らかに偽だ。 -
というか後者が成り立つようならそれは有限個どころか定数個の要素しか使ってない。
定数個しか使わないということは、
チューリングマシンどころか有限状態オートマトンでも計算できるという事になる。 -
普通、あるマシン（有限オートマトン、プッシュダウンオートマトン、チューリングマシン問わず）が
どの言語を判定するかという話をするとき、マシンの構成というのは入力によって構成を変えたりしないのだ。
お前がチューリングマシンのテープが有限でいいとか抜かすのは
入力によってマシンの構成（使えるテープの長さ）を無意識のうちにこっそり変えているのだ。
マシンの構成を入力によって変えてはいけないということが了承できるなら、
チューリングマシンのテープ長が可算無限必要なことも了承できるはずだ。 -
と思ったけど多項式時間チューリングマシンとかあるんだっけｗ
よくわからなくなってきたｗｗ
どっちにしろテープが有限てことはあり得ないが。 -
「状態」が有限だっていうのは、状態集合Qが有限集合だって意味であって
テープ上に「情報」を乗っけることとは全く関係ないんよ？ -
意味不明
オラクルテープを使うチューリングマシン2を使ってってなんだよ？
オラクルテープ使うんじゃん。
そうじゃなくてオラクルテープなしでオラクルテープをエミュレートしろっつってんの。 -
どういうこと？
オラクルテープの内容は所与だよね？ -
すまん、所与の意味が分からんｗ
オラクルテープの内容の扱いは状態遷移表の内容の扱いに近い。
通常テープの入力の扱いとはまったく違う。 -
すまん、そろそろ寝るわ。
これでも平日は朝６時に起きなきゃならん。 -
えーと、前提知識として与えられているものと仮定できるんだよね？っていう事
そのテープの内容は、勿論テープを媒体として与えられているとここでは仮定して、
>>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だとどうだろうか。
↑今すぐ読める無料コミック大量配信中！↑
