Saknat steg i Turingmaskinen
Vi vill utforma en Turingmaskin som adderar 1 till ett binärt tal. Maskinen bearbetar talet från höger till vänster och följer dessa regler:
- Börja vid den högra biten.
- Om den aktuella biten är 0: Vänd den till 1 och stanna.
- Om den aktuella biten är 1: Vänd den till 0 (eftersom 1 + 1 ger en minnessiffra) och flytta åt vänster för att bearbeta nästa bit.
- Om maskinen rör sig förbi den vänstraste siffran (dvs. stöter på en blank cell): Skriv en 1:a för att representera minnessiffran och stanna.
Följande tillståndsdiagram försöker beskriva dessa steg men saknar en viktig övergång. Identifiera det saknade steget.

Den här övningen är en del av kursen
Grundläggande datavetenskap
Interaktiv övning med praktiskt arbete
Gör teori till handling med en av våra interaktiva övningar
Starta övningen