如何知道圖靈機是否是決定者？

有沒有簡單的方法來解決這個問題？我可以通過查看圖靈機的圖來發現它是否是決定因素嗎？如何知道圖靈機是否是決定者？

來源

2016-10-30 Frank Joe

決定器是一個停止所有輸入的機器。 There is no general way to prove whether a given machine halts on all inputs。

如果您有特定的機器，您可以嘗試正式證明所有執行路徑都停止。例如，如果您的機器的讀取頭始終在每次轉換（從不離開）上正確移動，並且在沒有更多輸入時停止，那麼對於所有有限輸入，機器都將停止。一個更簡單的例子是一臺只有一個狀態的機器：暫停。

來源

2016-10-31 19:19:00 Welbog

我對無限輸入感到困惑。如果無限輸入保持圖靈機在兩種狀態之間的變化，並且兩種狀態都不接受狀態和拒絕狀態，這個圖靈機是一個決策者嗎？ –

TM決定語言L當且僅當 1-L把M分割爲接受狀態的字符串 2-串NOT IN L把M分割爲拒絕狀態

TM中號識別語言L IFF 1弦L將M分割爲接受狀態 2-串NOT IN L - 要麼把M分割爲拒絕狀態 - 或導致M至環

@Wanhui巧你說的「以舊換新兩種狀態和在兩者之間的變化國家既不接受也不拒絕國家，這是圖靈可判定？」那麼它肯定會無限地進入它正在進入圖靈識別的循環。

來源

2017-08-05 18:26:43

您可能需要編輯和重新編寫，以便更明顯地瞭解您的文本如何實際回答問題。 – Yunnosch

可以證明普遍認爲

DECIDER_tm = { <M> : TM M is a decider } is undecidable.

用反證法證明。假定它是可確定的，並讓R成爲DECIDER_tm的決定因素。

構造S決定器HALT_tm使用R作爲子程序。

S = on input <M,w> 
1. construct M_w = " on input x" 
    run M on w 
    if M accepts accept. if M rejects reject. 
2. Run R on M_w 
3. If R accept => accept, if R rejects => reject.

注意，如果M接受或拒絕的所有輸入w，M_w暫停，R接受因爲M_w是一個判定器。如果M環路在w,M_w環路上的所有輸入，R拒絕M_w。

我們爲HALT_tm建立了一個決策者，因爲我們知道HALT_tm是不可判定的，我們的假設是錯誤的=>DECIDER_tm是不可判定的。

來源

2017-08-09 23:00:15

如何知道圖靈機是否是決定者？

回答

相關問題