Am întâlnit problema de mai jos în acest pdf :
Având un TM M, dacă M scrie vreodată un simbol care nu este gol atunci când este pornit pe banda goală.
Soluția dată este după cum urmează:
Lăsați mașina să scrie doar gol simbol. Atunci numărul său de configurații în calculul com pe w este q × 2, unde q este numărul de stări ale lui M; factorul 2 este pentru alegerile re. direcția mișcării capetelor; nu există niciun factor pentru simbolul scris, deoarece acesta este întotdeauna gol. Deci problema este decisă, decisă de următoarea mașină: input (M, w), rulează M pe w pentru q × 2 pași; dacă M scrie vreodată un simbol necompletat, opriți-vă cu răspunsul da; dacă M nu scrie niciodată un simbol care nu este gol, opriți-vă fără răspuns
Îndoieli:
Q1. Cum să vă asigurați că toate configurațiile qx 2 se vor întâmpla în timp ce executați qx 2 pași pe w? Unele configurații se pot repeta în pașii qx 2.
Q2. Întrebarea spune „când a început pe bandă goală „, dar răspunsul a încercat să simuleze TM pe șirul necompletat w. Cum are sens?
Răspuns
Q1: O stare se poate repeta. Ideea este că, dacă o stare se repetă și nici măcar nu a fost scris niciun simbol ne-gol, atunci știați că mașina Turing nu se va opri niciodată, deoarece este neapărat blocată ciclând unele dintre stările întâlnite până acum. Deoarece niciuna dintre stările ciclului nu a determinat TM să scrie un simbol care nu este gol, TM nu va scrie niciodată un simbol care nu este gol.
După 2q $ $ pași, fie a fost scris un simbol care nu este gol și puteți răspunde „da”, fie că toate simbolurile scrise au fost goale și (cel puțin) o stare trebuie să fi fost întâlnită de două sau mai multe ori, ceea ce înseamnă că puteți răspunde „nu”.
Q2: Presupun că $ w $ este definit undeva pentru a fi șirul gol. Dacă TM poate fi pornit cu un șir arbitrar $ w $ , atunci o variantă a soluției de mai sus funcționează în continuare. Să presupunem că șeful TM începe la începutul $ w $ . Numărul de stări crește cu cel mult $ 1+ | w | $ pentru a lua în considerare toate stările posibile ale benzii (dacă sunt scrise doar simboluri goale) , atunci banda conține întotdeauna unul dintre $ 1+ | w | $ sufixe ale $ w $ ). Dacă capul poate începe de oriunde, atunci acest factor va fi cel mult $ 1+ | w | ^ 2 $ .
Comentarii
- În Q1. Vrei să spui " fie că a fost scris un simbol care nu este gol și poți răspunde da … și poți răspunde nu "? Deoarece întrebarea întreabă " dacă M scrie vreodată un simbol care nu este gol ". În Q2. Nu am primit " în numărul de stări corespunzător numărului de subseturi de poziții ale lui w care au fost suprascrise de un simbol gol "
- Ai dreptate. Mi-am fixat răspunsul. Am clarificat și ultima parte.