EmpezarEmpieza gratis

Paso que falta en la Máquina de Turing

Queremos diseñar una Máquina de Turing que sume 1 a un número binario. La máquina procesa el número de derecha a izquierda, siguiendo estas reglas:

  • Comienza en el bit más a la derecha.
  • Si el bit actual es 0: cámbialo a 1 y detente.
  • Si el bit actual es 1: cámbialo a 0 (porque 1 + 1 produce un acarreo) y muévete a la izquierda para procesar el siguiente bit.
  • Si la máquina se mueve a la izquierda más allá del dígito más a la izquierda (es decir, encuentra un blanco): escribe un 1 para representar el bit acarreado y detente.

El siguiente diagrama de estados intenta reflejar estos pasos, pero le falta una transición crítica. Identifica el paso que falta.

Diagrama de Turing con un paso faltante

Este ejercicio forma parte del curso

Conceptos de informática

Ver curso

ejercicio interactivo práctico

Convierte la teoría en práctica con uno de nuestros ejercicios interactivos

Empezar ejercicio