máquina de turing (Turing machine)

Una máquina de Turing es un modelo matemático de computación que describe una máquina abstracta que manipula símbolos en una tira de cinta de acuerdo con una tabla de...

Una máquina de Turing representa un modelo computacional matemático, conceptualizando un dispositivo abstracto que procesa símbolos en una cinta basándose en un conjunto predefinido de reglas. A pesar de su simplicidad inherente, este modelo posee la capacidad de ejecutar cualquier algoritmo informático imaginable.

Una máquina de Turing es un modelo matemático de computación que describe una máquina abstracta que manipula símbolos en una tira de cinta de acuerdo con una tabla de reglas. A pesar de la simplicidad del modelo, es capaz de implementar cualquier algoritmo informático.

Este dispositivo computacional funciona utilizando una cinta de memoria infinitamente larga, segmentada en distintas celdas. Cada celda es capaz de almacenar un único símbolo, seleccionado de una colección finita conocida como alfabeto de la máquina. La máquina incorpora un "cabezal" que, durante cualquier fase operativa, se sitúa sobre una de estas células, junto a un "estado" elegido entre un conjunto finito de estados posibles. En cada ciclo operativo, el cabezal lee el símbolo presente en su celda actual. Posteriormente, dependiendo del símbolo leído y del estado actual de la máquina, la máquina escribe un nuevo símbolo en la misma celda, desplaza el cabezal una posición hacia la izquierda o hacia la derecha o finaliza el cálculo. La determinación del símbolo a escribir, la dirección del movimiento de la cabeza y la decisión de detenerse se rigen por una tabla de transición finita, que dicta la acción apropiada para cada combinación del estado actual y el símbolo que se está leyendo. De manera análoga a los programas informáticos prácticos, una máquina de Turing puede entrar en un bucle infinito, evitando su terminación.

Alan Turing concibió la máquina de Turing en 1936, inicialmente refiriéndose a ella como una "máquina a" (máquina automática). Posteriormente, su director de doctorado, Alonzo Church, introdujo la nomenclatura "máquina de Turing" en una revisión. A través del desarrollo de este modelo, Turing logró proporcionar respuestas negativas a dos preguntas importantes:

¿Es posible construir una máquina capaz de determinar si una máquina arbitraria representada en su cinta muestra un comportamiento "circular", como congelarse o no completar su proceso computacional?
¿Se puede idear una máquina que determine si cualquier máquina arbitraria, codificada en su cinta, alguna vez generará un símbolo específico?

Al proporcionar una descripción matemática de un dispositivo notablemente simple capaz de realizar cálculos arbitrarios, Turing estableció propiedades fundamentales de la computación en términos generales, demostrando específicamente la incomputabilidad del Entscheidungsproblem, también conocido como el "problema de decisión" (la cuestión de si cada afirmación matemática puede ser probada o refutada).

Las máquinas de Turing demostraron de manera concluyente las limitaciones inherentes que gobiernan las capacidades de la computación. computación.

Aunque las máquinas de Turing son teóricamente capaces de representar cualquier cálculo, su arquitectura minimalista las hace poco prácticas para los requisitos de velocidad computacional del mundo real. Las computadoras contemporáneas, por el contrario, emplean diseños distintos, incorporando notablemente memoria de acceso aleatorio, que difiere del modelo de acceso secuencial de las máquinas de Turing.

La integridad de Turing se refiere a la capacidad de un modelo computacional o un conjunto de instrucciones para emular las operaciones de una máquina de Turing. Un lenguaje de programación que muestre la integridad de Turing es, en principio, capaz de articular todas las tareas que las computadoras pueden realizar; la mayoría de los lenguajes de programación logran la integridad de Turing cuando se ignoran restricciones prácticas como la memoria finita.

Descripción general

Una máquina de Turing sirve como una representación idealizada de una unidad central de procesamiento (CPU), que gobierna toda la manipulación de datos dentro de una computadora. El modelo canónico emplea memoria secuencial para el almacenamiento de datos, normalmente conceptualizada como una cinta infinitamente larga sobre la cual la máquina ejecuta operaciones de lectura y escritura.

Dentro del dominio de la teoría del lenguaje formal, una máquina de Turing (o autómata) posee la capacidad de enumerar un subconjunto arbitrario de cadenas válidas de un alfabeto determinado. Una colección de cadenas enumerables mediante este método se designa como lenguaje enumerable recursivamente. Alternativamente, una máquina de Turing puede conceptualizarse como un modelo diseñado para reconocer cadenas de entrada válidas, en lugar de simplemente enumerar cadenas de salida.

Considerando una máquina de Turing M y una cadena arbitraria s, generalmente es indecidible si M generará en última instancia s. Esta indecidibilidad surge de la insolubilidad inherente del problema de la detención, un fenómeno con profundas implicaciones para los límites teóricos de la computación.

Una máquina de Turing capaz de simular cualquier otra máquina de Turing se denomina máquina de Turing universal (UTM), o simplemente máquina universal. Al mismo tiempo, Alonzo Church introdujo el cálculo lambda, otro formalismo matemático que exhibe una característica "universal" comparable. Las contribuciones de Church, combinadas con las de Turing, establecieron las bases para la tesis de Church-Turing. Esta tesis postula que las máquinas de Turing, el cálculo lambda y formalismos computacionales análogos encapsulan con precisión el concepto informal de métodos efectivos en lógica y matemáticas. En consecuencia, ofrecen un modelo matemáticamente preciso para analizar algoritmos o "procedimientos mecánicos", independiente de cualquier formalismo específico. La investigación sobre los atributos abstractos de las máquinas de Turing ha avanzado significativamente en la comprensión de la informática, la teoría de la computabilidad y la teoría de la complejidad.

Concepción física

En su ensayo de 1948, "Maquinaria inteligente", Turing describió su máquina como compuesta por:

