すべての言語を判定する計算機構

1 ：デフォルトの名無しさん：2016/05/18(水) 22:13:24.42 ID:PfJrFPe9.net

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

73 ：１：2016/05/23(月) 22:39:28.65 ID:Y87SDCLt.net

すまん、所与の意味が分からんｗ

オラクルテープの内容の扱いは状態遷移表の内容の扱いに近い。
通常テープの入力の扱いとはまったく違う。

74 ：１：2016/05/23(月) 22:41:28.49 ID:Y87SDCLt.net

すまん、そろそろ寝るわ。
これでも平日は朝６時に起きなきゃならん。

75 ：デフォルトの名無しさん：2016/05/23(月) 22:43:20.74 ID:bDXz1lkX.net

えーと、前提知識として与えられているものと仮定できるんだよね？っていう事
そのテープの内容は、勿論テープを媒体として与えられているとここでは仮定して、
>>70は「オラクルテープ」と言う名のテープからテープ1へ転写してる。

76 ：デフォルトの名無しさん：2016/05/23(月) 22:44:45.28 ID:bDXz1lkX.net

>>74
行ける行ける
3時間寝れれば余裕

77 ：１：2016/05/24(火) 05:42:54.17 ID:/CRqdm6R.net

そう、オラクルテープは前提の知識として与えられていると仮定できる。

そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
オラクルテープは可算無限ビットの情報を所与に出来る。

だから拡張チューリングマシンは通常のチューリングマシンと本質的に異なる。

78 ：デフォルトの名無しさん：2016/05/24(火) 09:40:53.38 ID:TtTF6uFS.net

> そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
違う。

そのオラクルテープの「内容」が所与なんだから
その内容がテープ上に記述された状態で計算を開始するものとすれば
可算無限長の情報を所与とする事は出来る。

1936年の論文の236ページに、可算無限個の情報による初期化の例が載ってる。
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

79 ：デフォルトの名無しさん：2016/05/24(火) 09:43:11.68 ID:TtTF6uFS.net

何でも良いから
拡張チューリングマシンで計算できて普通のチューリングマシンで計算出来ないようなプログラムを
オラクルテープの内容の計算方法含めて書いてみてくれない？

80 ：１：2016/05/24(火) 19:34:31.83 ID:/CRqdm6R.net

例えばチューリングマシンの停止問題。

チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。

オラクルテープにH(x)を書き込んで置き、入力でxが与えられたら
オラクルテープのx番地を読み込んで1なら受理、0なら拒否する。

こうすることでチューリングマシンの停止問題を判定する拡張チューリングマシンが構成できる。

もちろん我々は具体的にこのオラクルテープを構成することは不可能だろう。
しかしチューリングマシンの停止問題を判定する拡張チューリングマシンは確かに存在するのである。

81 ：１：2016/05/24(火) 19:37:55.90 ID:/CRqdm6R.net

やっぱ「所与」のところにすれ違いがあるのかな？

82 ：１：2016/05/24(火) 20:08:22.49 ID:/CRqdm6R.net

つか本屋行けてないわ。
マイナー分野だしでかい本屋で探しても見つかるかどうか…

83 ：デフォルトの名無しさん：2016/05/24(火) 20:24:31.67 ID:kp/L/pO1.net

>>80
どうやってH(x)を計算するの？

H(x)を計算できる前提で拡張チューリングマシンが存在するのなら
Aならば(=>)BでいうところのAが偽なのでBはなんでも言えるんだがw
例えばH(x)が計算できるならば1+1=3であるも真になるぞ

84 ：１：2016/05/24(火) 20:35:45.53 ID:/CRqdm6R.net

具体的にH(x)は「計算」では求められない。
しかし拡張チューリングマシンは存在する。

そういうことだ。

85 ：デフォルトの名無しさん：2016/05/24(火) 20:39:04.50 ID:TtTF6uFS.net

一点目:
> チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
・プログラムの個数は非可算無限個。辞書順に並べることは出来ないし、「x番目」という言い方も出来ない。
・マシンへの入力を考慮していない。
・問題解決の前提知識として、その問題の答えを要求している; 拡張チューリングマシンが存在する為には、拡張チューリングマシンが必要である。
どう回避する？

二点目:
Nビットで表現できる全てのプログラム・入力対について判定する問題に置き換える。
つまり、プログラムは有限個であり、辞書順に並べることが出来る。
又、そのプログラム・入力対が有限時間で停止するかどうかは、つまりH(x)の値は既知であると仮定する。
この時、プログラムxが停止するかどうかを判定する>>80による拡張チューリングマシン上のプログラムの
時間計算量はO(2^N)である。
ところで、例えば世界最小のインタプリタは98バイト、そのインタプリタが停止しない最小の入力は3バイトなのでN=808について考えると、
拡張チューリングマシンが1秒間に10^100ステップ計算出来たとしても、終了までに平均2.7*10^135年掛かる。
もう少し現実的なプログラムは無いの？

86 ：１：2016/05/24(火) 20:51:20.79 ID:/CRqdm6R.net

