這種語言是否可確定

L = {（，，x）| M1（x）嚴格執行多於M2（x）的步數}。（如果兩個計算都是永久運行的，那麼兩個計算都不會比另一個嚴格得多）。這種語言是否可確定

該語言是否可判定？如何證明它？

2017-10-12 Rohil Hakim

作爲一個暗示，這一個是不可判定的。作爲一個提示，讓M1成爲一個總是循環的機器，看看你是否可以讓M2成爲一臺機器，其行爲取決於某些第三個TM M是否停止在一個字符串w上。（順便提一下，這些問題往往更適合cs.stackexchange.com，但由於我們不鼓勵交叉發佈，因此不要在此重新發布此特定問題。） – templatetypedef

作爲評論中的templatetypedef提示，此語言是不可判定的。如果它是可確定的，你可以按如下方式決定暫停問題。

首先，讓M1爲任何無法停止輸入x的TM。這樣一個TM可能是一個微不足道的，它有兩個左右移動的狀態，不會改變磁帶。讓M2成爲任何TM。現在，您的語言決策者可以回答「M2是否停止所有輸入」的問題，這相當於暫停問題。您也可以讓M2成爲TM，它首先確認磁帶上的任何特定輸入w，然後根據某些TM M3繼續。這會將問題改變爲「M3是否停止輸入w」，這可能是問題的更規範的版本。

來源

2017-10-13 12:34:37 Patrick87

這種語言是否可確定

回答

相關問題