可判定語言（計算模型）

Question

我需要證明L是否可判定與否：

L = {< M> | M是TM和L的（M）的結合和對H_TM是在RE}

（H_TM = {< M，W> | M是上瓦特}停止一個TM）

Answer 1

我假定< ...>是Gödelization中TM的編號。 L（M）是一組詞，而H_TM是一組對。因此，他們的聯盟是不相交的，兩者都不會出現任何因素。通常情況下，工會如果有兩個部分是可以列舉的。 H_TM是可枚舉的，因此可枚舉性僅取決於L（M）。但是作爲TM的語言意味着可以明確無誤地判斷。因此，在定義L時M的條件總是爲真，因此L是所有TM描述的集合，這是規則的且明確可判定的。