すべての言語を判定する計算機構 [無断転載禁止]©2ch.net

**デフォルトの名無しさん** · 2016/05/18(水) 22:13:24.42

チューリングマシンは可算個しかないからすべての言語は判定できないという。
じゃあチューリングマシンを拡張して濃度を増やせばいいんじゃね？
そのような拡張を考えたときどのようなものが出来上がるか？あるいは無意味なのか？
そんなことを考えるスレ。

**デフォルトの名無しさん** · 2016/05/18(水) 22:28:06.75

<　｀∀´>ﾆﾀﾞｰ

**デフォルトの名無しさん** · 2016/05/18(水) 22:40:02.24

言語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')を常に作り上げることができる
つまりすべての言語を判定できるチューリングマシンは存在しない

証明終わり

**デフォルトの名無しさん** · 2016/05/18(水) 22:55:46.59

>この時Mは有限個なので

なんで有限個なの？今考えている拡張は有限とかいう縛りは考えてないぞ。

**デフォルトの名無しさん** · 2016/05/18(水) 23:05:29.06

別に有限じゃなくても大丈夫だよ。有限だと言語Lがdecidableなのは自明というだけのこと
とにかく判定対象の言語Lはdecidableだというのが肝
すると結局LのEnumerator EとLを判定するマシンMで同じことができる

**デフォルトの名無しさん** · 2016/05/18(水) 23:10:10.83

>すべてのアルファベットの組み合わせにおけるj番目=xを計算する

ここもダウト。
今考えてる拡張はアルファベットを基にしたものとは限らない。
例えば実数を扱えるようにするとか。

**デフォルトの名無しさん** · 2016/05/18(水) 23:14:19.64

マシンは拡張するけど言語は拡張しないからね？言っとくけど。

**デフォルトの名無しさん** · 2016/05/18(水) 23:33:18.24

実数だって一緒だよ。{0-9.+-}というアルファベットの組み合わせなんだから
実数自体はuncountableなのが問題だけど
実数を扱えるチューリングマシンを”仮定”するならEnumeratorは作れる

ところでEnumeratorって日本語だとなんていうの？列挙？

**デフォルトの名無しさん** · 2016/05/18(水) 23:44:30.22

可算の動きしか通常仮定しないチューリングマシンにおいて実数を取り扱うって自体
話を無理矢理な方向にもって行き過ぎ。
uncountable なのは本質なのに。

１ · 2016/05/19(木) 00:02:12.29

だからチューリングマシンを拡張して濃度を増やすっつってんだろ。
濃度が増えなきゃ意味ない。
もう寝る。

１ · 2016/05/19(木) 20:22:06.73

今のところ通常のチューリングマシンにオラクル・ストリングという名前の実数を一つ書き込めるテープを追加したものを考えている。
このオラクル・ストリングに例えばチャイティンのΩのような実数を書き込めばチューリングマシンの停止問題を判定する
拡張チューリングマシンが構成できるだろう。

オラクル・ストリングに任意の実数を書き込めるなら任意の言語を判定する拡張チューリングマシンが構成できると思う。

まあ、これはほとんどトートロジーだよね。

１ · 2016/05/19(木) 20:24:49.45

オラクル・ストリングに書き込む実数のパワーによって拡張チューリングマシンのパワーも変わってくると思う。
じゃあ、最強のオラクル・ストリングは存在するのか？しないのか？とかそんなことを考えている。

１ · 2016/05/19(木) 23:00:19.98

うん？
最強のオラクル・ストリングはまさに>>3の議論によって存在しないのか？
よくわからなくなってきたｗ

１ · 2016/05/20(金) 20:56:35.88

拡張チューリングマシンが判定する言語に対して文字列を辞書順に並べ
言語に含まれるなら１含まれないなら０という風に数値を並べ実数を構成する。
ある実数aをオラクル・ストリングにもつ拡張チューリングマシンから生成できる実数の集合をL(a)とする。