>プログラムの個数は非可算無限個。
は？
今問題にしているのは通常のチューリングマシンの停止問題であって
拡張チューリングマシンの停止問題ではないぞ？

>問題解決の前提知識として、その問題の答えを要求している
もちろんそうだが。
そういう見方をすれば確かにこれはつまらない。

しかし真に興味深いのは２つのオラクルテープの関係を調べることなのである。
一方のオラクルテープは他方のオラクルテープより真に強力、ということがあり得る。
そのような関係が美しい数学的構造を成すのである。

>もう少し現実的なプログラムは無いの？
お前のような知識のあるやつがこんなセコイ因縁を吹っかけてくるとは失望したぞ。

87 ：デフォルトの名無しさん：2016/05/24(火) 20:59:57.89 ID:TtTF6uFS.net

>>86
もちろんそうだが、じゃねぇよ。
三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。

ついでで悪いんだけど、
プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？
俺には非可算無限個にしか思えないんだ。

88 ：１：2016/05/24(火) 21:18:34.79 ID:/CRqdm6R.net

>プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？

うん？
チューリングマシンが可算個、入力が可算個で可算の直積集合になると思ったがなにか勘違いしてるだろうか？

>三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
意味わからんどんな例えだ。

89 ：デフォルトの名無しさん：2016/05/24(火) 21:54:01.44 ID:TtTF6uFS.net

ごめんよ、よーく考えたらプログラムは高々可算無限個だったわ。
(えーと、状態集合Qの大きさをq、入力集合Γの大きさをγとすると、O(q^γ)パターン存在する。
とすると、状態の集合Qの大きさがqであるようなチューリングマシンはO(q^γ x log q)ビットの情報と等価に変換できる。
んでもって、qとγは有限の値を取るからー)
実数の濃度みたいに対角線論法で非可算個になる気がしてた。

喩えについてはユークリッド幾何学の第五公理に関する歴史と論争について知ってれば分かるかと
https://ja.wikipedia.org/wiki/%E5%B9%B3%E8%A1%8C%E7%B7%9A%E5%85%AC%E6%BA%96

90 ：デフォルトの名無しさん：2016/05/24(火) 21:56:05.64 ID:TtTF6uFS.net

本題に戻るけど
計算不能なテープをどうやって用意するの？

91 ：１：2016/05/24(火) 22:01:34.74 ID:/CRqdm6R.net

>喩えについてはユークリッド幾何学の第五公理に関する歴史と論争について知ってれば分かるかと

すまん、知らん。

>計算不能なテープをどうやって用意するの？

実際に用意はできないがあると仮定して推論を進めるのである。

92 ：１：2016/05/24(火) 22:03:42.61 ID:/CRqdm6R.net

思わず議論が白熱して張り付いてしまったがこれはいかんなｗ
張り付くの自重せねばｗ

93 ：デフォルトの名無しさん：2016/05/25(水) 08:23:37.20 ID:60iV75hD.net

仮定して推論を進めるのが有効なのは背理法の時だけかと

94 ：１：2016/05/25(水) 19:42:41.27 ID:5+8zav7P.net

詳しくはしらんがリーマン予想が真ならば〜と仮定して推論を進めた論文が結構あるそうだぞ。

95 ：デフォルトの名無しさん：2016/05/25(水) 20:52:42.77 ID:8+OpaV01.net

それは、証明はされていないけど正しいと思われているから。
P≠NPを仮定すれば現代の暗号は安全だっていうのも同じだね。

一方で、君は計算することが出来ないという事が証明されている数が所与であるという
無茶苦茶な仮定を置いてる。
特技：イオナズンとか言っちゃう厨二病患者と似たり寄ったり。

96 ：１：2016/05/25(水) 22:18:03.18 ID:5+8zav7P.net

読んでないが>>78の論文とやらが計算することが出来ない状態を所与にした論文とちゃうの？

97 ：１：2016/05/27(金) 20:25:50.00 ID:wEIQ/dS/.net

持ちネタも尽きたし新しいネタを仕入れないとな。
暫くこのスレはお休みかな。

98 ：１：2016/05/27(金) 22:50:36.91 ID:wEIQ/dS/.net

チューリングマシンの停止問題を解けるオラクルテープを使うとビジービーバー関数が計算出来きるとか
通常のチューリングマシンの停止問題を解けるオラクルテープをもつ拡張チューリングマシンの停止問題を解けるオラクルテープは
通常のチューリングマシンの停止問題を解けるオラクルテープよりさらに強力だとか、そんな感じのネタを仕入れたい。

99 ：デフォルトの名無しさん：2016/05/27(金) 23:15:01.55 ID:A2TIou2n.net

テープ自体に差はないんじゃないのかな。
結局テープにH(x)とかを書き込むんでしょ？

それともオラクルテープの内容が違うだけで別クラスの拡張チューリングマシンになるのだろうか

100 ：デフォルトの名無しさん：2016/05/30(月) 11:26:36.69 ID:9f9My9NT.net

もっと下位のオートマトンをより上位に拡張する方法を一般化したほうが早いんじゃないかな
FSMでは何が計算できて、何が計算出来ないのか。それは何故か。
PDAやLBAだとどうだろうか。

