1

なぜ、数piの有限接頭辞の言語がTMによって決定可能であるのに対し、その与えられた数の有限接頭辞を決定する実数のTMがあると言うのは誤りですか？

4

1 に答える 1

0

数piの有限接頭辞の言語がTMによって決定できるのはなぜですか

pi の数字の有限のプレフィックスを出力するための効果的な計算手順があります。sin(x) のマクローリン級数は x - x^3/3 です! + x^5/5! - ... さらに、sin(pi/2) = 1 であることがわかっているので、1 = x - x^3/3 と設定できます。+ x^5/5! - ...、どこか近いところ (x = 1.5 など) から始めて、前のものよりも増加した x の最大値を見つけます。次に、これに 2 を掛け、最初の n 桁を保持して、長さ n のプレフィックスを取得します。例えば：

f(1.50) < f(1.51) < f(1.52) < f(1.53) < f(1.54) < f(1.55) < f(1.56) < f(1.57)
f(1.59) < f(1.58) < f(1.57)

これは、x = 1.57 が pi/2 に最も近い値であり、実際に必要な値よりも少し大きいか少し小さいことを示しています。cos(x) のマクローリン級数を調べるとわかります。cos(1.57) が正の数に収束することがわかります。したがって、pi/2 より小さい n 桁の最大数にいることがわかります。計算を pi の数字を返すのに必要なレベルよりも少なくとも 1 レベル低くしておけば、すべてうまくいきます。

一方、与えられた数の有限の接頭辞を決定する任意の実数の TM があると言うのは誤りです。

ここに実数があります: n 番目のチューリング マシン (すべての TM の UTM エンコーディングの辞書編集順序によって決定される) が空の言語を受け入れる場合にのみ、n 桁目の 10 進数表現が 1 に設定される 0 と 1 の間の実数. これは明確に定義された実数です。10 進数の各桁は 0 または 1 ですが、この実数の有限の接頭辞を見つけることができる TM があれば、「この TM は空の言語？" 任意の TM について:

  • TM を UTM エンコーディングでエンコードする
  • すべての文字列を辞書順に列挙し、見つかった TM の有効な UTM エンコーディングの数を数えます。
  • 答えを求めている TM をカウントするときに計算を停止する
  • 取得したカウントと同じ長さのプレフィックスを要求する
  • プレフィックスの最後の桁をチェックして、TM が空の言語を受け入れるかどうかを確認します

TM が空の言語を受け入れるかどうかは決定できないため、これは矛盾です。したがって、この実数の有限のプレフィックスを計算できるという仮定は正しくありませんでした。

TM に関する決定不能な問題 (Rice の定理と対角化の引数により、TM の UTM エンコーディングのほとんどの言語がそうであることが保証されます) では、計算できない一意の実数が得られます。確かに、計算可能な実数は、チューリング マシンのように可算ですが、言語や実数は可算ではありません。

于 2017-11-21T21:55:14.843 に答える