Comece agoraComece grátis

Etapa ausente na Máquina de Turing

Queremos projetar uma Máquina de Turing que some 1 a um número binário. A máquina processa o número da direita para a esquerda, seguindo estas regras:

  • Comece no bit mais à direita.
  • Se o bit atual for 0: troque para 1 e pare.
  • Se o bit atual for 1: troque para 0 (porque 1 + 1 gera transporte) e mova para a esquerda para processar o próximo bit.
  • Se a máquina se mover para a esquerda além do dígito mais à esquerda (isto é, encontrar uma célula em branco): escreva 1 para representar o bit transportado e pare.

O diagrama de estados a seguir tenta capturar essas etapas, mas está faltando uma transição crítica. Identifique a etapa ausente.

Diagrama de Turing com etapa ausente

Este exercicio faz parte do curso

Conceitos em Ciência da Computação

Ver curso

exercicio interativo prático

Transforme teoria em prática com um dos nossos exercicio interativos

Iniciar exercicio