Jag stötte på nedanstående problem i denna pdf :
Givet en TM M, om M någonsin skriver en icke tom symbol när den startas på det tomma bandet.
Lösningen ges är följande:
Låt maskinen bara skriva tom symbol. Då är dess antal konfigurationer i com-beräkningen på w q × 2, där q är antalet tillstånd för M; faktor 2 är för de val som gäller. riktningen av huvudets rörelse; det finns ingen faktor för den skrivna symbolen eftersom den alltid är tom. Så problemet är avgörbart, beslutat av följande maskin: input (M, w), kör M på w för q × 2 steg; om det M någonsin skriver en icke tom symbol, sluta med ja svar; om M aldrig skriver en icke tom symbol, sluta utan svar
Tvivel:
Q1. Hur kan du vara säker på att alla qx 2-konfigurationer kommer att hända medan du kör qx 2 steg på w? En del konfigurationer kan upprepas i qx 2-steg.
Q2. Frågan säger ”när den startas på tom tejp ”, men svaret försökte simulera TM på icke tom sträng w. Hur är det vettigt?
Svar
F1: Ett tillstånd kan upprepas. Poängen är att om ett tillstånd upprepas och ingen icke-tom symbol ens har skrivits, så visste du att Turing-maskinen aldrig kommer att stanna eftersom den nödvändigtvis sitter fast och cyklar genom några av de stater som hittills hittats. Eftersom ingen av tillstånden i cykeln orsakade att TM skrev en icke-tom symbol, kommer TM aldrig att skriva en icke-tom symbol.
Efter $ 2q steg på $ , antingen en symbol som inte är tom har skrivits och du kan svara ”ja”, eller så var alla skrivna symboler tomma och (åtminstone) ett tillstånd måste ha påträffats två eller flera gånger, vilket betyder att du kan svara ”nej”.
Q2: Min gissning är att $ w $ definieras någonstans som den tomma strängen. Om TM kan startas med någon godtycklig sträng $ w $ , fungerar fortfarande en variant av ovanstående lösning. Antag att chefen för TM börjar i början av $ w $ . Antalet tillstånd ökar med en faktor som högst $ 1+ | w | $ för att ta hänsyn till alla möjliga tillstånd på bandet (om bara tomma symboler skrivs , då innehåller tejpen alltid ett av $ 1+ | w | $ suffix av $ w $ ). Om huvudet kan börja var som helst kommer denna faktor att vara högst $ 1+ | w | ^ 2 $ .
Kommentarer
- I Q1. Menar du " antingen en symbol som inte är tom har skrivits och du kan svara ja … och du kan svara nej "? Eftersom frågan frågar " om M någonsin skriver en icke tom symbol ". Under andra kvartalet. Fick inte " i antalet tillstånd som motsvarar antalet delmängder av positioner för w som har skrivits över med en tom symbol "
- Du har rätt. Jag fixade mitt svar. Jag klargjorde också den senare delen.