すべての言語を判定する計算機構 [無断転載禁止]©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)に含まれる値の個数は加算無限個である。