爲什麼lambda轉換不在圖靈機中？

圖靈機中未定義Lambda轉換？這是什麼原因？有人請解釋我。爲什麼lambda轉換不在圖靈機中？

在此先感謝。

2017-06-02 blackilDiamond

[lambda轉換]（https://en.wikipedia.org/wiki/Lambda_transition）似乎與圖靈機無關... –

在我的「計算理論」最後一年的課程中，我們學習如下序列：抽象引理，有窮自動機（DFA，NFS），下推自動機，圖靈機，可判定問題，NP，NP-complete。雖然NFA中的「lambda轉換」使事情變得更加簡單和乾淨，但與高度複雜的Turing模型相連並提出這個問題並不是很糟糕。 –

希望我20年前的記憶仍然有效，如有錯誤請更正！

您是否在談論NFA中的lambda轉換？ NFA中的Lambda轉換主要是爲了簡化FA的複雜性。您還應該學習如何將NFA轉換爲DFA s.t.它是確定性的，一個「機器」能夠逐步「執行」它來處理其反映的形式語言。圖靈機是圖靈理論下的一種抽象機器，也是當今大多數計算機的模型（量子計算機除外，這在我們的世界中還很少見）。在我的理解中，圖靈機是確定性的並通過水龍頭執行以執行「計算」。裏面沒有非確定性元素。

來源

2017-06-02 01:25:07

謝謝ken，是的，我正在考慮NFA中的Lambda轉換。是的，當我谷歌搜索時，我發現圖靈機是確定性的。你能解釋一下這句話嗎？「內部沒有非確定性元素」謝謝。 – blackilDiamond

對不起，我英文很差。我只想清楚地說明，對於圖靈機來說，一切都必須是確定性的。一旦我們有一個lambda轉換，這意味着我們可能有兩個或更多的有效和可能的「下一個狀態」去，這將使TM無法確定下一步應該做什麼。 –

非常感謝Ken – blackilDiamond

爲什麼lambda轉換不在圖靈機中？

回答

相關問題