...una capacidad de memoria ilimitada, realizada como una cinta infinita segmentada en cuadrados, cada uno capaz de contener un símbolo impreso. En un momento dado, la máquina contiene un único símbolo, denominado símbolo escaneado. La máquina puede modificar este símbolo escaneado y su comportamiento operativo está parcialmente dictado por él; sin embargo, los símbolos ubicados en otras partes de la cinta no influyen en las acciones inmediatas de la máquina. Sin embargo, la cinta puede desplazarse bidireccionalmente a través de la máquina, constituyendo una de sus operaciones fundamentales. En consecuencia, eventualmente se puede acceder y procesar cualquier símbolo en la cinta.

Descripción operativa

La máquina de Turing proporciona un modelo matemático para un dispositivo que manipula mecánicamente una cinta. Esta cinta contiene símbolos que el cabezal de cinta de la máquina puede leer y escribir secuencialmente. Su funcionamiento se rige enteramente por un conjunto finito de instrucciones elementales, por ejemplo: "en el estado 42, si el símbolo observado es 0, escribe un 1; si el símbolo observado es 1, pasa al estado 17; en el estado 17, si el símbolo observado es 0, escribe un 1 y pasa al estado 6", y así sucesivamente. En su artículo fundamental, "Sobre números computables, con una aplicación al Entscheidungsproblem", Turing no conceptualizó un aparato mecánico, sino una "computadora" humana que ejecuta diligentemente estas reglas mecánicas deterministas (o, como lo describió Turing, "de manera inconexa").

Más precisamente, una máquina de Turing consta de los siguientes componentes:

Una cinta, segmentada en celdas contiguas. Cada celda almacena un símbolo extraído de un alfabeto finito. Este alfabeto incluye un símbolo en blanco designado (representado aquí como '0') y al menos otro símbolo. Se supone que la cinta es infinitamente extensible tanto en dirección izquierda como derecha, lo que garantiza que la máquina de Turing siempre tenga suficiente cinta para sus requisitos computacionales. Se supone que las celdas no escritas contienen el símbolo en blanco. Ciertos modelos cuentan con una cinta con un marcador de límite izquierdo distintivo, que se extiende o es extensible indefinidamente solo hacia la derecha.
Una cabeza, capaz de leer y escribir símbolos en la cinta y mover la cinta con precisión una celda a la vez, ya sea hacia la izquierda o hacia la derecha. En modelos alternativos, el propio cabezal se mueve mientras la cinta permanece fija.
Un registro de estado, que retiene el estado actual de la máquina de Turing a partir de un conjunto finito de estados posibles. Este conjunto incluye un estado de inicio específico, que se utiliza para inicializar el registro de estado. Turing señaló que estos estados sirven como un sustituto formal del "estado mental" que normalmente experimentaría una computadora humana durante los cálculos.
Una tabla finita de instrucciones que, basándose en el estado actual de la máquina (q_i) y el símbolo (a_j) que se lee de la cinta (es decir, el símbolo debajo del encabezado), dirige a la máquina a realizar las acciones subsiguientes en secuencia (específicamente para 5 tuplas). modelos):

Para borrar o escribir un símbolo (sustituyendo a_j por a_j1).
Para mover la cabeza (representado por d_k, con valores posibles: 'L' para un solo paso hacia la izquierda, o 'R' para un solo paso hacia la derecha, o 'N' para permanecer estacionario).
Para realizar la transición al mismo estado o a un nuevo según lo especificado (es decir, proceder al estado q_i1).

Dentro de los modelos de 4 tuplas, las operaciones de borrar o escribir un símbolo (a_j1) y mover la cabeza hacia la izquierda o hacia la derecha (d_k) se definen como instrucciones distintas. La tabla operativa de la máquina dicta que debe (ia) borrar o escribir un símbolo o, o (ib) mover el cabezal hacia la izquierda o hacia la derecha, y posteriormente (ii) realizar la transición a un estado nuevo o existente específico. Fundamentalmente, las acciones (ia) y (ib) no pueden ejecutarse dentro de la misma instrucción. Ciertos modelos especifican que la máquina se detendrá si no existe ninguna entrada en la tabla para la combinación actual de símbolo y estado; por el contrario, otros modelos exigen que todas esas entradas se definan de manera integral.

Cada componente de la máquina, que abarca su estado, colecciones de símbolos y la porción utilizada de la cinta en un momento dado, junto con sus operaciones (por ejemplo, impresión, borrado y movimiento de la cinta), es inherentemente finito, discreto y distinguible. Sin embargo, la capacidad de la máquina para un espacio de almacenamiento ilimitado surge de la cinta y el tiempo de ejecución teóricamente ilimitados disponibles.

Definición formal

De acuerdo con la formulación de Hopcroft & Ullman (1979), una máquina de Turing de cinta única se define formalmente como una tupla de 7: $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ 41§ , F ⟩ {\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle } donde

$\Gamma$ representa un conjunto finito y no vacío de símbolos alfabéticos de cinta.
$b\in \Gamma$ denota el símbolo en blanco, que es el único símbolo al que se le permite aparecer infinitas veces en la cinta en cualquier etapa de la cálculo.
$\Sigma \subseteq \Gamma \setminus \{b\}$ representa el conjunto de símbolos de entrada, específicamente aquellos símbolos permitidos en la configuración inicial de la cinta.
$Q$ se define como un conjunto finito y no vacío de estados.
$q_{0}\in Q$ 11§ ∈ Q {\displaystyle q_{0}\in Q} designa el estado inicial.
$F\subseteq Q$ constituye el conjunto de estados finales, también conocidos como estados de aceptación. El contenido inicial de la cinta se considera aceptado por $M$ si la máquina finalmente se detiene en un estado que pertenece a $F$ .
La expresión $\delta :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}$ representa la función parcial conocida como función de transición, donde 'L' denota un desplazamiento hacia la izquierda y 'R' significa un desplazamiento hacia la derecha. Debería $\delta$ carece de definición para el estado actual y el símbolo de la cinta, la máquina dejará de funcionar. Conceptualmente, esta función de transición dicta el estado posterior al actual, el símbolo que reemplazará al símbolo actual debajo de la cabeza y la dirección del siguiente movimiento de la cabeza.

Una configuración alternativa permite una operación "sin desplazamiento", designada como 'N', que funciona como un tercer elemento dentro del conjunto de movimientos direccionales $\{L,R\}$ .

La especificación de 7 tuplas para el castor ocupado de 3 estados se presenta de la siguiente manera:

$Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}$ (que representa el conjunto de estados);
$\Gamma =\{0,1\}$ 14§ , §1718§ } {\displaystyle \Gamma =\{0,1\}} (que indica los símbolos del alfabeto de la cinta);
$b=0$ 11§ {\displaystyle b=0} (identificando el símbolo en blanco);
$\Sigma =\{1\}$ 14§ } {\displaystyle \Sigma =\{1\}} (especificando los símbolos de entrada);
$q_{0}={\mbox{A}}$ 11§ = A {\displaystyle q_{0}={\mbox{A}}} (que designa el estado inicial);
$F=\{{\mbox{HALT}}\}$ (que comprende los estados finales);
$\delta =$ (la función de transición, detallada en la tabla de estado posterior).

Inicialmente, cada celda de la cinta está designada con el símbolo $§6$ 7§ {\displaystyle 0} .

Se necesitan más especificaciones para la visualización o implementación práctica de las máquinas de Turing.

Según van Emde Boas (1990), "El objeto teórico de conjuntos [su descripción formal de siete tuplas similar a la anterior] proporciona sólo información parcial sobre cómo se comportará la máquina y cómo serán sus cálculos".

Por ejemplo,

Se deben tomar numerosas decisiones con respecto a la representación visual de los símbolos y el desarrollo de un mecanismo robusto para su lectura y escritura indefinidas.
Si bien las operaciones de desplazamiento hacia la izquierda y hacia la derecha mueven conceptualmente el cabezal de la cinta a través de la cinta, un enfoque más pragmático para construir una máquina de Turing física implica que la cinta se mueva bidireccionalmente debajo de un cabezal estacionario.
La cinta se puede conceptualizar como finita y se extiende automáticamente con símbolos en blanco según sea necesario, lo que se alinea estrechamente con la definición matemática. Sin embargo, una perspectiva más predominante considera que la cinta se extiende infinitamente en una o ambas direcciones, precargada con espacios en blanco excepto el segmento finito que actualmente está debajo del cabezal de la cinta (un concepto que no se puede implementar en la práctica). Fundamentalmente, la longitud de la cinta no puede fijarse, ya que esto se desviaría de la definición establecida y restringiría gravemente las capacidades computacionales de la máquina. Tal limitación reduciría su potencia a la de un autómata lineal limitado si el tamaño de la cinta fuera proporcional a la entrada, o a una máquina de estados finitos si su longitud estuviera estrictamente predeterminada.

Definiciones alternativas

Ocasionalmente aparecen variaciones en las definiciones en la literatura académica, normalmente para simplificar los argumentos o mejorar la claridad de las pruebas. Estas modificaciones se implementan consistentemente sin alterar el poder computacional fundamental de la máquina resultante. Por ejemplo, el conjunto de posibles movimientos del cabezal de la cinta podría ampliarse desde $\{L,R\}$ para incluir $\{L,R,N\}$ , donde N (que representa "Ninguno" o "Sin operación") permite que la máquina permanezca en su celda de cinta actual en lugar de moverse hacia la izquierda o hacia la derecha. Tal alteración no aumenta la capacidad computacional inherente de la máquina.

De acuerdo con la convención establecida por Turing (1936) y Davis (2000), el enfoque más frecuente define cada "instrucción de Turing" dentro de una "tabla de Turing" como una de nueve 5 tuplas distintas.

(Definición 1): (q_i, S_j, S_k/E/N, L/R/N, q_m)

( estado actual q_i , símbolo escaneado S_j , símbolo para imprimir S_k/borrar E/sin operación N , movimiento de cinta izquierda L/derecha R/sin movimiento N , estado posterior q_m )

En contraste, otros académicos, incluidos Minsky (1967), Hopcroft y Ullman (1979) y Stone (1972), emplean una convención alternativa donde el nuevo estado q_m se coloca directamente después del símbolo escaneado S_j.

