Vamos a suponer que en vez de tener una lista de instrucciones, vamos a tener un mecanismo que puede estar en distintos estados internos. Este mecanismo, en cada momento, estará examinando una casilla de una cinta infinita lineal. 

    La combinación del estado interno con el símbolo que se esté examinando en la cinta, da lugar a que la máquina ejecute una determinada acción. 
Estas acciones pueden ser: 

• Imprimir un símbolo   
• Pasar a examinar la casilla de la izquierda o de la derecha   

    Usaremos los símbolos q₁, q₂, q₃,... para representar los estados internos y los símbolos s₀, s₁, s₂,... para representar los símbolos que aparecen en la cinta, donde el símbolo s₀ representa un blanco, B. 

DEFINICION

    Por una cuádrupla entenderemos un conjunto ordenado de cuatro símbolos en el que el primer símbolo representa un estado interno, el segundo un símbolo leído en la cinta, el tercero una acción (L, R, o s_k representan respectivamente moverse a la izquierda, a la derecha o imprimir el símbolo s_k) y el cuarto, el estado al que se evoluciona. 

    Existen 3 tipos de cuádruplas, dependiendo de la acción que se ejecute, 

(1)   q_i s_j s_k q_i

(2) q_i s_j R q_i

(3) q_i s_j L q_i

DEFINICION

Una máquina de Turing se define como constituida por los siguientes elementos: 

• Un conjunto finito de estados, Q = {q₁, q₂,.., q_m}   
• Un estado inicial, q₁   
• Un alfabeto C = {s₁, s₂,..,s_n}   
• Un conjunto de cuádruplas, tales que no existen dos cuádruplas que empiecen por el mismo estado y el mismo símbolo. Es decir, una correspondencia biunívoca   

    Una máquina de Turing funciona de la siguiente forma.
Comienza en el estado inicial q₁ y con una cierta configuración en la cinta. De acuerdo con el símbolo observado en la cinta, ejecuta una acción y cambia de estado. Así va repitiendo esta misma operación hasta que en un momento dado, no exista ninguna cuádrupla en la máquina que empiece por el estado de la máquina y el símbolo observado. No hay ninguna acción definida para una configuración dada. En ese momento la máquina de Turing para. 

DEFINICION

    Con las mismas consideraciones respecto a la configuración inicial y final de la cinta se define el concepto de función parcial calculada por una máquina de Turing, M. 

    Análogamente, se dice que M calcula estrictamente una función parcial f definida en un conjunto de cadenas A si y solo si calcula f verificando, además 
 

• El alfabeto de M es un subconjunto de A.   
• Siempre que M pare, la configuración final tiene la forma   

donde "y" no contiene blancos 

EJEMPLO

Escribiendo s₀ = B, s₁ = 1, consideremos la siguiente máquina de Turing: 

• El conjunto de estados es {q₁, q₂, q₃}.   
• El estado inicial es q₁.   
• El alfabeto es {1}   
• Las cuádruplas son   

    Los distintos pasos del cálculo, en los que se muestra el estado de la máquina, los símbolos de la cinta y la casilla actual se llaman configuraciones. 

    A veces, es interesante y más claro dar las cuádruplas mediante una tabla de doble entrada en la que a cada estado y a cada símbolo examinado se le haga corresponder una acción y un estado. En el siguiente ejemplo se expresan las cuádruplas del ejemplo anterior.

EJEMPLO

    Otra representación que se suele dar en numerosas ocasiones es la de un grafo, en la que los nodos representan los estados y los arcos el símbolo examinado y la acción. Estos grafos se llaman diagramas de transición de estados. 

EJEMPLO
La siguiente máquina simple de Turing reconoce el conjunto de palabras de igual longitud sobre {a, b}. El diagrama de transición de estados para este dispositivo es: 

    Las transiciones entre estados están representadas por flechas etiquetadas por el símbolo que causa la transición. El símbolo que queda después del desplazamiento denota al carácter que va a ser impreso o, en caso de L y R, la dirección de movimiento de la cabeza de la cinta. El símbolo # denota el espacio en blanco B. 

TEOREMA

    Cualquier función parcial calculable por un programa Post-Turing puede calcularse por una máquina de Turing usando el mismo alfabeto. 

TEOREMA

    Sea f una función parcial de m variables parcialmente calculable definida en A para un alfabeto dado A. Entonces existe una máquina de Turing que calcula f estrictamente. 

