Ik kwam onderstaand probleem tegen in deze pdf :
Gegeven een TM M, of M ooit een niet-leeg symbool schrijft bij het starten op de lege band.
De gegeven oplossing is als volgt:
Laat de machine alleen blanco schrijven symbool. Dan is het aantal configuraties in de com-berekening op w q × 2, waarbij q het aantal toestanden van M is; de factor 2 is voor de keuzes re. de richting van de beweging van het hoofd; er is geen factor voor het geschreven symbool omdat dat altijd leeg is. Het probleem is dus beslisbaar, beslist door de volgende machine: invoer (M, w), voer M uit op w voor q × 2 stappen; als het M ooit een niet-leeg symbool schrijft, stop dan met ja antwoord; als M nooit een niet-leeg symbool schrijft, stop dan zonder antwoord
Twijfels:
Q1. Hoe weet je zeker dat alle Qx 2-configuraties zullen plaatsvinden tijdens het uitvoeren van qx 2 stappen op w? Sommige configuraties kunnen worden herhaald in stappen van qx 2.
Q2. Vraag zegt “wanneer gestart op de lege tape “, maar het antwoord probeerde TM te simuleren op een niet-lege string w. Hoe is het logisch?
Antwoord
Q1: Een toestand kan worden herhaald. Het punt is dat als een toestand wordt herhaald en er is zelfs geen niet-leeg symbool geschreven, je weet dat de Turing-machine nooit zal stoppen, omdat hij noodzakelijkerwijs vastloopt tijdens het fietsen door enkele van de tot nu toe aangetroffen toestanden. Aangezien geen van de toestanden van de cyclus ervoor zorgde dat de TM een niet-leeg symbool schreef, zal de TM nooit een niet-leeg symbool schrijven.
Na $ 2q $ stappen, is er een niet-leeg symbool geschreven en kunt u met “ja” antwoorden, of alle geschreven symbolen waren leeg en (ten minste) één toestand moet twee of meer keer zijn aangetroffen, wat betekent dat je kunt “nee” antwoorden.
V2: Ik vermoed dat $ w $ is ergens gedefinieerd als de lege string. Als het TM kan worden gestart met een willekeurige tekenreeks $ w $ , dan werkt een variatie op de bovenstaande oplossing nog steeds. Stel dat de kop van de TM begint aan het begin van $ w $ . Het aantal toestanden neemt toe met een factor van maximaal $ 1+ | w | $ om rekening te houden met alle mogelijke toestanden van de tape (als er alleen lege symbolen worden geschreven , dan bevat de tape altijd een van de $ 1+ | w | $ achtervoegsels van $ w $ ). Als de kop ergens kan beginnen, is deze factor maximaal $ 1+ | w | ^ 2 $ .
Reacties
- In Q1. Bedoelt u " of er is een niet-leeg symbool geschreven en u kunt ja antwoorden … en u kunt nee "? Omdat de vraag " vraagt of M ooit een niet-leeg symbool schrijft ". In Q2. " niet ontvangen in het aantal staten dat overeenkomt met het aantal subsets van posities van w die zijn overschreven door een leeg symbool "
- Je hebt gelijk. Ik heb mijn antwoord opgelost. Ik heb ook het laatste deel verduidelijkt.