Saya ingat dari kelas sarjana bahwa untuk Mesin Turing dengan kaset berhingga akan selalu ada Finite State Automata yang sesuai, tetapi saya tidak dapat menemukan ini dikonfirmasi di mana pun di internet. Apakah ini yang sebenarnya terjadi atau saya salah mengingat?
turing-machines
finite-automata
Jesse Berlin
sumber
sumber
Jawaban:
Itu tergantung apa yang Anda maksud dengan "tape terbatas". Jika Anda mengikat panjang rekaman dengan beberapa fungsi input, maka tidak - Anda dapat mengenali bahasa yang tidak biasa. Sebagai contoh, pertimbangkan LBA .
Untuk membuktikan ini, pertimbangkan informasi apa yang Anda butuhkan untuk menentukan masa depan menjalankan TM: Anda perlu isi rekaman itu, lokasi kepala, dan negara. Jika rekaman itu memiliki jumlah sel yang konstan, dan alfabetnya tetap, maka Anda memiliki jumlah konfigurasi yang konstan, yang dapat Anda enkode sebagai keadaan otomat terbatas.
sumber