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

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

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

**デフォルトの名無しさん** · 2016/05/31(火) 16:36:27.31

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

**デフォルトの名無しさん** · 2016/06/01(水) 14:20:53.02

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

**デフォルトの名無しさん** · 2016/06/01(水) 20:57:13.79

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

**デフォルトの名無しさん** · 2016/06/01(水) 23:07:06.59

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

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

**デフォルトの名無しさん** · 2016/06/01(水) 23:30:03.64

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

**デフォルトの名無しさん** · 2016/06/01(水) 23:39:12.08

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

１ · 2016/06/08(水) 21:22:28.95

エミール・ポストのwikiに

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

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

72 · 2016/06/08(水) 22:20:21.00

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

**デフォルトの名無しさん** · 2016/06/08(水) 22:36:44.92

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

1 · 2016/06/09(木) 21:16:57.10

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

72 · 2016/06/10(金) 10:05:10.25

>>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

1 · 2016/06/10(金) 22:37:47.93

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

1 · 2016/06/14(火) 22:12:58.58

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

72 · 2016/06/14(火) 23:59:34.81

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

**デフォルトの名無しさん** · 2016/06/15(水) 00:11:45.70

wikipediaで会話するスレ

**デフォルトの名無しさん** · 2016/06/24(金) 06:39:10.08

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

**デフォルトの名無しさん** · 2016/06/24(金) 20:12:27.64

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

1 · 2016/07/08(金) 23:23:02.66

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

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

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

でも英語か～

**デフォルトの名無しさん** · 2018/05/23(水) 22:38:15.50

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

5E8RY

**デフォルトの名無しさん** · 2018/07/04(水) 23:28:44.34

SQ1