ComeçarComece de graça

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

Este exercício faz parte do curso

Concepts in Computer Science

Ver curso

Exercício interativo prático

Transforme a teoria em ação com um de nossos exercícios interativos

Começar o exercício