關於圖靈機接受的語言定義的困惑,一個非常基本的問題


0

我正在為即將參加的考試而學習,我的書給出了以下定義:

$ M $ 成為圖靈機,然後將接受的語言 $ T(M)$ $ M $ 的定義為 $ T(M)= \ {x \ in \ Sigma ^ * \ mid z_0 x\ vdash ^ * \ alpha z \ beta;\ alpha,\ beta \在\ Gamma ^ *;z \ in E \} $

作為旁注, $ \ vdash $ 表示從TM的一種配置過渡到另一種配置,而 $ ^ * $ 表示此關係的任意數量的應用程序。

我感到困惑的是,在接受的定義下,我只需要進入一次結束狀態,即使我離開它,單詞也會被接受,或者我可以在這個結束狀態下循環。在下推自動機或常規自動機中,當我們從頭到尾依次遍歷單詞時,我們沒有這個問題,尤其是在下推自動機中,堆棧與輸入單詞分離。

現在,我在大多數其他定義中都讀到了另外,以結束狀態結束,圖靈機也必須停止,這意味著它必須以沒有過渡的狀態結束。儘管我不確定這對於確定性的Turing機器意味著什麼,因為它們必須對機器的所有配置進行轉換。

總結一下:

問題1:是否需要停止?是接受語言的有用屬性,還是有理由按原樣給出定義?

問題2:您將如何為確定性圖靈機定義"停止"?

0

Even in a deterministic Turing machine, the transition function $\delta$ may be a partial function i.e. there can be pairs of states and tape symbols for which the transition function is not defined. If the Turing machine is in state $z$ and reads symbol $\alpha$ and $\delta(z,\alpha)$ is not defined then it halts. Usually the accepting states $E$ are implemented by creating states for which the transition function is undefined for all inputs i.e. the Turing machine will always halt once it enters a state $z \in E$, regardless of the symbol it reads from the tape. You may also have other halting states, but if the machine halts in a state $z \notin E$ then it has rejected the input string.