101 ：デフォルトの名無しさん：2016/05/30(月) 14:10:13.66 ID:j9NktVXe.net

FSM＝正規表現
PDA＝文脈自由文法

終了

102 ：デフォルトの名無しさん：2016/05/31(火) 16:36:27.31 ID:JlIYRfhe.net

チューリングマシンの停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシン…
と可算無限回繰り返した時のオラクルテープの内容は如何なるものか。

103 ：デフォルトの名無しさん：2016/06/01(水) 14:20:53.02 ID:z/VHQJBB.net

チューリングマシンの停止問題を解けるオラクルテープを持つ拡張チューリングマシン
の停止問題を解けるオラクルテープを持つ拡張チューリングマシンは
チューリングマシンの停止問題を解けるや否や？

104 ：デフォルトの名無しさん：2016/06/01(水) 20:57:13.79 ID:vZYp5pY7.net

>>103
>>20を信じるなら解ける

105 ：デフォルトの名無しさん：2016/06/01(水) 23:07:06.59 ID:KWV9l2rU.net

HALT(TM, x)が解ければAccept(TM, x)もとけるので

入力x∈Σ^*を受け取って∃y∈Σ^*.Accept(y,x)を返す拡張チューリングマシンMを考えた時
その言語L(M)は「あるチューリングマシンM'(=y)によって判定されうる言語」の集合なはず

106 ：デフォルトの名無しさん：2016/06/01(水) 23:30:03.64 ID:KWV9l2rU.net

よく考えたらAccept(y, x)とかいちいち構築しなくても
オラクルテープあるんだから「i番目の入力xはあるTMによって判定されるか」を0、1で書き込んでおけば一発だね
オラクルテープ万能すぎじゃないかい？

107 ：デフォルトの名無しさん：2016/06/01(水) 23:39:12.08 ID:vZYp5pY7.net

>>106
もともとそういう定義のものだからな。
オラクルテープを自由に書き換えるんじゃなくて、
オラクルテープを固定して遷移関数だけ変えることを考えると、
色々面白い議論も出てくる、はず。

108 ：１：2016/06/08(水) 21:22:28.95 ID:wtOBkV3F.net

エミール・ポストのwikiに

停止性問題よりもチューリング次数が低い計算不可能な帰納的可算集合が存在するかという問題を提起した。
これは1950年代に肯定的に解決

てのがあるんだけどだれか詳しいこと知らない？

109 ：72：2016/06/08(水) 22:20:21.00 ID:butypxOf.net

>>108
ttps://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_and_the_priority_method?wprov=sfla1

110 ：デフォルトの名無しさん：2016/06/08(水) 22:36:44.92 ID:wtOBkV3F.net

うお英語か
まあ、サンクス

111 ：1：2016/06/09(木) 21:16:57.10 ID:EAGKuhJB.net

チューリング次数について書かれた良和書が欲しい。
英語分からん。

112 ：72：2016/06/10(金) 10:05:10.25 ID:T7AOwkcm.net

>>111
ttps://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%AC%A1%E6%95%B0

113 ：1：2016/06/10(金) 22:37:47.93 ID:nrwEVc+r.net

>>112
日本語でもわからんかったｗ
とりあえず優先度法というのが気になる。

114 ：1：2016/06/14(火) 22:12:58.58 ID:Jl6Qd2UZ.net

NP問題周辺の話題に多項式階層というのがあるが
チューリング次数と何か繋がっているのだろうか

115 ：72：2016/06/14(火) 23:59:34.81 ID:ytAJecFL.net

>>114
ttps://ja.wikipedia.org/wiki/%E5%A4%9A%E9%A0%85%E5%BC%8F%E9%9A%8E%E5%B1%A4

116 ：デフォルトの名無しさん：2016/06/15(水) 00:11:45.70 ID:SLYlY5zm.net

wikipediaで会話するスレ

117 ：デフォルトの名無しさん：2016/06/18(土) 11:06:26.47 ID:rl9oH78Rh

オラクルオラクル言ってるってことは
ようは神託機械を実装してみようって言ってんの？

118 ：デフォルトの名無しさん：2016/06/24(金) 06:39:10.08 ID:gjcXKDKa.net

お前らって本当に浅い知識で語りたがるよな

119 ：デフォルトの名無しさん：2016/06/24(金) 20:12:27.64 ID:SgoRQ7d3.net

>>118
お前の深い知識を披露してくれてもいいんだぜ？

120 ：1：2016/07/08(金) 23:23:02.66 ID:g+JJCT55.net

巨大数探索スレ
http://wc2014.2ch.net/test/read.cgi/math/1448211924/

の497に面白そうなのがあった。

http://projecteuclid.org/euclid.pl/1235415519#info

でも英語か〜

121 ：デフォルトの名無しさん：2018/05/23(水) 22:38:15.50 ID:Au5e7VGg.net

僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

5E8RY

122 ：デフォルトの名無しさん：2018/07/04(水) 23:28:44.34 ID:gFgZc5FG.net

SQ1