(Definición 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

( estado actual q_i , símbolo escaneado S_j , estado posterior q_m , símbolo para imprimir S_k/borrar E/sin operación N , movimiento de la cinta izquierda L/derecha R/sin movimiento N )

A lo largo del resto de este artículo, se empleará consistentemente la "Definición 1", que se alinea con la convención de Turing/Davis.

En la tabla siguiente, el modelo inicial de Turing incorporó sólo los primeros tres tipos de instrucciones, que designó N1, N2 y N3. Facilitó el borrado del "cuadrado escaneado" definiendo un símbolo 0, S₀, como "borrar" o "en blanco". Sin embargo, su marco original no permitía operaciones que no fueran de impresión, lo que significaba que cada línea de instrucción exigía "imprimir el símbolo S_k" o "borrar". Las abreviaturas utilizadas son las introducidas por Turing. Tras la publicación del artículo fundamental de Turing en 1936-1937, los modelos de máquinas posteriores se ampliaron para dar cabida a los nueve tipos potenciales de cinco tuplas.

Cualquier tabla de Turing, que constituya una lista completa de instrucciones, se puede formular utilizando las nueve 5-tuplas antes mencionadas. Por consideraciones técnicas específicas, las tres instrucciones no imprimibles o "N" (tipos 4, 5 y 6) a menudo se consideran prescindibles.

Con menos frecuencia, se encuentran 4-tuplas, lo que significa una atomización más granular de las instrucciones de Turing.

El concepto de "Estado"

Dentro del discurso en torno a las máquinas de Turing, el término "estado" puede generar ambigüedad debido a sus interpretaciones duales. La mayoría de los comentaristas posteriores a Turing definen "estado" como el identificador o designador de la instrucción actualmente programada para su ejecución, refiriéndose efectivamente al contenido del registro estatal. Sin embargo, el propio Turing (1936) trazó una clara distinción entre lo que denominó la "configuración m" de la máquina (un registro) y el "estado de progreso" de la máquina (o computadora humana) durante un cálculo, que abarca la condición general de todo el sistema. La "fórmula de estado" de Turing incorpora específicamente tanto la instrucción actual como todos los símbolos presentes en la cinta.

El progreso computacional en cualquier etapa determinada está completamente definido por el conjunto de instrucciones y los símbolos presentes en la cinta. En consecuencia, el estado del sistema puede representarse mediante una expresión singular, una secuencia de símbolos que comprende el contenido de la cinta, seguida de un símbolo delta (Δ, que se supone único), y luego las instrucciones. Esta expresión compuesta se denomina "fórmula de estado".

Anteriormente, en su publicación, Turing amplió este concepto ilustrando un ejemplo en el que un símbolo que representa la "configuración m" actual (la etiqueta de la instrucción) se colocaba debajo del cuadrado escaneado, junto a todos los símbolos de la cinta. Designó esto como la "configuración completa". Para representar esta "configuración completa" en una sola línea, colocó la etiqueta de estado o configuración m a la izquierda del símbolo que se estaba escaneando.

Kleene (1952) presenta una variación de este concepto, demostrando el método para codificar la "situación" de una máquina usando un número de Gödel. Coloca el símbolo de "configuración m" q₄ encima del cuadrado escaneado, aproximadamente centrado entre los seis cuadrados que no están en blanco en la cinta, y lo coloca a la derecha del cuadrado escaneado. Sin embargo, Kleene identifica específicamente "q₄" como "el estado de la máquina". Por el contrario, Hopcroft y Ullman se refieren a esta composición como la "descripción instantánea" y se adhieren a la convención de Turing de colocar el "estado actual" (etiqueta de instrucción, configuración m) a la izquierda del símbolo escaneado (p. 149). Por lo tanto, una descripción instantánea comprende los símbolos que no están en blanco a la izquierda, el estado de la máquina, el símbolo actualmente escaneado por la cabeza y los símbolos que no están en blanco a la derecha.

Ejemplo: el estado total de un castor ocupado de 3 estados y 2 símbolos después de tres "movimientos" computacionales.

1A1

Esta notación indica que después de tres operaciones, la cinta contiene la secuencia "...000110000...", con el cabezal escaneando actualmente el '1' más a la derecha, y el estado de la máquina se designa como A. Los símbolos en blanco, aquí representados por '0's, se pueden incorporar al estado total, como lo ejemplifica B01. En este caso, la cinta contiene un solo '1', pero el cabezal escanea el '0' (en blanco) a su izquierda y el estado es B.

Dentro del dominio de las máquinas de Turing, el término "estado" necesita una aclaración con respecto a su referente específico: si denota la instrucción actual, la compilación de símbolos en la cinta combinada con la instrucción actual, o la compilación de símbolos en la cinta con la instrucción actual colocada a la izquierda o a la izquierda. a la derecha del símbolo escaneado.

Diagramas de estado

La tabla anterior se representa como un diagrama de "transición de estado".

Por lo general, los conjuntos de datos extensos se presentan de manera más efectiva en formato tabular (Booth, p. 74), lo que facilita su simulación por computadora. Sin embargo, elementos conceptuales específicos, como máquinas que incorporan estados de "reinicio" o exhiben patrones repetitivos (cf. Hill y Peterson p. 244 y siguientes), pueden entenderse más claramente cuando se visualizan gráficamente.

La determinación de si una representación gráfica ofrece una mejora sobre su contraparte tabular depende de la evaluación del lector dentro del contexto específico.

Es imperativo reiterar que estos diagramas representan una representación estática de sus tablas correspondientes, una instantánea congelada en el tiempo, no la progresión dinámica o "trayectoria" de un cálculo a través de dimensiones temporales y espaciales. Aunque una máquina de castor ocupada sigue consistentemente una trayectoria de estado idéntica durante cada ejecución, este principio no se aplica a una máquina de "copia", que admite "parámetros" de entrada variables.

El diagrama de "progreso del cálculo" ilustra el avance secuencial del "estado" (instrucción) del castor ocupado de tres estados a lo largo de todo su proceso computacional. En el extremo derecho, se presenta para cada paso la "configuración completa" de Turing (alternativamente denominada "situación" de Kleene o "descripción instantánea" de Hopcroft-Ullman). Si la máquina se detuviera y tanto su "registro de estado" como toda la cinta se pusieran en blanco, estas "configuraciones" registradas permitirían la reanudación de un cálculo en cualquier punto de su progresión.

Modelos equivalentes

Muchas máquinas que pueden parecer poseer mayor capacidad computacional que una simple máquina universal de Turing son demostrablemente equivalentes en poder computacional (Hopcroft y Ullman p. 159, cf. Minsky (1967)). Si bien estas máquinas pueden ofrecer ventajas en cuanto a velocidad, eficiencia de la memoria o concisión del conjunto de instrucciones, no mejoran el poder computacional fundamental, lo que significa que no pueden procesar una gama más amplia de funciones matemáticas. Este principio está respaldado además por la tesis de Church-Turing, que plantea la hipótesis de que cualquier función computable puede ser calculada por una máquina de Turing, afirmando así la universalidad del cálculo de Turing en todos los modelos teóricos.

Una máquina de Turing exhibe equivalencia a un autómata de empuje de pila única (PDA) cuando la restricción de pila de último en entrar, primero en salir (LIFO) de este último se relaja, mejorando así su flexibilidad y concisión. Además, una máquina de Turing se puede modelar como una PDA de dos pilas que funciona según la semántica LIFO estándar, donde una pila representa el segmento de cinta a la izquierda del cabezal de lectura/escritura y la otra modela el segmento a la derecha.

Por el contrario, se ha demostrado que ciertos modelos computacionales altamente simplificados poseen equivalencia de Turing, lo que significa una capacidad computacional idéntica al modelo de máquina de Turing estándar.

Los modelos equivalentes que se encuentran con frecuencia incluyen el Turing de múltiples cintas. máquina, la máquina de Turing multipista, máquinas que incorporan mecanismos explícitos de entrada y salida, y la máquina de Turing no determinista (NDTM). El NDTM contrasta con la determinista máquina de Turing (DTM), donde la tabla de acciones especifica una transición única para cada combinación dada de símbolo y estado.

Las máquinas de Turing restringidas a operaciones de solo lectura y movimiento hacia la derecha son computacionalmente equivalentes a los autómatas finitos deterministas (DFA) y, por extensión, a los autómatas finitos no deterministas (NFA) mediante la aplicación del algoritmo de conversión de NFA a DFA.

En aplicaciones prácticas y con fines pedagógicos, la máquina de registro equivalente sirve como modelo para un lenguaje de programación ensamblador típico.

Una investigación pertinente se refiere a la equivalencia de Turing de modelos computacionales incorporados en lenguajes de programación específicos. Aunque los cálculos informáticos reales operan dentro de restricciones de estados finitos, lo que excluye la simulación directa de la máquina de Turing, los lenguajes de programación en sí no están inherentemente sujetos a esta limitación. La investigación de Kirner et al. (2009) indica que los lenguajes de programación de propósito general exhiben variabilidad en la completitud de Turing, algunos poseen esta propiedad y otros carecen de ella. Por ejemplo, ANSI C no es Turing completo porque todas sus instancias (incluso aquellas con comportamientos indefinidos permitidos por el estándar de compatibilidad heredada) presuponen un espacio de memoria finito. Esta limitación surge de la capacidad del lenguaje para acceder al tamaño de los tipos de datos de referencia de la memoria, específicamente punteros. Por el contrario, los lenguajes de programación como Pascal, que carecen de esta característica específica, pueden considerarse en principio como Turing completo. Esta integridad 'en principio' reconoce que, si bien un lenguaje puede ser completo en Turing si se ignoran las fallas en la asignación de memoria, los programas compilados ejecutados en hardware físico siguen estando limitados por recursos finitos.

Choice Machines y Oracle Machines

En su artículo fundamental de 1936, Turing diferenciaba entre una "máquina automática", caracterizada por su "movimiento... completamente determinado por la configuración", y una "máquina de elección", que describió de la siguiente manera:

...cuyo movimiento está sólo parcialmente determinado por la configuración... Al encontrar una configuración ambigua, dicha máquina no puede continuar hasta que un operador externo realice una selección arbitraria. Este escenario se aplicaría a las máquinas empleadas en el análisis de sistemas axiomáticos.

Turing (1936) no proporcionó más detalles sobre las máquinas de elección más allá de una nota a pie de página, donde esbozó un método para que una máquina automática (una máquina) "encontrara todas las fórmulas demostrables del cálculo [de Hilbert]" como alternativa al empleo de una máquina de elección. Postuló que "las opciones siempre están entre dos posibilidades 0 y 1. Cada prueba estará entonces determinada por una secuencia de opciones i₁, i₂, ..., i_n (i§67§ = 0 o 1, i§8_{9§ = 0 o 1, ..., i_n = 0 o 1), y de ahí el número 2ⁿ + i§14}15_{16§n-1 + i§18_{19_{20§n-2 + ... +i_n determina completamente la prueba. La máquina automática realiza sucesivamente la prueba 1, la prueba 2, la prueba 3,..."}}}

