小さなもので大規模なチューリングマシンをシミュレートした議論の欠陥を見つけるのを助けます

cs.stackexchange https://cs.stackexchange.com/questions/121911

  •  29-09-2020
  •  | 
  •  

質問

私はそれが通過した場合、ちょうどそれがあることが証明されている引数を持っています：

  • プログラミング言語は、Turing Machines
    • よりも強力です。
  • チューリングマシンのビジービーバー関数（ $ bb（）$ ）は計算可能です

今、私の議論が私が見つけることができないいくつかの欠陥を持っている可能性が非常に高いことを理解しています。しかし、それは私にとってより面白いです私がではなく、ではなく私が間違っているかどうか。

引数

チューリングマシンを構築する $ m_1 $ の引数として（テープ上） $ n、k $ < / SPAN>は、 $ k $ が停止するまで、状態ですべてのチューリングマシンをシミュレーションします。それからそれ自体を止める。次のPythonスニペットで実証されたように、これはプログラミング言語で書くのは簡単です：

def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1
.

今、 $ m_1 $ $ m_1 $ に必要な状態の数です。 $ n $ $ m_1 $ よりはるかに大きい。 $ k_1 $ を $ m_1（n、k_1）$ haltsと $ k_0 $ $ m_1（n、k_0）$ halts、 $ K_1 $ シミュレートされたチューリングマシンは停止しました（すべての同等のマシンは同じステップで停止します）。 $ k $ を選択して、 $ k_0 \ leq k \ leq k_1 $ 。つまり、 $ m_1（n、k）$ は、約 $ bb（n）$ ステップで停止します。

construct $ m_2 $ は、 $ m_1 $ と同じですが、最初に行ったことを除いて $ n $ と $ k $ をテープに書き込みます。 $ m_2 $ を $ m_2 $ に必要な状態の数になります。その後、 $ m_1 + k（n）+ k（k）+ c= m_2 $ いくつかの小さな $ c $ （おそらく一定と可能性がある $ 0 $ ）、 $ k（n）$ $ n $ の複雑性

今、 $ k（n）$ は $ O（\ log（n））$ 。 $ n $ 状態を備えた $ n $ sot span class="math -container "> $ k $ は $ n ^ n $ 、したがって $ k（k） $ は $ o（\ log（n ^ n））= o（n \ cdot \ log（n））$ です。つまり、 $ m_2> n $ です。しかし、ここで問題があります。 $ k $ の場合（ $ k（k）に書き込むのが簡単です。 ）、 $ m_2 $ は $ nよりわずかに小さくなります。 $ 。それは $ bb（m_2）> bb（n）$ 、および $ m_2 、明確な矛盾

私の心の中で、これらは可能性のある解像度です：

  • $ M_1 $ は、チューリングマシンとして作成することは不可能です。つまり、Pythonはマシンのチューリングよりも強力です。
  • 一般的にチューリングマシンよりもはるかに強力ではないチューリングマシンへのトランスフィニリスト拡張があり、 $ m_1 $ をこの拡張子に書き込むことができます。言い換えれば、 $ m_1 $ の一連のマシンの制限です $ m_ {1、n} $ 、それぞれが $ n を処理できます。これはおそらく計算可能なビジービーバー関数を必要とするでしょう。
  • $ \ log（k）= n $ 状態にはるかに少ないチューリングマシンによって書き込まれない数字の大きなセットがあります。 SPAN CLASS="math-container"> $ k（k））。 $（n、k）$ の候補者が十分に圧縮されている可能性があることは不可能です。

このロジックのエラーはどこにありますか？

私は以前は $ k（k）\ leq o（n）$ であると言っていましたが、疑わしいものは指摘されました。それと固定されている（ $ O（n \ cdot \ log（n））$ ）、それはまだ私たちが減少を達成できないことがまだ驚くようです $ k（k）\ \ \ cdot \ log（n）$ <

/ span> $ k（k） $（n、k）$ 、しかしもはや不可能ではありません。
役に立ちましたか？

解決

あなたの欠陥はここにいるようです：

今、 $ k（n）$ は $ O（\ log（n））$ 。 $ k $ は、 $ n ^ n $ です。 $ k（k）$ は、 $ o（n）$ です。これは $ m_2 $ を $ n $ よりわずかに大きいです。

$ k $ は $ n ^ n $ です（より正確には $ k= n ^ {\ theta（n）} $ または $ k= 2 ^ {\ theta（n \ log n） $ で、これは上限 $ k $ によって示されます。チューリングマシンの数によって、シンプルな停止チューリングのファミリを見つけることで下限の下限マシン）。ただし、 $ k（k）$ が $ o（n）$ 。 むしろ、 $ k（k）$ が最大であることを知っています $$ o（\ log（n ^ n））= o（n \ log n）。 $$

矛盾は、 $ k（k）$ が $ k $ の選択に依存しています。 class="math-container"> $ O（n）$ （ $ n $ より少し小さい）。あなたの推論はこれが不可能であることを示しています。

しかし、これは驚くべきことではありません：ほとんどの $ k $ 私たちは $ O（n \ log n）であることを期待しています）$ 、および $ k $ は、 $ nを持つマシンのチューリングに関する情報をたくさん保持する番号です。 $ の状態、そのような数値を $ o（n）$ 状態よりも小さくすることができることを期待していません。

ps Pythonがチューリングマシンと実質的に同等であるかどうかの質問は（おそらくそれが正式に示されていないので知っていない）、あなたのプログラムM1は実際にはAとして明確に表現可能です。チューリング機。これから、チューリングマシンとして表現可能ではないM1に基づく解像度が正しくないことがわかります。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top