Apakah mesin yang tidak pernah berhenti selalu berputar?

Mesin Turing yang kembali ke keadaan sebelumnya dengan kepala baca / tulis pada sel yang sama dari rekaman yang sama akan ditangkap dalam satu lingkaran. Mesin seperti itu tidak berhenti.

Bisakah seseorang memberi contoh mesin yang tidak pernah berhenti yang tidak berputar?

Pertimbangkan TM yang selalu menggerakkan kepala kaset ke kanan dan mencetak simbol pita khusus yang tidak kosong pada setiap langkah. Ini berarti bahwa TM tidak pernah berhenti, karena selalu bergerak ke kanan, dan tidak pernah mengulangi keadaan, karena setelah langkah k kepala tape berada di atas sel k mesin. Akibatnya, setiap konfigurasi mesin berbeda dari yang lain, dan mesin selalu loop.

Kami juga bisa secara non-konstruktif menunjukkan keberadaan mesin tersebut. Asumsikan adanya kontradiksi bahwa setiap TM yang tidak pernah berhenti pada akhirnya berputar. Ini berarti bahwa jika Anda memulai TM pada string w , salah satu dari berikut ini pada akhirnya akan terjadi:$M$$w$

1. berhenti, atau$M$
2. mengulangi konfigurasi.$M$

Dalam hal ini, masalah penghentian akan dianggap sebagai berikut. Diberikan TM dan string w , mensimulasikan M on w , pada setiap titik menuliskan isi rekaman, keadaan saat ini, dan posisi rekaman saat ini. Jika konfigurasi ini adalah duplikat, output "tidak berhenti." Kalau tidak, jika M berhenti pada w , output "berhenti." Karena salah satu dari ini dijamin akan terjadi pada akhirnya, proses ini selalu berakhir, jadi kami akan memiliki algoritme untuk masalah penghentian, yang kami tahu tidak ada.$M$$w$$M$$w$$M$$w$

Semoga ini membantu!

Mesin Turing yang menghitung semua tempat desimal π (atau fraksi non-terminasi lainnya, dalam basis apa pun) tidak pernah berhenti, dan dapat dibuat untuk menulis pada setiap sel hanya beberapa kali. Tentu saja, fakta bahwa tidak ada transisi ke keadaan berhenti akan menjadi hadiah mati, tetapi setidaknya merupakan contoh alami.

Kasus yang lebih menarik (tetapi juga ambigu) akan menjadi mesin Turing yang secara iteratif menghitung fungsi Collatz pada inputnya, mengakhiri jika dan hanya jika ia memperoleh bilangan bulat 1. Dugaan Collatz yang terkenal

$$f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases}$$ adalah untuk input apa pun, prosedur ini akhirnya berhenti. Tetapi tidak diketahui apakah ini masalahnya. Ia dapat gagal dalam dua cara yang berbeda, pada prinsipnya: ia dapat menemukan urutan bilangan bulat yang berputar-putar (sesuai dengan keberadaan bilangan bulat n sehingga untuk sejumlah komposisi, dimana n  ≠ 1); atau bisa jadi ada rantai bilangan bulat n , f (n) , f (f (n))$f \circ f \circ \cdots f(n) = n$, ... yang secara asimptot berbeda dengan tak terhingga. Jika ada urutan dari jenis yang terakhir ada, ini akan menyiratkan bahwa mesin Turing yang saya jelaskan di atas tidak akan berulang, karena rekaman itu akan terus berubah menjadi angka yang lebih besar dan lebih besar.

Pertimbangkan mesin Turing non-stop yang tidak pernah menggerakkan kepala baca / tulis ke kiri.

Jika ini benar, maka masalah penghentian akan dapat ditentukan. Anda hanya akan merekam setiap pasangan (kaset, negara bagian) yang terlihat saat menjalankan mesin Turing, dan mesin tersebut akan berhenti (dalam hal ini jelas berhenti), atau Anda melihat pasangan yang telah Anda lihat sebelumnya, dalam hal ini mesin tersebut tidak berhenti.

Karena masalah penghentian tidak dapat diputuskan, ini tidak mungkin benar. (Lihat contoh lain untuk contoh balasan.)