Este método demuestra eficazmente cómo un método determinista (es decir, automática) La máquina de Turing puede emular las operaciones de una máquina de Turing no determinista. Turing abordó este concepto en una nota a pie de página, aparentemente concluyendo su discusión sobre el tema.

Una máquina oráculo, u o-máquina, funciona como una máquina de Turing que detiene temporalmente su cálculo en el estado "o", esperando una decisión del "oráculo" para completar su cálculo. Turing (1939) describió este oráculo como una entidad cuya naturaleza permanece sin especificar, más allá de la estipulación crucial de que no puede ser en sí misma una máquina.

Máquinas universales de Turing

Como lo expresa Turing en Lo indecidible (énfasis añadido):

Se puede diseñar una única máquina para calcular cualquier secuencia computable. Si esta máquina, denominada U, recibe una cinta que contiene los quíntuplos separados por punto y coma de otra máquina informática, M, entonces U calculará posteriormente la secuencia idéntica a M.

Si bien este descubrimiento ahora es ampliamente aceptado, se consideró innovador en 1936. El modelo computacional de Turing, al que denominó "máquina universal" (abreviado como "U"), se considera ampliamente como el avance teórico fundamental que allanó el camino para el concepto de computadora con programa almacenado.

El artículo fundamental de Turing abarca fundamentalmente la invención de la computadora moderna y varias técnicas de programación asociadas.

En cuanto a la complejidad computacional, una máquina de Turing universal de cintas múltiples muestra una reducción de rendimiento de solo un factor logarítmico en comparación con las máquinas que simula. Este hallazgo fue establecido en 1966 por F. C. Hennie y R. E. Stearns.

Comparación con máquinas físicas

Las máquinas de Turing poseen una mayor potencia computacional que otros autómatas, incluidas las máquinas de estados finitos y los autómatas de empuje. La tesis de Church-Turing postula que las máquinas de Turing son equivalentes en potencia a las computadoras físicas, capaces de ejecutar cualquier operación que pueda realizar un programa real. Sin embargo, esta afirmación pasa por alto una distinción crítica: una máquina física, limitada por un número finito de configuraciones, opera fundamentalmente como una máquina de estados finitos, mientras que una máquina de Turing se beneficia de una capacidad de almacenamiento ilimitada para sus cálculos.

Varias justificaciones aclaran por qué las máquinas de Turing sirven como modelos efectivos para las computadoras físicas:

