Diberi TM

Saya ingin menentukan apakah masalah keputusan ini dapat diputuskan. Saya telah mencoba membuat reduksi dari Halt dan "Terima string kosong", tetapi saya belum menemukan solusi.

Adakah yang bisa membantu saya?

computability turing-machines undecidability Shuzheng
sumber

Ini berarti mesin harus tetap berada di tempat yang sama, tidak bergerak. Tidak banyak kemungkinan untuk perhitungan seperti itu?

Hendrik Jan

Mungkin bergerak, sebenarnya. Tapi anggaplah itu

δ (q_{0},_) = (q, a, D)

$\delta(q_0,\_) = (q,a,D)$ untuk beberapa negara

q

$q$ , label

a

$a$ dan

D \in {L, R}

$D\in\{L,R\}$ . Apa yang bisa Anda katakan tentang kasus ini?

q \neq q_{0}

$q\neq q_0$ ? Apa yang terjadi selanjutnya jika

q = q_{0}

$q = q_0$ ?

Klaus Draeger

Masalah ini mungkin bisa diputuskan. Saya menemukan makalah ini hal.inria.fr/inria-00074105 (saya tidak membaca jadi saya tidak yakin) yang dapat menarik minat Anda. Ia mengklaim bahwa masalah penghentian untuk satu mesin Turing keadaan dapat ditentukan. (yang merupakan masalah yang cukup dekat dengan masalah Anda).

wather

Silakan ubah judul pertanyaan "... saat mulai kaset kosong" jika karunia Anda adalah tentang "input kaset apa pun": kasus di mana kaset itu balnk dapat diputuskan oleh orang lain (saya mengirim jawaban tetapi tiba-tiba saya menghapusnya saat Saya melihat komentar pada bounty)

Vor

Jawaban:

Saya akan mengatakan itu decidable.

Jika saya mengerti dengan benar, inilah yang saya pikirkan.

Pertama-tama TM dimulai dari beberapa keadaan awal $s_0$ . Bagaimana itu bisa mengubah keadaan? Dalam fungsi transisi Anda, Anda memiliki sesuatu seperti $(s_0, x) \to (s_i, y, m)$ dimana $s_i$ adalah sebuah negara dan $x$ , $y$ adalah simbol dan $m$ adalah gerakan kepala (kiri kanan atau tetap). Jadi, jika ia meninggalkan kondisi awal harus ada transisi dari $(s_0, \_)$ ke beberapa negara tidak $s_0$ . Mudah dilihat bahwa itu adalah jika dan hanya jika. Dengan demikian, Anda dapat membangun mesin Turing lain yang memiliki input sebagai TM dalam beberapa pengkodean, melewati fungsi transisi dan memeriksa kondisi di atas, dan masalahnya dapat diputuskan.

Eugene
sumber

Saya tidak mengerti jawaban / algoritma ini. Pertimbangkan TM yang memang memiliki aturan transisi yang dapat meninggalkan status

s_{0}

$s_0$ jika simbol di bawah kepala adalah X. Sekarang kita perlu tahu apakah X dapat hadir dalam sel rekaman itu. Misalkan TM juga memiliki aturan transisi tentang negara

s_{0}

$s_0$ yang bergerak ke kiri dan / atau kanan dan menulis simbol ke rekaman itu, termasuk berpotensi X. Sekarang apa yang akan Anda lakukan? Bagaimana Anda akan tahu apakah TM berpotensi menulis X ke beberapa sel dan kemudian mengunjungi kembali sel itu? Saya tidak melihat algoritma apa pun di sini yang menangani situasi itu.

@DW Apakah kita berbicara tentang TM deteministik atau nondeterministik di sini?

Eugene

Itu pertanyaan Anda harus menanyakan poster asli jika Anda pikir itu tidak jelas, tetapi dengan informasi yang diberikan saya pikir kita harus menganggap TM deterministik. Yang mengatakan, saya curiga saya dipengaruhi oleh teks karunia, yang disebut ~ "tidak pernah meninggalkan keadaan awal tidak masalah untuk keadaan awal rekaman" ~, yang sedikit berbeda dari "tidak pernah meninggalkan keadaan input saat awal keadaan rekaman itu sepenuhnya kosong ", jadi mungkin keberatan saya tidak relevan dengan pertanyaan yang diajukan.

Bagaimanapun, mungkin akan membantu untuk membenarkan bagian "mudah dilihat ..." dengan lebih hati-hati. Misalnya, Anda tampaknya tidak secara eksplisit menggunakan fakta bahwa rekaman awal semuanya kosong, meskipun tampaknya ini membuat perbedaan besar.

Dapat dianggap remeh. Mengingat rekaman itu benar-benar kosong, maka T dalam keadaan $s_0$ harus mengubah sel kaset yang saat ini dipindai dan melakukan salah satu dari tiga hal: (1) Transisi ke keadaan berbeda dan bergerak ke kiri atau kanan (atau berhenti); (2) Transisi kembali ke $s_0$ dan gerakkan satu sel ke kiri; (3) Transisi kembali ke $s_0$ dan gerakkan satu sel ke kanan. Untuk kedua (2) dan (3) kepala TM telah pindah dari sel kaset asli dan sekarang memindai sel kosong; karena itu sekarang berada dalam situasi yang sama dengan yang dimulainya, dan akan bertindak dengan cara yang sama. Jadi untuk (2) atau (3) perilaku TM pada pita kosong adalah bergerak selamanya dalam satu arah, meninggalkan jejak (mungkin) sel yang diubah. Jadi properti ini dapat diperiksa dengan memeriksa isi satu baris dari 'program' TM (yaitu aturan transisi untuk $s_0$ pemindaian kosong) - jika negara baru TIDAK $s_0$ (termasuk 'penghentian') jawabannya adalah YA, jika tidak, jawabannya TIDAK.

Saya juga cukup yakin bahwa masalah ini masih dapat diputuskan karena diberi input sewenang-wenang - Anda hanya perlu memperhatikan lebih dekat ke arah mana kepala pita bergerak tergantung pada isi sel saat ini.

PMar
sumber