證明TM和DFA的等價性

Question

我試圖用停止問題的減少來證明TM = DFA是不可判定的理論上我明白圖靈機捕獲所有可計算函數，而DFA只捕獲可以常量計算的函數因此TM = DFA是不可判定的。

這裏是我的步驟： 假設是R那個決定L（M）= L（d）

EQ_DM = {[d，M] | L（M）= L（d）}

和我們創建一個圖靈機

HALT_TM = {[M，W] | （在輸入砂→M停止接受
中號沒有輸入停止波→拒絕）}

如何構建一個d &中號中以r [d，M]告訴如果M停止W上？

Answer 1

假設TM和DFA是否接受相同的語言是可判定的。您可以使用它來解決一般TM的停機問題。

給定任何TM M和單詞w，構造M'，以便每當M進入暫停狀態時，M'進入暫停接受狀態。現在，M'是一個接受導致M停止的每個字符串的TM。現在從M'構造M「，使得L（M」）是L（M'）和{w}的交點，其中w是任何單詞。給定{D}和M'的DFA，您可以始終使用笛卡爾產品機器構造來構造M''。由於可以確定L（M「）是否等於DFA的值 - 比如說{W}的DFA，我們可以說M''是否接受{w}。如果它接受w，則L（M'）包含w，並且如果L（M'）包含w，則M將停止在w上。如果M「不接受w，則L（M'）不包含w，因此M不會停止w。