DEFINICION

    A continuación veremos unas máquinas de Turing ligeramente distintas. En vez de tener cuádruplas que definan su funcionamiento, van a tener quíntuplas. Va a haber 2 tipos de quíntuplas: 

            q_i s_j s_k R q_i

            q_i s_j s_k L q_i

    La diferencia está en que estas máquinas de Turing, en cada paso, imprimen un símbolo y, entonces, se mueven hacia la derecha o hacia la izquierda. Es decir, realizan dos acciones, una de imprimir y otra de movimiento. Así, para cada par de estado y símbolo en la cinta, se especifica el símbolo que se imprime, s_k , el movimiento (L o R) y el nuevo estado q_i . A estas máquinas les llamaremos máquinas de Turing de quíntuplas. Se puede demostrar el siguiente teorema. 

TEOREMA

    Cualquier función que sea calculada por una máquina de Turing puede calcularse con una máquina de Turing de quíntuplas y usando el mismo alfabeto 

TEOREMA

    Cualquier función parcial que pueda calcularse mediante una máquina de Turing de quíntuplas puede calcularse mediante un programa Post-Turing, usando el mismo alfabeto. 

COROLARIO

    Para una función parcial dada, f, las siguientes condiciones son equivalentes: 

• f puede calcularse mediante un programa Post-Turing   
• f puede calcularse mediante una máquina de Turing   
• f puede calcularse mediante una máquina de Turing de quíntuplas   

DEFINICION

    Recordemos ahora la función parcialmente calculable F (x,z). Para un z fijo, F (x,z) es la función parcial de una variable calculada por el programa número z. Sea M la máquina de Turing que calcula esta función con el alfabeto {1}. A esta máquina de Turing le llamaremos máquina de Turing universal.

EJEMPLO

    Sea g(x) una función parcialmente calculable de una variable y sea z₀ el número de un programa P en el lenguaje Y que calcula g. Entonces, si comenzamos con la configuración 

B x B z₀
↓
q₁

donde x y z₀ están escritos como series de 1 (en notación unaria), y la máquina M comienza a calcular, M puede usarse para calcular cualquier función parcialmente calculable de una variable. 

DEFINICION

    Dada una máquina de Turing con alfabeto A = {s₁,..., s_n}, se dice que una palabra u Î A es aceptada por M, s M para cuando comienza con la configuración 

B u 
↓

q₁

    Es importante caracterizar los distintos lenguajes aceptados por los distintos tipos de máquinas o dispositivos. Este problema es fácil de resolver en las máquinas de Turing. 

TEOREMA

    Un lenguaje es aceptado por una máquina de Turing si y sólo si es recursivamente enumerable (r.e.) 

TEOREMA

 Un conjunto U de números es r.e. si y sólo si existe una máquina de Turing M con alfabeto {1} que acepta 1^(x) si y sólo si     x Î U

EJEMPLO

    Vamos a considerar ahora algunas ambigüedades que a veces resultan al hablar de conjuntos de cadena r.e. Por ejemplo, consideremos el lenguaje 

            L₀ = { a^{n} / n0 } 

sobre el alfabeto {a,b} 

Lo que ocurre aquí no es una excepción. De hecho ocurriría siempre. Esto es una consecuencia del primer teorema de este apartado. El que una cadena sea aceptada por una máquina de Turing es independiente del orden de los símbolos del alfabeto. Por tanto, podemos afirmar que el hecho de que un lenguaje particular sobre un alfabeto determinado sea r.e. es independiente del orden que exista en el alfabeto. 

  Lo mismo ocurre para los lenguajes recursivos. Ya que un lenguaje L sobre un alfabeto A, será recursivo si y sólo si los lenguajes L y A^* - L son ambos r.e. 

EJEMPLO

    Otra ambigüedad viene del hecho de que un lenguaje particular puede considerarse respecto a más de un alfabeto. Sea, por ejemplo, A un alfabeto de n letras y Ø A un alfabeto de m letras que contiene a A (mn). 

Un lenguaje L sobre el alfabeto es simplemente un subconjunto de A^*.
De esta forma, L será también un lenguaje sobre el alfabeto  ØA. 
De esta forma, dependiendo del alfabeto que se considere, veremos los elementos de L como cadenas representando números en base n o en base m.
En cada caso, estaremos considerando distintos conjuntos de números. Podría entonces darse el caso de que el hecho que un lenguaje L sea o no r.e. dependa del alfabeto considerado. 

De hecho, esta coincidencia va a ocurrir siempre como demuestra el siguiente teorema: 

TEOREMA

    Sea A ÍØ A donde A y Ø A son alfabetos y sea L Í A^*. Entonces L es recursivamente enumerable (r.e.) en el alfabeto A si y sólo si es r.e. en Ø A 

COROLARIO

    Sean A, Ø A y L como en el teorema anterior. Entonces L es un lenguaje recursivo en A si y sólo si es un lenguaje recursivo en Ø A 
 
 

    Vamos a demostrar en esta sección que el problema de la parada para una máquina de Turing M no tiene solución, es decir, no existe ningún algoritmo (expresado en cualquiera de las formas conocidas) para determinar cuando M parará cuando empiece con una entrada dada. 

