チューリングマシンの同等物のリストに関するウィキペディアの記事を見つけました。ただし、特定のマシンがチューリングマシンと同等であるかどうかを判断する方法はわかりません。
それを証明するためにチューリングマシンの定義を使用する必要がありますか？例を挙げていただけますか？
ありがとう。
1835 次
3 に答える
4
チューリング完全であることを証明する標準的な方法は、TMに相当するものの1つをマシンに実装することです。それが可能であれば、マシンはチューリング完全です。そうでない場合は、そうではありません。したがって、たとえば、新しいプログラミング言語が完全にチューリング完全であることを証明しようとした場合、実装が最も簡単なTM相当を選択し、プログラミング言語がそれをシミュレートできることを示します。
于 2011-01-10T10:08:34.517 に答える
1
実際、それを実際に証明することはできません。少なくとも、これらの一般的な等式証明を完全に形式化するには、理論計算機科学でさえ予想されるよりもはるかに形式的な論理が必要になる可能性があります。（同意できない場合は、教えてください！これについて話し合いたいと思います。）
ただし、コンテキストからはほとんど明らかです。別のそのような計算モデルB内に計算スキームAの「マシン」のシミュレーションを構築しようとします。これは、BがAをシミュレートできるため、Aの全能力を備えていることを意味します。逆の場合、これら2つのモデルは次のように呼ばれます。同等。
于 2011-06-04T22:37:43.493 に答える
0
私の頭のてっぺんから：あなたのマシンが既知のチューリングマシン等価マシンの1つをシミュレートできる場合、あなたのマシンもチューリングマシン等価です。
おそらく、このようなことをする最も簡単な方法です。
編集：私は、これがチューリングマシンと同等であるための要件であることを意味していませんが、そうである可能性があります。たぶん、理論情報学にもう少し熟練している誰かがこれについて私を片付けることができますか？
于 2011-01-10T09:29:27.167 に答える