Turing describió por primera vez la máquina de Turing en un artículo publicado en 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem” que apareció en Proceedings of the London Mathematical Society.
La cabeza y la cinta
Una máquina de Turing es un dispositivo informático idealizado que consta de un cabezal de lectura/escritura (o “escáner”) con una cinta de papel que lo atraviesa. La cinta se divide en cuadrados, cada uno de los cuales tiene un solo símbolo: ‘0’ o ‘1’, por ejemplo.
Esta cinta es el medio de almacenamiento de propósito general de la máquina, sirviendo como vehículo para la entrada y salida y como memoria de trabajo para almacenar los resultados de los pasos intermedios del cálculo.
La entrada que se inscribe en la cinta antes de que comience el cálculo debe constar de un número finito de símbolos. Sin embargo, la cinta tiene una longitud ilimitada, ya que el objetivo de Turing era mostrar que hay tareas que estas máquinas no pueden realizar, incluso con una memoria de trabajo ilimitada y un tiempo ilimitado.
El cabezal de lectura/escritura es programable. Es útil pensar en la operación de programación como si consistiera en alterar el cableado interno del cabezal por medio de un arreglo de clavijero. Para calcular con el dispositivo, lo programa, inscribe la entrada en la cinta (en código binario o decimal, digamos), coloca la cabeza sobre el cuadrado que contiene el símbolo de entrada más a la izquierda y pone la máquina en movimiento. Una vez que se completa el cálculo, la máquina se detendrá con la cabeza colocada sobre el cuadrado que contiene el símbolo más a la izquierda de la salida (o en otro lugar si así se programa).
Estados
La cabeza contiene un subdispositivo que llamo el indicador . Esta es una segunda forma de memoria de trabajo. El indicador se puede configurar en cualquiera de varias ‘posiciones’. En la jerga de la máquina de Turing, la posición del indicador en cualquier momento se denomina estado de la máquina en ese momento. Para dar un ejemplo simple de la función del indicador, se puede utilizar para realizar un seguimiento de si el último símbolo encontrado fue ‘0’ o ‘1’. Si ‘0’, el indicador se establece en su primera posición, y si ‘1’, en su segunda posición.
Operaciones atómicas
Hay solo seis tipos de operaciones fundamentales que realiza una máquina de Turing en el curso de un cálculo. Puede:
- leer (es decir, identificar) el símbolo actualmente debajo de la cabeza
- escriba un símbolo en el cuadrado actualmente debajo de la cabeza (después de eliminar primero el símbolo que ya está escrito allí, si corresponde)
- mover la cinta a la izquierda un cuadrado
- mueve la cinta un cuadrado a la derecha
- cambian de estado
- detener.
Éstas se denominan operaciones primitivas o atómicas de la máquina. Un cálculo complicado puede consistir en cientos de miles, o incluso millones, de ocurrencias de estos átomos.
Las computadoras disponibles comercialmente están cableadas para realizar operaciones primitivas considerablemente más sofisticadas que las de una máquina de Turing: sumar, multiplicar, decrementar, almacenar en la dirección, bifurcar, etc. La constitución precisa de la lista de primitivas varía de un fabricante a otro. Es un hecho notable que ninguna de estas computadoras puede superar a una máquina de Turing. A pesar de la austera simplicidad de la máquina de Turing, es capaz de computar cualquier cosa que pueda computar cualquier computadora en el mercado.
De hecho, dado que es una máquina abstracta o nocional, una máquina de Turing puede calcular más que cualquier computadora física. Esto se debe a que (1) la computadora física tiene acceso solo a una cantidad limitada de memoria y (2) la velocidad de operación de la computadora física está limitada por varias restricciones del mundo real.
A veces se dice, incorrectamente, que una máquina de Turing es necesariamente lenta, ya que la cabeza se mueve continuamente hacia adelante y hacia atrás, un cuadrado a la vez, a lo largo de una cinta de longitud ilimitada. Pero dado que una máquina de Turing es un dispositivo idealizado, no tiene restricciones del mundo real en su velocidad de operación.
La tabla de instrucciones
Un programa o “tabla de instrucciones” para una máquina de Turing es una colección finita de instrucciones, cada una de las cuales requiere que se realicen ciertas operaciones atómicas si se cumplen ciertas condiciones. Toda instrucción es de la forma:
Si el estado actual es n y el símbolo actualmente debajo del encabezado es x, entonces escriba y en el cuadrado actualmente debajo del encabezado [y puede ser idéntico a x], pase al estado m [m puede ser n] y – – – .
En lugar de – – – puede escribirse ‘mover a la izquierda un cuadrado’ o ‘mover a la derecha un cuadrado’ o ‘detener’.
Un ejemplo
La máquina de este ejemplo comienza a trabajar con una cinta en blanco. La cinta es interminable. El problema es configurar la máquina de modo que si el escáner se coloca sobre cualquier cuadrado y la máquina se pone en movimiento, imprimirá dígitos binarios alternos en su cinta, 0 1 0 1 0 1…, trabajando hacia la derecha desde su lugar de inicio, y dejando un cuadrado en blanco entre cada dígito.
Para realizar su trabajo, la máquina utiliza cuatro estados, denominados ‘ a ‘, ‘ b ‘, ‘ c ‘ y ‘ d ‘. La máquina está en el estado a cuando comienza a funcionar.
La tabla de instrucciones para esta máquina es la siguiente. La línea superior de la tabla dice: si está en el estado a y el cuadrado que está escaneando está en blanco, imprima 0 en el cuadrado escaneado, muévase un cuadrado a la derecha y pase al estado segundo _
| EXPRESAR | SÍMBOLO ESCANEADO | IMPRIMIR | MOVERSE | SIGUIENTE ESTADO |
|---|---|---|---|---|
| un | espacio en blanco | 0 | R | b |
| b | espacio en blanco | R | C | |
| C | espacio en blanco | 1 | R | d |
| d | espacio en blanco | R | un |
Una máquina que actúa de acuerdo con esta tabla de instrucciones trabaja incansablemente, imprimiendo la secuencia deseada de dígitos y dejando casillas alternas en blanco.
Máquinas de Turing universales
De hecho, hay dos formas de disponer que una máquina de Turing actúe de acuerdo con una tabla o programa de máquina. Una, como ya se mencionó, es modificar apropiadamente el ‘cableado’ en la cabeza de una máquina de Turing. La otra es traducir la tabla de la máquina a, digamos, código binario e inscribir el resultado en la cinta de un tipo especial de máquina de Turing conocida como máquina de Turing universal .
Turing pudo demostrar que existe una tabla U tal que si la cabeza de una máquina de Turing se programa de acuerdo con U, y si cualquier tabla, P, se traduce y se escribe en la cinta de la máquina, entonces la máquina se comportará como si su cabeza hubiera sido programada de acuerdo con P. Una máquina de Turing universal es cualquier máquina de Turing cuya cabeza haya sido programada de acuerdo con U.
Hay muchas tablas diferentes que harán el trabajo de U y, por lo tanto, muchas máquinas de Turing universales distintas, todas equivalentes en potencia computacional. La mesa más económica de este tipo se debe a Marvin Minsky. ¡Usando un alfabeto de cuatro símbolos y haciendo uso de solo siete estados, esta tabla consta de solo 28 instrucciones!
La mayor contribución de Turing al desarrollo de la computadora digital fueron
- esta idea de controlar la función de una máquina de computación almacenando un programa de instrucciones codificadas simbólica o numéricamente en la memoria de la máquina, y
- su prueba de que, por este medio, una sola máquina -una máquina universal- es capaz de realizar todos los cálculos que puede realizar cualquier otra máquina de Turing.
Números computables
Se dice que un programa de máquina de Turing termina en caso de que cualquier máquina de Turing que ejecute el programa se detenga sin importar la entrada. Una manera fácil de escribir un programa que no termine es simplemente omitir una instrucción para detener. En el mundo real, los programas de computadora que nunca terminan por diseño son comunes. Los sistemas de control de tráfico aéreo, las redes de cajeros automáticos y los sistemas de control de reactores nucleares son ejemplos de ello.
Un ejemplo de un programa de máquina de Turing sin terminación es un programa que calcula secuencialmente cada dígito de la representación decimal de pi (por ejemplo, usando una de las expresiones estándar de series de potencias para pi). Una máquina de Turing que ejecute este programa pasará toda la eternidad escribiendo la representación decimal de pi dígito por dígito, 3.14159. . .
Turing llamó a los números que pueden ser escritos por una máquina de Turing los números computables . Es decir, un número es computable, en el sentido de Turing, si y sólo si existe una máquina de Turing que calcule en secuencia cada dígito de la representación decimal del número.
Números no computables
Inmediatamente, uno podría esperar que todo número que tenga una representación decimal, ya sea finita o infinita, es decir, todo número real , sea computable. (Los números reales comprenden los números enteros, los números racionales, es decir, los números que pueden expresarse como una razón de números enteros, por ejemplo, 1/2 y 3/4, y los números irracionales, por ejemplo, la raíz cuadrada de 2 y pi, que no puede expresarse como una razón de números enteros). Porque, ¿qué podría evitar que haya, para cualquier número real en particular, una máquina de Turing que ‘produzca en masa’ la representación decimal de ese número dígito por dígito?
Sin embargo, Turing pudo demostrar que no todos los números reales son computables. Las representaciones decimales de algunos números reales están tan completamente desprovistas de patrón que simplemente no existe una tabla finita de instrucciones del tipo que pueda seguir una máquina de Turing para calcular el enésimo dígito de la representación, para n arbitrario.
De hecho, los números computables son relativamente escasos entre los números reales. Solo hay muchos números computables contables, mientras que, como demostró el matemático Georg Cantor en 1874, hay muchos números reales incontables. (Un conjunto es contable si y solo si es finito o sus miembros se pueden poner en una correspondencia uno a uno con los números enteros).
Funciones computables y no computables
Siguiendo a Turing, decir que una función matemática , por ejemplo la suma de los números enteros, es computable es decir que hay una máquina de Turing tal que si, para cualquier par de números enteros x e y, la máquina tiene x e y como entrada, imprimirá el valor de x+y y se detendrá.
La suma de números enteros es una función computable, mientras que la suma de números reales no es una función computable. Esto se debe a que ni siquiera hay forma de inscribir las entradas xey en la cinta de una máquina de Turing si xey son números no computables. (Recuerde que la entrada debe constar de un número finito de símbolos).
¿Es la suma sobre los números computables una función computable? Es decir, ¿es x+y computable siempre que x e y sean ambos números computables?
La respuesta es sí , pero en la parte superior de la cabeza uno podría pensar lo contrario, porque si x (o y) es un número computable que tiene una representación decimal infinita, por ejemplo ¹, ¿cómo se puede ingresar x, dada la restricción de que la entrada inscrito en la cinta debe constar de un número finito de símbolos? La solución es ingresar x en forma de programa . El número computable x puede representarse por medio de un programa que, si se inscribe en la cinta (de otro modo en blanco) de alguna máquina de Turing universal en particular, haría que la máquina universal calculara la representación decimal de x dígito por dígito.
Así Turing nos ha dado un nuevo método para representar números. En este sistema hay representaciones finitas de algunos números que, en el sistema decimal, sólo pueden representarse mediante una secuencia infinita de símbolos.