Cualquier cálculo realizado por una computadora física también puede ser ejecutado por una máquina de Turing. Por ejemplo, "una máquina de Turing es capaz de simular cualquier tipo de subrutina que se encuentre en los lenguajes de programación, abarcando procedimientos recursivos y todos los mecanismos establecidos de paso de parámetros" (Hopcroft y Ullman, p. 157). Además, un autómata de estados finitos (FSA) suficientemente grande puede modelar cualquier computadora física, excluyendo las operaciones de entrada/salida. En consecuencia, cualquier limitación identificada para las máquinas de Turing es igualmente aplicable a las computadoras físicas.
La única distinción reside en la capacidad teórica de una máquina de Turing para manipular una cantidad ilimitada de datos. Sin embargo, dentro de un período de tiempo finito, una máquina de Turing, al igual que una máquina física, sólo puede procesar una cantidad finita de datos.
De manera análoga a una máquina de Turing, la capacidad de almacenamiento de una máquina física se puede ampliar incrementalmente mediante la adición de discos u otros medios de almacenamiento.
Describir programas para máquinas físicas utilizando modelos abstractos más simples frecuentemente resulta en una complejidad significativamente mayor en comparación con las descripciones que emplean máquinas de Turing. Por ejemplo, un algoritmo descrito por una máquina de Turing podría implicar sólo unos pocos cientos de estados, mientras que su autómata finito determinista (DFA) equivalente en una máquina física específica podría comprender billones de estados, lo que haría que la representación DFA no fuera práctica para el análisis.
Las máquinas de Turing proporcionan un marco para describir algoritmos independientemente de su consumo de memoria. Si bien todas las máquinas físicas actuales tienen memoria finita, en teoría este límite puede aumentar indefinidamente con el tiempo. En consecuencia, las máquinas de Turing permiten la formulación de afirmaciones sobre algoritmos que son (teóricamente) perpetuamente válidos y no se ven afectados por los avances en la arquitectura de las máquinas informáticas convencionales.
Los algoritmos ejecutados en máquinas abstractas equivalentes a Turing pueden utilizar tipos de datos de precisión arbitraria y no están sujetos a condiciones inesperadas, como el agotamiento de la memoria.

Limitaciones

Teoría de la complejidad computacional

Las máquinas de Turing presentan una limitación en su capacidad para modelar con precisión las ventajas específicas de ciertas configuraciones arquitectónicas. Por ejemplo, las computadoras contemporáneas con programas almacenados ejemplifican una máquina abstracta más especializada conocida como modelo de máquina de programas almacenados de acceso aleatorio (RASP). De manera similar a una máquina de Turing universal, el RASP almacena su "programa" en una "memoria" externa, separada de las "instrucciones" de la máquina de estados finitos. Sin embargo, a diferencia de una máquina de Turing universal, la RASP presenta una gama infinita de "registros" distintos, numerados e ilimitados: "células" de memoria capaces de contener cualquier número entero (cf. Elgot y Robinson (1964), Hartmanis (1971) y Cook-Rechow (1973)). La máquina de estados finitos del RASP incorpora direccionamiento indirecto, lo que permite que el contenido de un registro sirva como dirección para otro; en consecuencia, el "programa" del RASP puede acceder a cualquier registro dentro de su secuencia. Esta diferencia fundamental permite optimizaciones computacionales basadas en índices de memoria que son inalcanzables con una máquina de Turing general. Por lo tanto, emplear máquinas de Turing para establecer límites en los tiempos de ejecución puede conducir a la derivación de un "falso límite inferior" para ciertos algoritmos, atribuible a una suposición demasiado simplificada inherente al modelo de la máquina de Turing. La búsqueda binaria sirve como ilustración pertinente, ya que demuestra un rendimiento superior cuando se implementa utilizando el modelo computacional RASP en comparación con el modelo de la máquina de Turing.

Interacción

Durante las etapas incipientes de la informática, el uso de la computadora se limitaba predominantemente al procesamiento por lotes, que implicaba tareas no interactivas que generaban datos de salida a partir de una entrada específica. La teoría de la computabilidad, que investiga la computabilidad de funciones que asignan entradas a salidas y para las cuales se concibieron las máquinas de Turing, refleja este paradigma operativo histórico.

Desde la década de 1970 en adelante, la aplicación interactiva de las computadoras ganó una prevalencia generalizada. Si bien es teóricamente factible modelar dicha interacción postulando que un agente externo lea y escriba simultáneamente en la cinta de una máquina de Turing, este enfoque rara vez representa con precisión los procesos interactivos del mundo real. En consecuencia, al caracterizar la interactividad, generalmente se prefieren modelos alternativos como los autómatas de E/S.

Comparación con el modelo aritmético de computación

El modelo aritmético de computación difiere del modelo de Turing en dos aspectos principales:

Dentro del modelo aritmético, cada número real ocupa una celda de memoria singular, mientras que en el modelo de Turing, el requisito de almacenamiento para un número real depende del número de bits necesarios para su representación.
En el modelo aritmético, las operaciones aritméticas fundamentales con números reales (incluidas la suma, la resta, la multiplicación y la división) se ejecutan en un solo paso computacional. Por el contrario, en el modelo de Turing, el tiempo de ejecución de cada operación aritmética está determinado por la longitud de sus operandos.

Ciertos algoritmos exhiben complejidad de tiempo polinomial en un modelo pero no en el otro. Por ejemplo:

El algoritmo euclidiano logra la ejecución en tiempo polinómico dentro del modelo de Turing, pero no en el modelo aritmético.
El algoritmo que procesa n números y posteriormente calcula $2^{2^{n}}$ 10§ §1314§ n {\displaystyle 2^{2^{n}}} mediante la elevación al cuadrado repetida opera en tiempo polinomial dentro del modelo aritmético, pero no dentro del modelo de Turing. Esta discrepancia surge porque la longitud de bits necesaria para representar el resultado crece exponencialmente con el tamaño de entrada.

Sin embargo, un algoritmo que se ejecuta en tiempo polinómico dentro del modelo aritmético, siempre que la longitud binaria de todos los números involucrados también sea polinómica en la longitud de entrada, invariablemente exhibirá complejidad en tiempo polinómico en el modelo de Turing. Un algoritmo de este tipo se caracteriza por ejecutarse en un tiempo fuertemente polinomial.

Contexto histórico

Antecedentes históricos: maquinaria computacional

Robin Gandy (1919-1995), ex alumno y asociado de toda la vida de Alan Turing (1912-1954), rastreó los orígenes conceptuales de la "máquina calculadora" hasta Charles Babbage (alrededor de 1834) y articuló lo que denominó "Tesis de Babbage":

Que todo el desarrollo analítico y las operaciones ahora pueden ejecutarse mediante maquinaria.

El análisis de Gandy del motor analítico de Babbage delinea cinco operaciones fundamentales (Gandy, págs. 52-53):

Estas incluyen las funciones aritméticas de suma (+), resta "adecuada" (-) y multiplicación (×), donde la resta "adecuada" se define de manera que x − y = 0 si y ≥ x.
Cualquier secuencia compuesta de estas operaciones constituye una operación válida.
La iteración de una operación, definida como repetir una operación P n veces.
Iteración condicional, que implica la repetición de una operación P n veces, dependiendo del resultado exitoso de una prueba T.
Transferencia condicional, también conocida como instrucción "goto" condicional.