TEOREMA

    Existe una máquina de Turing K con alfabeto {1} cuyo problema de la parada asociado es irresoluble (indecidible) 

EJEMPLO

    Sea K una máquina de Turing con alfabeto {1} que tiene un problema de parada asociado irresoluble. Sean los estados de K, q₁, ... , q_k. 
 

Podemos concluir entonces el siguiente teorema 

TEOREMA

    Existe una máquina de Turing K’ con alfabeto {1} y un estado q_m tal que no existe ningún algoritmo que pueda determinar si K’ alcanzará el estado q_m cuando comienza con una configuración dada. 

MÁQUINAS DE TURING NO DETERMINÍSTICAS
 

Las máquinas de Turing que hemos visto se llaman también determinísticas. 
Existe otro tipo de máquinas más generales llamadas no determinísticas.

La diferencia fundamental es que puede haber varias cuádruplas comenzando por la misma pareja de símbolo estado. De esta forma ante una configuración inicial pueden existir distintos cálculos posibles. No existe una única línea de cálculo. Dada una configuración la máquina puede evolucionar a distintas configuraciones. 

Análogamente a las máquinas determinísticas, diremos que una configuración 

... s_j ... 
 ↓

   q_i

es terminal si y sólo si no existe ninguna cuádrupla que comience por q_is_j. Cuando alcanza una configuración terminal, la máquina se dice que para. 

    Usaremos el símbolo |- entre un par de configuraciones para indicar que se puede pasar de una a otra mediante una cuádrupla (un paso de cálculo) 

EJEMPLO

    Consideremos la máquina de Turing no determinística compuesta por las siguientes cuádruplas 

           q₁ B R q₂

           q₂ 1 R q₃

           q₂ B B q₄

           q₃ 1 R q₂

           q₃ B B q₃

           q₄ B R q₄

           q₄ B B q₅
 

DEFINICION DE MÁQUINA DE TURING NO DETERMINISTICA.

    Sea A = {s₁,..., s_n} un alfabeto y sea u Î A^*. Entonces la máquina de Turing no determinística M se dice que acepta la cadena u si existe una sucesión de configuraciones g₁, g₂, ..., g_n tal que g₁ es la configuración 

s₀ u 
↓
q₁

g _m es terminal respecto a M y g ₁ |- g₂|- ... |- g _m

    En este caso, la sucesión g₁, g₂, ..., g_m se llama un cálculo de aceptación de M para u. 

    Si A es el alfabeto de M, entonces el lenguaje aceptado por M es el conjunto de todas las cadenas u ÎA^* que son aceptadas por M. 

    Claro está, para máquinas determinísticas esta definición es la misma de antes. 
Sin embargo, es importante hacer notar que en las máquinas de Turing no determinísticas es posible que una cadena u sea aceptada, aunque sea posible tener una sucesión infinita de configuraciones 

g ₁ |- g₂ |- g ₃ |- ... 

siendo la primera configuración 

s₀ u 
↓
q₁

    Es solo necesario que una de las posibles sucesiones de cálculo conduzca a una configuración terminal. Esto se expresa, a veces, diciendo que "la máquina puede adivinar en cualquier momento el paso correcto entre todos los posibles" 

EJEMPLO

    En el ejemplo anterior, considerando el alfabeto A= {1}, resulta que M acepta la cadena 1111. De hecho, el lenguaje aceptado por M es {1^{2n}} 

    Como una máquina de Turing es también no determinística, podemos enunciar el siguiente teorema 

TEOREMA

    Para todo lenguaje L recursivamente enumerable existe una máquina de Turing M no determinística que acepta el lenguaje L. 

    La propiedad inversa es también cierta. Todo lenguaje aceptado por una máquina de Turing no determinística será también r.e. . Por la tesis de Church-Turing esto debería ser cierto. Sólo es necesario simular una máquina no determinística M para una entrada u, siguiendo todas las alternativas en cada paso, y dando un valor (por ejemplo 0) si se alcanza una configuración terminal en una de las posibles ramas. Esto define una función que es intuitivamente parcialmente calculable y cuyo dominio es el lenguaje aceptado por M. 
 
 