Not(a∈L(b)) And Not(b∈(L(a))を満たすような実数の組(a,b)は存在するか？

１ · 2016/05/20(金) 21:00:17.50

辞書順だとちょっとまずいかな。
まず文字列の長さでならべてそれぞれの長さに対して辞書順でならべたほうがいいかな。

1 · 2016/05/20(金) 21:09:01.15

すべてのa∈Rに対してNot(b∈L(a))となるb∈Rが存在する。
濃度より明らか
ゆえに最強のオラクル・ストリングは存在しない。

１ · 2016/05/20(金) 21:11:28.28

>>14も濃度から存在が言えるかな？
よくわからん。

**デフォルトの名無しさん** · 2016/05/20(金) 22:12:42.14

ん？
>>16って正しい？
自信なくなってきたｗｗｗ

１ · 2016/05/20(金) 22:32:07.92

なんだよレスがまったくねーな。
誰かツッコミ頼む。

１ · 2016/05/21(土) 08:44:04.11

(a∈L(b))=>(L(a)⊂L(b))
かな

**デフォルトの名無しさん** · 2016/05/21(土) 09:47:18.67

既存のチューリングマシンが全ての言語を認識できないなんて誰でも知ってるんだから
拡張して濃度を上げるってんならその拡張をどうやるかについて最初に話すべきじゃない？

１ · 2016/05/21(土) 13:50:35.11

>>21
俺よりいいアイディア持ってるやつがひょっとしたらいるかと思ってな。
遅まきながら俺のアイディアは>>11で示した。

**デフォルトの名無しさん** · 2016/05/21(土) 14:34:44.04

任意の実数aに対してa∈L(a)
まあ当たり前かな。

１ · 2016/05/21(土) 16:17:11.21

L(a)=L(b)というaとbの同値関係によって実数を同値類に分類したらなにか出てくるかな？

１ · 2016/05/21(土) 18:44:10.86

キーワードはこの辺やな

相対計算可能性
チューリング次数
チューリング還元可能

**デフォルトの名無しさん** · 2016/05/21(土) 20:23:20.06

学校の宿題かなんか？

1 · 2016/05/21(土) 20:31:47.22

>>26
ただの趣味。

１ · 2016/05/21(土) 22:03:00.11

ネットだといまいち、いい情報が見つからないな。
本でも買うか…

21 · 2016/05/22(日) 14:04:16.69

>>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は高々可算無限長の配列とする。

**デフォルトの名無しさん** · 2016/05/22(日) 14:27:36.48

(>>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)に含まれる値の個数は加算無限個である。

**デフォルトの名無しさん** · 2016/05/22(日) 14:28:30.10

(>>30の続き)
よって、以下の定理が成り立つ

定理4
この方法により拡張されたチューリングマシンの計算能力は、
元のチューリングマシンと等価である。

証明4
高々加算無限回の演算によってテープに出力可能な値の集合の濃度がN0に等しい事から、
それらの値を適切に符号化する事によって
元のチューリングマシンで高々可算無限回の演算をエミュレート出来る為自明。

１ · 2016/05/22(日) 17:04:22.07

よくわからんが拡張の仕方がまずいと元のチューリングマシンと能力変わんないのはあり得る話だと思う。
>>21って>>11のと違うやつだよね？
>>21だと濃度も増えてないっしょ？多分。
よければ>>11のも形式的に書いてくれんか？

１ · 2016/05/22(日) 17:05:44.25

>>21じゃなくて>>29か

**デフォルトの名無しさん** · 2016/05/22(日) 17:23:55.91

いや、>>11を適当にエスパーしたのが>>29なんだけど、
その結果得られた拡張だと上手く行かないよって事を言った。

>>11をもうちょっと分かりやすく書きなおしてくれない？
もしかしたら俺が勘違いして>>1が意図したのとは違う拡張をしてるかも知れんから。

１ · 2016/05/22(日) 18:02:18.28

上手く定義できてるか不安だが以下のような感じかな。

拡張チューリングマシンは以下の要素からなる

１．状態の集合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になればその入力を拒否する。

オラクルテープの存在によって拡張チューリングマシンの濃度は可算を超える。

**デフォルトの名無しさん** · 2016/05/22(日) 19:05:01.51

うーん
Γが有限集合であると仮定すると、
それは単にテープが2つあるチューリングマシンって事になると思うんだけど
テープが2つあるチューリングマシンはテープ1つのチューリングマシンと等価。

**デフォルトの名無しさん** · 2016/05/22(日) 19:09:29.82

次のようにすればテープ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回右へ移動し、もう一度この行を実行する
定義修了

**デフォルトの名無しさん** · 2016/05/22(日) 19:11:25.22

sage忘れスマソ

s/修了/終了/
あと、S1での「現在の値」は現在のテープヘッドから読み込んだ時の値って読み替えて。

１ · 2016/05/22(日) 19:33:59.13

テープ二本のチューリングマシンと違うのはオラクルテープに可算無限の情報をあらかじめ書き込めるってことかな。

**デフォルトの名無しさん** · 2016/05/22(日) 19:45:40.41

テープ2本のチューリングマシンも予め可算無限個の情報を書き込めるけど・・・・・・？

**デフォルトの名無しさん** · 2016/05/22(日) 19:51:09.25

ん？どゆこと？

**デフォルトの名無しさん** · 2016/05/22(日) 20:24:15.32

初期状態として、テープに可算無限個の列を与えることはよくある拡張だし
>>37はその拡張を踏まえてるって事。

例えば、チューリングマシンで足し算をするアルゴリズムは
初期状態として1進数で2つの数がテープに書かれていると仮定する場合が殆ど。

１ · 2016/05/22(日) 20:37:07.84

通常のチューリングマシンの入力は有限長でしょ？

**デフォルトの名無しさん** · 2016/05/22(日) 20:43:54.89

それは計算が有限ステップで終了することを前提にした場合の話だよね？
そもそもは無限長のテープを仮定するんだから、
可算無限個のデータ列がそのテープ上に記述されているとするのは自然な発想だと思うんだけど。

１ · 2016/05/22(日) 20:48:11.74

いや、>>35の拡張チューリングマシンは入力は有限長でさらに有限ステップで停止することを考えている。
オラクルテープの内容は入力ではなくてチューリングマシンの一部。
状態とかと似たようなもんかな？

**デフォルトの名無しさん** · 2016/05/22(日) 21:02:08.07

ちょっと待った。
「入力」は何を指してる？

俺は全てのテープ上に存在するデータの集合を指して「入力」って言ってるけど、
君はそうでないように思える。

オラクルテープの内容が計算開始時点で所与であると仮定するならば、
テープとヘッダをもう一組追加するのと何ら変わりはない。
複数のテープがある時に、遷移前にテープへデータを書き込まないようなヘッダの存在を許す拡張は至って普通。

ついでに言うと、通常テープに対する任意の入力列xに対してそのプログラムが有限時間で停止すると仮定するならば、
その停止時刻をT(x)とした時に、オラクルテープの添字T(x)の右側は無視できる。
何故ならそこまでヘッダを動かすのに最低でもT(x)時間掛かるから。
とするならば、オラクルテープが可算無限長であろうが有限長であろうが同じ議論が成り立つと思うのだけど。

１ · 2016/05/22(日) 21:10:50.52

入力は計算開始時に通常テープに書かれてるものだけを指している。

>その停止時刻をT(x)とした時に、オラクルテープの添字T(x)の右側は無視できる。

これはそうはならない。
なぜなら停止時刻は入力によって左右されるものだから。
入力が大きくなれば停止時刻も大きくなり、
結果、オラクルテープが可算無限長もつのは本質的である。

**デフォルトの名無しさん** · 2016/05/22(日) 21:25:37.88

>>47
ふぅむ

> なぜなら停止時刻は入力によって左右されるものだから。
その入力によって左右される値を関数形でT(x)と書いたのだけど・・・・・・

今、有限長入力列xが与えられたとしよう。
但し、有限時間T(x)でプログラムは終了するものとする。
さて、任意の正の整数aに対し、添字T(x)+aにヘッダを移動するのには最低でも時間T(x)+aだけ掛かるから
時刻T(x)の時点で添字T(x)+a上の値を読み取ることは不可能である。
よって、任意の有限長入力列xに対し、ある値T(x)が存在し、位置T(x)より右側は無効である。

この議論が問題ないとするならば、系として
どのような有限長入力列を用意したとしても、それがプログラムを必ず有限時間内に停止させるのであれば、
オラクルテープ上の有限個の要素しか扱う事は出来ない。
つまり、オラクルテープ上の要素数は本質的に有限個である。
という事が言えると思うのだけど。

１ · 2016/05/22(日) 21:34:04.14

入力が有限であっても上限はないでしょ？
上限がない入力に対応するために無限のオラクルテープが必要になるの

**デフォルトの名無しさん** · 2016/05/22(日) 21:38:47.60

それは正確には
長さに上限がない入力に対応するために、非常に長いオラクルテープが必要になりうる
じゃない？

一定時間あたり有限個の要素しか扱うことができず、
有限時間で停止するならば
停止するまでに有限個の要素しか扱うことが出来ない
というだけの、掛け算レベルの話なんだけど。

１ · 2016/05/22(日) 21:38:50.31

一つの入力に対しオラクルテープの有限部分しか使わないことと、
すべての入力に対して無限のオラクルテープが必要になることは矛盾しない。

**デフォルトの名無しさん** · 2016/05/22(日) 21:39:57.18

チューリングマシンの入力の濃度はいくつよ？

**デフォルトの名無しさん** · 2016/05/22(日) 21:43:22.91

いや、それは矛盾する。
何故なら、計算開始時点でオラクルヘッドは常に左端にあって
任意の正の整数iに対し、オラクルヘッドを添字iに移動するのに最低でもiステップ掛かり
そしてどんな入力を与えても有限時間で動作を停止するから。

**デフォルトの名無しさん** · 2016/05/22(日) 21:46:12.46

>>52
入力記号の集合Γの要素数は有限だよね？

１ · 2016/05/22(日) 21:49:21.98

だから入力一つにたいして有限ステップなのは認めるよ。
お前の言ってるのは通常のチューリングマシンのテープ長も有限でいいって言ってるようなもんだぞ。

**デフォルトの名無しさん** · 2016/05/22(日) 21:51:51.99

>>55
もしも、任意の入力に対して常に停止するプログラムだって事が保証されてるなら
通常のチューリングマシンのテープ長も有限で良い。

もしプログラムが停止しないような入力が存在するなら、
その時に限り、無限長のテープが必要になる。

**デフォルトの名無しさん** · 2016/05/22(日) 21:58:41.49

ところでー
>>37は
オラクルテープの長さが無限であろうが、
入力長が無限であろうが、
有限時間で止まらなかろうが、正しく動くんだけど

１ · 2016/05/22(日) 22:05:17.87

じゃあ入力に対してそれを２倍にするプログラムを考えよう。
これは常に停止するな？
テープ長が有限でいいならこのプログラムに対してどれだけのテープがあればいいのだ？

**デフォルトの名無しさん** · 2016/05/22(日) 22:06:23.77

入力の倍の長さのテープがあれば良い。

１ · 2016/05/22(日) 22:07:02.07

すまん、今日は落ちる。ノシ

**デフォルトの名無しさん** · 2016/05/22(日) 22:07:33.27

おやすみ

**デフォルトの名無しさん** · 2016/05/22(日) 22:13:55.66

うーん

俺は
全ての入力列xに対し、ある有限の整数Nが存在し、プログラムは高々N個の要素を使用する
って言ってるのに対し、君は多分
ある有限の整数Nが存在し、全ての入力列xに対し、プログラムは高々N個の要素を使用する
と受け取ってるんじゃないかな。
後者は明らかに偽だ。

**デフォルトの名無しさん** · 2016/05/22(日) 22:25:18.51

というか後者が成り立つようならそれは有限個どころか定数個の要素しか使ってない。
定数個しか使わないということは、
チューリングマシンどころか有限状態オートマトンでも計算できるという事になる。

１ · 2016/05/23(月) 20:06:48.97

普通、あるマシン（有限オートマトン、プッシュダウンオートマトン、チューリングマシン問わず）が
どの言語を判定するかという話をするとき、マシンの構成というのは入力によって構成を変えたりしないのだ。
お前がチューリングマシンのテープが有限でいいとか抜かすのは
入力によってマシンの構成（使えるテープの長さ）を無意識のうちにこっそり変えているのだ。
マシンの構成を入力によって変えてはいけないということが了承できるなら、
チューリングマシンのテープ長が可算無限必要なことも了承できるはずだ。

１ · 2016/05/23(月) 21:31:55.99

と思ったけど多項式時間チューリングマシンとかあるんだっけｗ
よくわからなくなってきたｗｗ
どっちにしろテープが有限てことはあり得ないが。

**デフォルトの名無しさん** · 2016/05/23(月) 21:51:05.41

チューリングマシンの下位に当たる線形拘束オートマトンが
まさに入力長に対してテープ長を変化させるシステムなんだが。

あと、>>57に書いてあるけど、
>>37はそのオラクルテープとやらが無限長だろうがなんだろうが問題なく動くぞ？

１ · 2016/05/23(月) 22:10:54.62

だから通常のチューリングマシンの状態は有限じゃなきゃいけないの。
オラクルテープは可算無限長だから通常のチューリングマシンでは>>37の

「4*i+3番地はオラクルテープ上の添字iのデータで初期化する。」

てのは無理なの。

>>37の議論はオラクルテープの存在を認めており、
オラクルテープと通常のテープを一本にまとめてヘッドを一つに出来るという議論であって
通常のチューリングマシンでオラクルテープをエミュレートできるという議論ではない。

本質はオラクルテープがあるかないかだから。

そこんとこ間違えないで。

**デフォルトの名無しさん** · 2016/05/23(月) 22:12:58.66

「状態」が有限だっていうのは、状態集合Qが有限集合だって意味であって
テープ上に「情報」を乗っけることとは全く関係ないんよ？

１ · 2016/05/23(月) 22:22:39.86

>>37
じゃあ、オラクルテープのない通常のチューリングマシンでどうやって
「4*i+3番地はオラクルテープ上の添字iのデータで初期化する。」
を実現するんだよ。

**デフォルトの名無しさん** · 2016/05/23(月) 22:28:38.53

>>69
オラクルテープの内容は所与なんだろ？
したらば、テープ1を使うチューリングマシン1の他に、
テープ1とオラクルテープを使うチューリングマシン2を使って
並列計算すれば良い。