Gandy afirma que "las funciones que pueden calcularse mediante (1), (2) y (4) son precisamente aquellas que son computables por Turing". Además, hace referencia a otras propuestas de "máquinas calculadoras universales", como las de Percy Ludgate (1909), Leonardo Torres Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936) y Howard Aiken (1937). Sin embargo:

… el énfasis está en programar una secuencia iterable fija de operaciones aritméticas. No se reconoce la importancia fundamental de la iteración condicional y la transferencia condicional para una teoría general de las máquinas calculadoras...

El Entscheidungsproblem, comúnmente conocido como el "problema de decisión", se originó a partir de la décima pregunta de Hilbert planteada en 1900.

En relación con los problemas articulados por el renombrado matemático David Hilbert en 1900, una faceta específica del problema número 10 había sido discutida conceptualmente durante casi tres décadas antes de su formulación precisa. La declaración original de Hilbert para el problema número 10 se presenta a continuación:

10. Determinación de la solubilidad de una ecuación diofántica. Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes integrales racionales: Idear un proceso según el cual se pueda determinar en un número finito de operaciones si la ecuación es solucionable en números enteros racionales. El Entscheidungsproblem [problema de decisión para lógica de primer orden] se resuelve cuando conocemos un procedimiento que permite que cualquier expresión lógica determinada decida mediante un número finito de operaciones su validez o satisfacibilidad... El Entscheidungsproblem debe considerarse el principal problema de la lógica matemática.

En 1922, el concepto de "Entscheidungsproblem" había evolucionado, lo que llevó a H. Behmann a articular lo siguiente:

... la forma más general del Entscheidungsproblem [es] la siguiente:
Se requiere una prescripción bastante definida y de aplicación general que permita a uno decidir en un número finito de pasos la verdad o falsedad de una afirmación puramente lógica dada...

Behmann comenta que... el problema general es equivalente al problema de decidir qué proposiciones matemáticas son verdaderas.

Si uno fuera capaz de resolver el Entscheidungsproblem entonces tendría un "procedimiento para resolver muchos (o incluso todos) los problemas matemáticos".

En el congreso internacional de matemáticos de 1928, Hilbert "hizo sus preguntas bastante precisas. En primer lugar, ¿las matemáticas eran completas... En segundo lugar, las matemáticas eran consistentes... Y en tercer lugar, ¿las matemáticas eran decidibles?" Kurt Gödel proporcionó respuestas a las dos primeras preguntas en 1930, durante la misma asamblea en la que Hilbert pronunció su discurso de jubilación, algo que, según se dice, disgustó a Hilbert. La tercera cuestión, relativa al Entscheidungsproblem, permaneció sin resolver hasta mediados de la década de 1930.

Un desafío principal era el requisito previo para una definición precisa de una "prescripción general aplicable definida", un concepto que más tarde denominó "calculabilidad efectiva" por el profesor de Princeton Alonzo Church. En 1928 no existía tal definición formal. Sin embargo, durante los siguientes seis o siete años, Emil Post formuló una definición que involucraba a un trabajador que manipulaba marcas en habitaciones según instrucciones. Al mismo tiempo, Church, junto con sus alumnos Stephen Kleene y J. B. Rosser, desarrollaron sus propias definiciones utilizando el cálculo lambda de Church y la teoría de la recursividad de Gödel (1934). El artículo fundamental de Church, publicado el 15 de abril de 1936, demostró la "indecidibilidad" del Entscheidungsproblem, precediendo a hallazgos similares de Turing por casi un año (el artículo de Turing fue presentado el 28 de mayo de 1936 y publicado en enero de 1937). Mientras tanto, Emil Post presentó un documento conciso en el otoño de 1936, estableciendo la prioridad de Turing sobre Post. Mientras Church sirvió como árbitro para el artículo de Turing, Turing tuvo la oportunidad de examinar el trabajo de Church y posteriormente adjuntar un Apéndice que describe una prueba de que el cálculo lambda de Church y sus propias máquinas podían calcular funciones idénticas.

El enfoque de Church, sin embargo, presentó una metodología distinta y algo menos sólida. En contraste, la construcción de Turing ofreció un argumento más directo derivado de principios fundamentales, resolviendo así las deficiencias de la demostración original de Church.

El Post, por el contrario, se limitó a proponer una definición de calculabilidad y criticó la "definición" de Church sin proporcionar ninguna prueba formal.

La máquina A de Alan Turing

En la primavera de 1935, mientras estudiaba una maestría en el King's College de Cambridge, Turing aceptó este desafío. Su interés se despertó gracias a las conferencias del lógico M. H. A. Newman, a través de las cuales conoció la obra de Gödel y el Entscheidungsproblem. Newman empleó con frecuencia el término "mecánico", como se señala en su obituario de Turing de 1955, donde afirmó:

Cuando se le pidió que definiera un proceso "mecánico", Turing respondió característicamente: "Algo que puede ser hecho por una máquina", y posteriormente emprendió la agradable tarea de analizar el concepto general de una máquina informática.

Gandy afirma:

Supongo, aunque sin un conocimiento definitivo, que el objetivo inicial de Turing era demostrar la indecidibilidad del Entscheidungsproblem. Contó que la "idea principal" de su artículo surgió mientras estaba en Grantchester Meadows durante el verano de 1935. Este concepto fundamental podría haber sido su análisis detallado de la computación o su comprensión de la existencia de una máquina universal, que luego permitiría un argumento diagonal para establecer la insolubilidad.

Aunque Gandy consideró "engañosa" la declaración antes mencionada de Newman, esta perspectiva no es universalmente aceptada. Turing mantuvo durante toda su vida una fascinación por las máquinas; por ejemplo, "Alan había soñado con inventar máquinas de escribir cuando era niño; [su madre] la señora Turing tenía una máquina de escribir; y bien podría haber comenzado preguntándose qué significaba llamar 'mecánica' a una máquina de escribir" (Hodges p. 96). Durante sus estudios de doctorado en Princeton, Turing construyó un multiplicador de lógica booleana. Su tesis doctoral, "Sistemas de lógica basados en ordinales", proporciona la siguiente definición de "función computable":

