等效的計算模型

Question

我在尋求解釋如何能夠證明計算模型是等價的。我一直在閱讀有關該主題的書籍，但省略了等效證明。我有兩個計算模型等價的意思（自動機視圖：如果他們接受相同的語言）意味着什麼。還有其他的思考等值的方式嗎？如果你能幫助我理解如何證明圖靈機模型等價於lambda演算，那就足夠了。

Answer 1

爲了證明一個模型A相當於模型B你需要證明：

1. 型號A不強則模型B
2. 型號B不強則模型A

要顯示模型X不是更強，那麼模型Y必須證明：

對於從X每個機器，有選自Y存在一臺機器，使得L（M_X） = L（M_Y）

[其中M_X和M_Y是從每個模型分別不同的機器]

公知的常用證明是：

• DFA相當於NFA
• NFA相當於NFA與小量移動
• Multi tape turing machine相當於一個磁帶圖靈機對這個問題

更多信息，可以Turing machine equivalents

下閱讀還要注意，索賠：the automata view: if they accept the same languages是不正確的。
您無需顯示相同的自動機在兩種型號中都接受相同的語言。
您需要證明對於A中的每個自動機，B中有一個自動機，使得L（M_A）= L（M_B），反之亦然