Aan de slagGa gratis aan de slag

Ontbrekende stap in Turingmachine

We willen een Turingmachine ontwerpen die 1 bij een binair getal optelt. De machine verwerkt het getal van rechts naar links en volgt deze regels:

  • Begin bij het meest rechtse bit.
  • Als het huidige bit 0 is: Zet het om naar 1 en stop.
  • Als het huidige bit 1 is: Zet het om naar 0 (want 1 + 1 levert een carry op) en ga naar links om het volgende bit te verwerken.
  • Als de machine links voorbij het meest linkse cijfer gaat (dus een blanco tegenkomt): Schrijf een 1 om de carry weer te geven en stop.

Het onderstaande toestandsdiagram probeert deze stappen weer te geven, maar mist een cruciale transitie. Identificeer de ontbrekende stap.

Turing-diagram met ontbrekende stap

Deze oefening maakt deel uit van de cursus

Concepten in de informatica

Cursus bekijken

Praktische interactieve oefening

Zet theorie om in actie met een van onze interactieve oefeningen.

Begin met trainen