Introducción a la máquina de Turing

Una máquina de Turing es un dispositivo receptor que acepta lenguajes (conjunto enumerado recursivamente) generados por gramáticas de tipo 0. Fue inventado en 1936 por Alan Turing.

Definición

Una máquina de Turing (TM) es un modelo matemático que consiste en una cinta de longitud infinita, dividida en celdas en las que se ingresan los datos. Consiste en un cabezal que lee la cinta de entrada. El registro estatal almacena el estado de la máquina de Turing. Una vez que se lee el carácter de entrada, se reemplaza por otro carácter, su estado interno cambia y se mueve de una celda a la derecha o la izquierda. Si la TM alcanza el estado final, se acepta la cadena de entrada; de lo contrario, se rechaza.

TM se puede describir formalmente como un conjunto de siete (Q, X, ∑, δ, q0, B, F), donde –

  • Q conjunto finito de estados

  • X alfabeto de cinta

  • ∑ este es el alfabeto de entrada

  • δ – función de transición; δ: Q × X → Q × X × {Shift Left, Shift Right}.

  • q0 este es el estado inicial

  • B es un personaje vacio

  • F este es un conjunto de estados finales

Comparación con la máquina anterior

La siguiente tabla muestra una comparación de cómo una máquina de Turing se diferencia de una máquina de estados finitos y una máquina de expulsión.

Auto Estructura de datos de pila Determinista?
Máquina de estados finitos N / A sí
Máquina de eyección Llegó el último, se fue el primero (LIFO) No
máquina de Turing Cinta sin fin sí

Un ejemplo de una máquina de Turing

Máquina de Turing M = (Q, X, ∑, δ, q0, B, F) con

  • Q = {q0, q1, q2, qf}
  • X = {a, b}
  • ∑ = {1}
  • q0 = {q0}
  • B = carácter vacío
  • F = {qf}

δ se define como –

Símbolo del alfabeto de cinta Estado actual ‘q0’ Estado actual ‘q1’ Estado actual ‘q2’
y 1Rq1 1Lq0 1lkf
B 1Lq2 1Rq1 1Rqf

Aquí la transición 1Rq1 significa que el carácter de escritura es 1, la cinta se mueve hacia la derecha y el siguiente estado es q1. Asimismo, una transición 1Lq2 implica que el carácter de escritura es 1, la cinta se mueve hacia la izquierda y el siguiente estado es q2.

Complejidad temporal y espacial de la máquina de Turing

Para una máquina de Turing, la complejidad del tiempo se refiere al número de movimientos de cinta cuando la máquina se inicializa para algunos caracteres de entrada y la complejidad del espacio se refiere al número de celdas de cinta escritas.

Complejidad del tiempo todas las funciones cuerdas –

T (n) = O (n log n)

Complejidad espacial de la MT –

S (n) = O (n)

🚫