- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
77 ：１[sage]：2016/05/24(火) 05:42:54.17 ID:/CRqdm6R - そう、オラクルテープは前提の知識として与えられていると仮定できる。
そして、通常のチューリングマシンでは有限の情報しか所与にする手立てがなく、
オラクルテープは可算無限ビットの情報を所与に出来る。
だから拡張チューリングマシンは通常のチューリングマシンと本質的に異なる。
|
- スレを勃てるまでもないC/C++の質問はここで 24 [転載禁止]©2ch.net
794 ：デフォルトの名無しさん[sage]：2016/05/24(火) 19:24:21.51 ID:/CRqdm6R - そんなひどいｗ
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
80 ：１[sage]：2016/05/24(火) 19:34:31.83 ID:/CRqdm6R - 例えばチューリングマシンの停止問題。
チューリングマシンを辞書順に並べてx番目のマシンが停止するかどうかをH(x)とおく。
オラクルテープにH(x)を書き込んで置き、入力でxが与えられたら
オラクルテープのx番地を読み込んで1なら受理、0なら拒否する。
こうすることでチューリングマシンの停止問題を判定する拡張チューリングマシンが構成できる。
もちろん我々は具体的にこのオラクルテープを構成することは不可能だろう。
しかしチューリングマシンの停止問題を判定する拡張チューリングマシンは確かに存在するのである。
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
81 ：１[sage]：2016/05/24(火) 19:37:55.90 ID:/CRqdm6R - やっぱ「所与」のところにすれ違いがあるのかな？
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
82 ：１[sage]：2016/05/24(火) 20:08:22.49 ID:/CRqdm6R - つか本屋行けてないわ。
マイナー分野だしでかい本屋で探しても見つかるかどうか…
|
- スレを勃てるまでもないC/C++の質問はここで 24 [転載禁止]©2ch.net
795 ：デフォルトの名無しさん[sage]：2016/05/24(火) 20:11:53.37 ID:/CRqdm6R - 移植するとき発狂するぞｗ
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
84 ：１[sage]：2016/05/24(火) 20:35:45.53 ID:/CRqdm6R - 具体的にH(x)は「計算」では求められない。
しかし拡張チューリングマシンは存在する。
そういうことだ。
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
86 ：１[sage]：2016/05/24(火) 20:51:20.79 ID:/CRqdm6R - >プログラムの個数は非可算無限個。
は？
今問題にしているのは通常のチューリングマシンの停止問題であって
拡張チューリングマシンの停止問題ではないぞ？
>問題解決の前提知識として、その問題の答えを要求している
もちろんそうだが。
そういう見方をすれば確かにこれはつまらない。
しかし真に興味深いのは２つのオラクルテープの関係を調べることなのである。
一方のオラクルテープは他方のオラクルテープより真に強力、ということがあり得る。
そのような関係が美しい数学的構造を成すのである。
>もう少し現実的なプログラムは無いの？
お前のような知識のあるやつがこんなセコイ因縁を吹っかけてくるとは失望したぞ。
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
88 ：１[sage]：2016/05/24(火) 21:18:34.79 ID:/CRqdm6R - >プログラムの個数が高々可算無限個だというのなら自然数と対応付ける方法を示してくれない？
うん？
チューリングマシンが可算個、入力が可算個で可算の直積集合になると思ったがなにか勘違いしてるだろうか？
>三角形の内角の和が180度だから平行線は交わらないって言ってるようなもんだぞ。
意味わからんどんな例えだ。
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
91 ：１[sage]：2016/05/24(火) 22:01:34.74 ID:/CRqdm6R - >喩えについてはユークリッド幾何学の第五公理に関する歴史と論争について知ってれば分かるかと
すまん、知らん。
>計算不能なテープをどうやって用意するの？
実際に用意はできないがあると仮定して推論を進めるのである。
|
- すべての言語を判定する計算機構 [無断転載禁止]©2ch.net
92 ：１[sage]：2016/05/24(火) 22:03:42.61 ID:/CRqdm6R - 思わず議論が白熱して張り付いてしまったがこれはいかんなｗ
張り付くの自重せねばｗ
|