Apakah menerima berarti bahwa TM akan membaca dan mengenali arang dari sel yang sedang dibacanya? Dan apakah TM berhenti jika inputnya dapat ditentukan?
terminology
turing-machines
undecidability
sdfasdgasg
sumber
sumber
Jawaban:
Menerima dan menolak keadaan yang mungkin masuk mesin Turing, didasarkan pada string yang dibaca dari pita, bukan hanya simbol dari satu sel. Tentu saja, keputusan untuk memasukkan kaset penerimaan atau penolakan pada akhirnya dibuat atas dasar satu simbol.
Mesin Turing akhirnya bisa memasuki kondisi penerima, memasuki kondisi menolak, atau mengulang selamanya. Jika masuk ke kondisi menerima atau menolak, maka itu berhenti.
Mesin Turing dikatakan total jika berhenti pada semua input.
Bahasa yang diterima oleh mesin Turing adalah himpunan semua kata yang, ketika diberikan sebagai input ke mesin Turing, menyebabkan mesin Turing memasuki kondisi penerimaan.
Suatu bahasa dikatakan dapat dipilih jika dan hanya jika ada total mesin Turing yang akan menerima bahasa tersebut.
sumber