Kom igångKom igång gratis

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.

Turing diagram with missing step

Den här övningen är en del av kursen

Grundläggande datavetenskap

Visa kurs

Interaktiv övning med praktiskt arbete

Gör teori till handling med en av våra interaktiva övningar

Starta övningen