Jeg stødte på nedenstående problem i denne pdf :
Givet en TM M, om M nogensinde skriver et ikke-blankt symbol, når det startes på det tomme bånd.
Løsning er som følger:
Lad maskinen kun skrive tomt symbol. Derefter er antallet af konfigurationer i com-beregningen på w q × 2, hvor q er antallet af tilstande for M; faktor 2 er for valgene til. retningen af hovedernes bevægelse der er ingen faktor for det skrevne symbol, fordi det altid er tomt. Så problemet kan afgøres, bestemt af følgende maskine: input (M, w), kør M på w for q × 2 trin; hvis det M nogensinde skriver et ikke-blankt symbol, skal du stoppe med ja-svaret; hvis M aldrig skriver et ikke-blankt symbol, skal du stoppe uden svar
Tvivl:
Q1. Hvordan skal du være sikker på, at alle qx 2-konfigurationer vil ske mens du kører qx 2 trin på w? Nogle konfigurationer kan gentages i qx 2 trin.
Q2. Spørgsmålet siger “når startet på tom tape “, men svaret forsøgte at simulere TM på ikke-tom streng w. Hvordan giver det mening?
Svar
Q1: En tilstand kan gentages. Pointen er, at hvis en tilstand gentages, og der ikke engang er skrevet noget ikke-tomt symbol, så vidste du, at Turing-maskinen aldrig vil stoppe, da den nødvendigvis sidder fast og cykler gennem nogle af de stater, der er stødt indtil videre. Da ingen af cyklustilstandene fik TM til at skrive et ikke-blankt symbol, vil TM aldrig skrive et ikke-blankt symbol.
Efter $ 2q $ trin, enten er der skrevet et ikke-blankt symbol, og du kan svare “ja”, eller alle de skrevne symboler var blanke og (mindst) en tilstand skal være stødt på to eller flere gange, hvilket betyder at du kan svare “nej”.
Q2: Mit gæt er, at $ w $ er defineret et eller andet sted som den tomme streng. Hvis TM kan startes med en vilkårlig streng $ w $ , fungerer en variation af ovenstående løsning stadig. Antag, at lederen af TM starter i begyndelsen af $ w $ . Antallet af stater øges med en faktor på højst $ 1+ | w | $ for at tage højde for alle båndets mulige tilstande (hvis der kun er tomme symboler skrevet , så indeholder båndet altid et af $ 1+ | w | $ suffikser af $ w $ ). Hvis hovedet kan starte hvor som helst, vil denne faktor højst være $ 1+ | w | ^ 2 $ .
Kommentarer
- I Q1. Mener du " enten er der skrevet et ikke-tomt symbol, og du kan svare ja … og du kan svare nej "? Fordi spørgsmål spørger " om M nogensinde skriver et ikke-blankt symbol ". I 2. kvartal. Fik ikke " i antallet af tilstande svarende til antallet af undersæt af positioner af w, der er blevet overskrevet af et blankt symbol "
- Du har ret. Jeg fik mit svar. Jeg præciserede også sidste del.