MÁQUINAS DE TURING MODIFICADAS
 
 

    En los programas de Post-Turing y en las máquinas de Turing ya sean de cuádruplas o quíntuplas hemos supuesto que la memoria estaba constituida por una única cinta ilimitada en ambas direcciones. Sin embargo se podrían suponer otros dispositivos de memoria. Por ejemplo, en la formulación original de Turing se consideraba que la cinta era infinita en una única dirección, estando acotada por la derecha: 
 

    Vamos a comenzar considerando las máquinas de Turing con cinta ilimitada en una sola dirección. Para concretar vamos a suponer que cuando la máquina esté posicionada en la casilla más a la izquierda y haya que moverse a la izquierda, entonces la máquina para. 

    Es evidente que todo lo que se pueda hacer en estas máquinas se puede hacer en una máquina de Turing. El problema está en determinar si este tipo de cintas limita la capacidad de cálculo. La realidad es que no es así. De hecho, Turing dio su modelo original con este tipo de cintas. 

    Vamos a indicar la idea de la demostración. Esta se basa en representar el contenido de una cinta infinita bidireccional mediante una cinta unidireccional con dos pistas, dos filas de símbolos. Es decir, los símbolos que se escriben en la cinta unidireccional van a ser parejas de símbolos de la bidireccional. 

EJEMPLO

    Supongamos que tenemos la cinta:

    De forma más precisa, sea M una máquina de Turing con alfabeto {s₁, ...,s₂} y estados q₁, ..., q_k. Supongamos que M calcula la función unaria g en A₀^*, donde A₀Î A. Cuando en esta máquina estamos calculando g(x) la configuración inicial de la cinta bidireccional será 

B x 
↓
q₁

 A continuación construiremos una máquina de Turing ØM que calcule g con una cinta unidireccional 

    En lugar de dar las cuádruplas que realizarían esta tarea, vamos a dar un programa Post-Turing que realiza el mismo efecto y que podría traducirse posteriormente a cuádruplas. 

• Al hacer esta descomposición los símbolos blancos de la cinta doble se traducirán por #, para no interferir las macros que usamos.
• Posteriormente, todos los # se pasan a los blancos.

[D]    RIGHT TO NEXT BLANK 

          MOVE BLOCK RIGHT 

          RIGHT 

[C]    RIGHT 

          IF b_jⁱ GOTO A_jⁱ (0 <= i, j <= n) 

          IF B GOTO f 

          GOTO C 

[A_jⁱ]    PRINT s_i (0 < i <= n , 0 <= j<=n) 

          GOTO B_j

[A_j⁰]   PRINT # ( 0 < j <=n ) 

           GOTO B_j

[B_j]     LEFT TO NEXT BLANK ( 0 < j <= n ) 

           PRINT s_j

           GOTO D 

[B₀]    LEFT TO NEXT BLANK 

           PRINT # 

           GOTO D 

[F]      LEFT 

           IF s_j GOTO F ( 0< j <= n ) 

           IF # GOTO G 

           IF B GOTO E 

[G]      PRINT B 

           GOTO F 
 

Cada b_jⁱ se procesa de izquierda a derecha.

b_jⁱ se reemplaza por s_i (o por # si i=0) y s_j (o # si j=0) a su izquierda.

La macro MOVE BLOCK RIGHT se usa para hacer espacio para imprimir los símbolos de la pista inferior 

EJEMPLO

    Consideremos como actúa el programa anterior sobre la configuración 

B b₁² b₁⁰ b₀¹
↓

    A continuación se muestran distintas configuraciones por las que va pasando la cinta, junto con las etiquetas de las siguientes instrucciones que han de ejecutarse en cada caso. 

B b₁² b₁⁰ b₀¹                               D 
↓

B B b₁² b₁⁰ b₀¹ B                        C 
↓

B B b₁² b₁⁰ b₀¹ B                        A₁²
↓

B B s₂ b₁⁰ b₀¹ B                          B₁
     ↓

B s₁ s₂ b₁⁰ b₀¹ B                         D 
   ↓

B B s₁ s₂ b₁⁰ b₀¹ B                     A₁⁰
          ↓

B s₁ s₁ s₂ # b₀¹ B                        D 
↓

B # s₁ s₁ s₂ # s₁ B                       D 
  ↓

B B # s₁ s₁ s₂ # s₁ B                    F 
           ↓

B B B s₁ s₁ s₂ B s₁ B                    E 
↓

    La técnica de pensar en la cinta de una máquina de Turing como descomponible en varias pistas paralelas tiene numerosos usos. Por ejemplo, se podría usar para simular máquinas de Turing con múltiples cintas y cabezas de lectura independientes para cada una de ellas. Si tenemos una máquina con k cintas, se puede considerar una máquina de Turing con 2k pistas. En ellas se contienen los símbolos de las k cintas, y para cada una de las k cintas, habrá una pista que contendrá la posición de la cabeza de lectura - escritura en dicha cinta (por ejemplo, esta pista puede tener todos los símbolos blancos, menos en la casilla activa, en la que contendrá un uno). De esta forma, se puede simular una máquina con k cintas mediante una máquina de Turing con una sola cinta