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