2

計算モデルが同等であることをどのように証明できるかについての説明を求めています。同等性の証明が省略されていることを除いて、私はこの主題に関する本を読んでいます。2つの計算モデルが同等であるとはどういう意味かについての基本的な考え方があります（オートマトンビュー：同じ言語を受け入れる場合）。同等性について他の考え方はありますか？チューリングマシンモデルがラムダ計算と同等であることを証明する方法を理解するのを手伝っていただければ、それで十分です。

4

1 に答える 1

1

Aモデルがモデルと同等であることを証明するには、次のBことを示す必要があります。

  1. モデルAはモデルより強くないB
  2. モデルBはモデルより強くないA

モデル X がモデル Y より強くないことを示すには、次のことを証明する必要があります。

X からのすべてのマシンに対して、L(M_X) = L(M_Y) となる Y からのマシンが存在します。

[M_X と M_Y は、それぞれのモデルの別のマシン]

一般的によく知られている証明は次のとおりです。

このテーマに関する詳細情報は、チューリング マシンの同等物の下で読むことができます。

the automata view: if they accept the same languagesまた、クレーム:は正しくない ことに注意してください。両方のモデルで同じオートマトンが同じ言語を受け入れること
を示す必要はありません。A の各オートマトンに対して、L(M_A) = L(M_B) およびその逆のような B のオートマトンがあることを示す必要があります。

于 2012-08-19T14:34:14.697 に答える