すべての言語を判定する計算機構 [無断転載禁止]©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

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