CommencerCommencez gratuitement

Missing step in Turing Machine

We want to design a Turing Machine that adds 1 to a binary number. The machine processes the number from right to left, following these rules:

  • Start at the rightmost bit.
  • If the current bit is 0: Flip it to 1 and halt.
  • If the current bit is 1: Flip it to 0 (because 1 + 1 causes a carry) and move left to process the next bit.
  • If the machine moves left beyond the leftmost digit (i.e. encounters a blank): Write a 1 to represent the carried bit and halt.

The following state diagram attempts to capture these steps but is missing a critical transition. Identify the missing step.

Turing diagram with missing step

Cet exercice fait partie du cours

<cours>Concepts in Computer Science</cours>
Voir le cours

Exercice interactif pratique

Transformez la théorie en action avec l’un de nos exercices interactifs

Commencer l’exercice