Jeg kom over problemet under denne pdf :
Gitt en TM M, om M noen gang skriver et ikke-blankt symbol når det startes på det tomme båndet.
Løsningen er som følger:
La maskinen bare skrive tom symbol. Deretter er antall konfigurasjoner i com-beregningen på w q × 2, hvor q er antall tilstander til M; faktor 2 er for valgene re. retningen på hodet bevegelse; det er ingen faktor for det skrevne symbolet fordi det alltid er tomt. Så problemet er avgjørbart, avgjort av følgende maskin: input (M, w), kjør M på w for q × 2 trinn; hvis det M noen gang skriver et ikke-tomt symbol, stopp med ja-svaret; hvis M aldri skriver et ikke-tomt symbol, må du stoppe uten svar
Tvil:
Q1. Hvordan være sikker på at alle qx 2-konfigurasjoner vil skje mens du kjører qx 2 trinn på w? Enkelte konfigurasjoner kan gjentas i qx 2 trinn.
Q2. Spørsmålet sier «når det startes på tom tape «, men svaret prøvde å simulere TM på ikke tom streng w. Hvordan er det fornuftig?
Svar
Q1: En tilstand kan bli gjentatt. Poenget er at hvis en tilstand blir gjentatt og det ikke en gang er skrevet noe ikke-tomt symbol, så visste du at Turing-maskinen aldri vil stoppe, da den nødvendigvis sitter fast og sykler gjennom noen av statene man har opplevd så langt. Siden ingen av tilstandene i syklusen førte til at TM skrev et ikke-tomt symbol, vil TM aldri skrive et ikke-tomt symbol.
Etter $ 2q trinn på $ , enten er det skrevet et ikke-tomt symbol, og du kan svare «ja», eller alle de skrevne symbolene var blanke og (i det minste) en tilstand må ha vært oppstått to eller flere ganger, noe som betyr at du kan svare «nei».
Q2: Jeg antar at $ w $ er definert et sted for å være den tomme strengen. Hvis TM kan startes med en vilkårlig streng $ w $ , fungerer en variant av løsningen ovenfor fortsatt. Anta at hodet til TM starter i begynnelsen av $ w $ . Antall stater øker med en faktor på maksimalt $ 1+ | w | $ for å ta hensyn til alle mulige tilstander på båndet (hvis bare tomme symboler er skrevet , så inneholder båndet alltid en av $ 1+ | w | $ suffikser av $ w $ ). Hvis hodet kan starte hvor som helst, vil denne faktoren maksimalt være $ 1+ | w | ^ 2 $ .
Kommentarer
- I Q1. Mener du " enten er det skrevet et ikke-tomt symbol, og du kan svare ja … og du kan svare nei "? Fordi spørsmål stiller " om M noen gang skriver et ikke-blankt symbol ". I 2. kvartal. Fikk ikke " i antall tilstander som tilsvarer antall delmengder av posisjoner av w som er blitt overskrevet av et tomt symbol "
- Du har rett. Jeg fikset svaret mitt. Jeg presiserte også den siste delen.