Como se indicó anteriormente, "una función es efectivamente calculable si sus valores pueden determinarse mediante algún proceso puramente mecánico". Esta afirmación puede interpretarse literalmente, definiendo un proceso puramente mecánico como aquel ejecutable por una máquina. Es factible proporcionar una descripción matemática, de forma estandarizada, de las arquitecturas de estas máquinas. La progresión de estos conceptos culmina en la definición del autor de función computable y la equivalencia de computabilidad con calculabilidad efectiva. Demostrar la equivalencia de estas tres definiciones [la tercera es el cálculo λ], aunque no es inherentemente difícil, requiere un esfuerzo considerable.

Alan Turing concibió la "máquina a" (máquina automática) en 1936. Presentó su artículo fundamental a la Sociedad Matemática de Londres para sus Actas el 31 de mayo de 1936; sin embargo, se publicó a principios de 1937 y las separatas estuvieron disponibles en febrero de ese año. Alonzo Church, asesor doctoral de Turing, introdujo posteriormente el término "máquina de Turing" en una reseña. Utilizando este modelo, Turing proporcionó respuestas negativas a dos preguntas fundamentales:

¿Existe una máquina capaz de determinar si cualquier máquina arbitraria representada en su cinta es "circular" (es decir, entra en un bucle infinito o cesa su proceso computacional)?
¿Se puede construir una máquina que determine si cualquier máquina arbitraria representada en su cinta alguna vez imprimirá un símbolo específico?

En consecuencia, al ofrecer una descripción matemática de un dispositivo notablemente simple capaz de realizar cálculos arbitrarios, demostró con éxito las propiedades generales de la computación, específicamente la incomputabilidad del Entscheidungsproblem (el 'problema de decisión').

A su regreso al Reino Unido, Turing finalmente compartió la responsabilidad de descifrar los códigos secretos alemanes generados por las máquinas de cifrado "The Enigma". También participó en el diseño del motor de computación automática (ACE), y Hodges (p. 318) señaló que "la propuesta ACE [de Turing] era efectivamente autónoma y sus raíces no estaban en el EDVAC [la iniciativa de EE. UU.], sino en su propia máquina universal". Persisten los debates sobre la génesis y el carácter de lo que Kleene (1952) denominó la Tesis de Turing. Sin embargo, lo que Turing probó con su modelo de máquina computacional se presenta en su artículo "Sobre números computables, con una aplicación al Entscheidungsproblem" (1937).

[que] el problema de Hilbert Entscheidungs carece de solución... Por lo tanto, propongo demostrar la ausencia de un procedimiento general para determinar la demostrabilidad de una fórmula dada U dentro del cálculo funcional K, lo que implica que ninguna máquina, cuando se le proporciona dicha fórmula U, puede determinar en última instancia su demostrabilidad.

La segunda prueba de Turing ilustra este concepto: la pregunta "¿Esta máquina alguna vez imprime 0?", representa un problema indecidible, lo que indica la ausencia de un procedimiento algorítmico general para resolverlo.

1937-1970: la aparición de la computadora digital y la génesis de la informática

En 1937, durante sus estudios de doctorado en Princeton, Turing construyó de forma independiente un multiplicador digital (lógica booleana), fabricando sus relés electromecánicos (Hodges, p. 138). Su objetivo era implementar la arquitectura lógica de una máquina de Turing utilizando una red de interruptores operados por relés (Hodges, p. 138). Paralelamente a los esfuerzos exploratorios de Turing, se estaban llevando a cabo importantes investigaciones paralelas: Konrad Zuse en Alemania (1938) y Howard Aiken y George Stibitz en los Estados Unidos (1937) prosiguieron desarrollos similares. Los resultados de estos esfuerzos fueron posteriormente utilizados tanto por las fuerzas del Eje como por las Aliadas durante la Segunda Guerra Mundial (cf. Hodges, págs. 298-299). Desde principios hasta mediados de la década de 1950, Hao Wang y Marvin Minsky simplificaron la máquina de Turing a una forma más rudimentaria, que sirvió como precursora de la máquina Post-Turing de Martin Davis. Al mismo tiempo, los investigadores europeos conceptualizaron la naciente computadora electrónica como una entidad teórica equivalente a lo que ahora se reconoce como una "máquina de Turing". A finales de la década de 1950 y principios de la de 1960 se presenciaron avances convergentes por parte de Melzak y Lambek (1961), Minsky (1961) y Shepherdson y Sturgis (1961), quienes ampliaron el trabajo europeo refinando la máquina de Turing hasta convertirla en un modelo abstracto más accesible, similar a una computadora, conocido como la contramáquina. Investigaciones posteriores de Elgot y Robinson (1964), Hartmanis (1971) y Cook y Reckhow (1973) desarrollaron aún más estos conceptos, introduciendo los modelos de máquina de registro y de máquina de acceso aleatorio, que fundamentalmente representan máquinas de Turing de cintas múltiples equipadas con un conjunto de instrucciones de tipo aritmético.

1970–presente: La máquina de Turing como modelo computacional

En la actualidad, las máquinas de contador, registro y acceso aleatorio, junto con su progenitora, la máquina de Turing, siguen siendo los modelos preferidos para los teóricos que exploran investigaciones dentro de la teoría de la computación. En particular, la teoría de la complejidad computacional emplea con frecuencia la máquina de Turing:

En la teoría de la complejidad basada en máquinas, dos modelos han alcanzado prominencia, dependiendo de los objetos computacionales manipulados (por ejemplo, enteros no negativos o cadenas alfanuméricas):
la máquina de Turing multicinta fuera de línea, que sirve como modelo convencional para el cálculo orientado a cadenas; y la máquina de acceso aleatorio (RAM), conceptualizada por Cook y Reckhow, que simula la computadora idealizada de estilo Von Neumann.

Por el contrario, dentro del dominio relacionado del análisis de algoritmos, el modelo RAM asume esta función principal.

máquina de turing (Turing machine)