Apakah non-determinisme dalam mesin turing non-deterministik berbeda dari yang ada pada automata terbatas dan push down automata?

Biarkan string input diberikan sebagai . Kemudian jika NFA saat ini dalam keadaan r (dan telah membaca input hingga alfabet w i ) maka sebelum membaca simbol input berikutnya NFA terbagi menjadi dua NFA, satu berada di keadaan r dan yang lainnya di s , jika ada transisi dari tipe r ϵ → s . Jika ada siklus tipe r ϵ → s ϵ → q 1 . . . . ϵ →$w_1w_2...w_n$$r$$w_i$$r$$s$$r \xrightarrow{\epsilon} s$ , di mana q i adalah beberapa status NFA, maka tidak ada gunanya mengingat NFA lain dalam status r hingga titik di mana input telah dibaca hingga alfabet w i . Jika PDA (non-deterministik) dalam keadaan r (dan input dibaca hingga w i ) dan terdapat siklus r ϵ , ϵ → a → s ϵ , ϵ → a → q 1 . . . . ϵ , ϵ → $r \xrightarrow{\epsilon} s \xrightarrow{\epsilon} q_1....\xrightarrow{\epsilon} q_k \xrightarrow{\epsilon} r$$q_i$$r$$w_i$

$r$$w_i$(di mana transisiϵ,ϵ→aberarti bahwa tidak ada setelahwidibaca dari input, tidak ada yang muncul atau dibaca dari stack dan alfabetadidorong ke stack) kemudian sebelum membaca input berikutnya alfabetwi+1akan ada PDA terbatas di negara-negarar,s,q1,. . . q$r \xrightarrow{\epsilon,\epsilon \to a} s \xrightarrow{\epsilon,\epsilon \to a} q_1....\xrightarrow{\epsilon,\epsilon \to a} q_k \xrightarrow{\epsilon,\epsilon \to a} r$$\epsilon,\epsilon \to a$$w_{i}$$a$$w_{i+1}$$r,s,q_1,...q_k$ karena berbeda dengan NFA walaupun pada kondisi stack isinya terbatas bisa berbeda (kemungkinan tak terbatas), kalau saya tidak salah.

Seperti halnya NFA dan PDA, kekuatan non-determinisme berasal dari transisi . Jadi saya berasumsi bahwa mesin Turing non-deterministik juga mendapatkan non-determinisme dari transisi ϵ seperti NFA dan PDA (lebih seperti PDA). Saya tahu bahwa mesin Turing deterministik dapat mensimulasikan yang non-deterministik (saya tahu bukti yang menggunakan pencarian pertama-roti). Tapi sekarang saya ragu bagaimana itu mungkin. Karena jika siklus dari tipe dalam PDA di atas, ada dalam diagram keadaan mesin Turing non-deterministik maka sebelum membaca simbol selanjutnya w i + $\epsilon$$\epsilon$$w_{i+1}$mesin Turing deterministik bahkan ketika mensimulasikan konfigurasi di beberapa cabang mesin Turing non-deterministik (sementara bfs) harus melacak mesin Turing infinite (sekali lagi keadaannya terbatas tetapi simbol pada rekaman memiliki kemungkinan tak terbatas).
Lantas bagaimana tepatnya non-determinisme di definisikan dalam kasus mesin Turing? Apakah saya salah memahami sesuatu yang sepele? Apakah mesin Turing non-deterministik menggunakan transisi ?$\epsilon$

Saya minta maaf atas keraguan sepele saya. Jika ada yang salah saya dapat memperbarui pertanyaan saya.

Non-determinisme adalah konsep yang sama dalam semua konteks - mesin diperbolehkan beberapa opsi untuk melanjutkan pada titik tertentu. Namun, semantiknya sedikit berbeda karena DFA / NFA dan PDA selalu mendefinisikan fungsi total , sementara mesin Turing (deterministik atau non-deterministik) secara umum mendefinisikan fungsi parsial .

$f$$x$$f(x) = \bot$$f$$M$$M$$x$$M(x)$$M$$x$$M(x) = \bot$.

$M$$x$$M(x)=1$$M(x)=0$$M(x)=\bot$$M$$L = \{x : M(x) = 1\}$

Mesin Turing non-deterministik (yang selalu merupakan penentu) diizinkan untuk "bercabang" (memiliki beberapa opsi yang memungkinkan pada titik waktu tertentu), dan memiliki semantik berikut:

• $M(x) = 1$$x$$M$
• $M(x) = 0$$x$$M$
• $M(x) = \bot$$x$$M$

Dengan definisi ini, mudah-mudahan jelas bagaimana mensimulasikan mesin Turing non-deterministik menggunakan penentu mesin Turing deterministik: Anda mencoba semua cabang, memeriksa apakah ada di antara mereka yang mengarah ke keadaan berhenti menerima. Setelah semua cabang berhenti, Anda dapat memutuskan apakah akan pergi ke negara penerima atau ke negara penerima. Jika mesin Turing non-deterministik tidak berhenti di beberapa cabang, maka mesin Turing yang deterministik juga akan berhenti.

$\epsilon$$\epsilon$

$\epsilon$