マシンがチューリングマシンであるかどうかを確認する方法

Question

私はウィキペディアの記事a list of Turing machine equivalentsを見つけました。しかし、与えられたマシンが同等のチューリングマシンであるかどうかを判断する方法を教えているわけではありません。

チューリングマシンの定義を使ってそれを証明する必要がありますか？例を挙げていただけますか？

ありがとうございました。

Answer 1

何かを証明する標準的な方法は、お使いのマシンにTM相当物の1つを実装することです。それが可能なら、あなたのマシンはチューリング完了です。そうでなければ、そうではありません。ですから、新しいプログラミング言語が完成したことを証明しようとしていたら、実装するのが最も簡単なTM同等物を選び、私のプログラミング言語がそれをシミュレートできることを示しましょう。

Answer 2

私の頭の上部：あなたのマシンが既知のチューリングマシンと同等のマシンの1つをシミュレートできれば、あなたのマシンも同等のチューリングマシンです。

おそらく、このようなことをするのが最も簡単な方法です。

編集：これはマシンがチューリングマシンに相当することを意味しているわけではありません。理論的な情報学にもう少し熟練している人なら、私はこれを解消することができますか？

Answer 3

実際、それは実際には証明できません。少なくとも、これらの共通の平等証明を完全に公式化するには、理論計算機科学でも予想されるよりもはるかに正式な論理が必要になるかもしれない。 （あなたが同意しない場合は、私に教えて欲しい！）

しかし、それは文脈からほとんど明らかです。あなたは計算Bの別のモデルの中で計算Aのスキームの "マシン"のシミュレーションを構築しようとします。これはBがAをシミュレートできることを意味し、したがってAの完全なパワーを持ちます。逆の場合、同等。