Máquina de Turing

En informática , una máquina de Turing (o MdT para abreviar ) es una máquina ideal que manipula los datos contenidos en una cinta de longitud potencialmente infinita, de acuerdo con un conjunto predeterminado de reglas bien definidas [1] . En otras palabras, es un modelo abstracto que define una máquina capaz de ejecutar algoritmos y equipada con una cinta potencialmente infinita en la que puede leer y/o escribir símbolos.

Introducido en 1936 por Alan Turing [2] como un modelo computacional para responder al Entscheidungsproblem (problema de decisión) [3] propuesto por Hilbert en su programa fundacional formalista de las matemáticas , es una poderosa herramienta teórica que es ampliamente utilizada en la teoría de la computabilidad y en el estudio de la complejidad de los algoritmos , ya que es de gran ayuda para los estudiosos en la comprensión de los límites del cálculo mecánico; su importancia es tal que hoy en día, para definir la noción de algoritmo de forma formalmente precisa , tendemos a retrotraerla a los cálculos que se pueden realizar con las máquinas de Turing.

Descripción

Tiene la particularidad de estar regido por reglas de naturaleza muy simple, es decir que puede describirse como constituido por mecanismos elementales muy simples; además, es posible presentar sus evoluciones a un nivel sintético por medio de descripciones mecánicas bastante intuitivas. Por otro lado, tiene la computabilidad que se presume máxima: se demuestra, de hecho, que es capaz de realizar todos los cálculos que pueden realizar los demás modelos de cálculo conocidos por el hombre. Entre estos modelos computacionales recordamos las funciones recursivas de Jacques Herbrand y Kurt Gödel , el cálculo lambda de Alonzo Church y Stephen Kleene , la lógica combinatoria de Moses Schönfinkel y Haskell Curry , los algoritmos de Markov , los sistemas de Thue , los sistemas de Post , Las máquinas de Hao Wang y las RAM abstractas o máquinas de registros elementales de Marvin Minsky . En consecuencia, se ha consolidado la convicción de que para cada problema computable existe una MdT capaz de resolverlo: esta es la llamada conjetura de Church-Turing , que básicamente postula que para cada función computable existe una máquina de Turing equivalente, es decir, que l 'conjunto de funciones computables coincide con el de funciones recursivas .

Los algoritmos que puede implementar un MdT se denominan "algoritmos computables de Turing".

Características

En 1936 se publicó un artículo de Alan Mathison Turing titulado Sobre los números computables, con una aplicación al Entscheidungsproblem , en el que el autor resolvía negativamente el Entscheidungsproblem o problema de decidibilidad lanzado en 1900 por David Hilbert y Wilhelm Ackermann .

La pregunta había sido planteada por Hilbert en los siguientes términos: "¿Existe siempre, al menos en principio, un método mecánico (es decir, una forma rigurosa) por el cual, dado cualquier enunciado matemático, es posible establecer si es verdadero ¿o falso?"

Las ventajas de contar con un método así son enormes y merecen todo el énfasis que Hilbert y muchos otros que le siguieron le dieron a la pregunta: tal algoritmo sería capaz de resolver todos los problemas matemáticos y, mucho más, sería posible reducir cualquier problema humano. razonamiento por mero cálculo mecanizable. Una primera respuesta contundente la dio el matemático bohemio Gödel en la segunda conferencia sobre epistemología de las ciencias exactas en Königsberg (1930), en la que expresó por primera vez públicamente las ideas contenidas en su obra más famosa sobre la incompletud de las ciencias coherentes. sistemas formales ( primer teorema de incompletitud ); Gödel demostró que la mera coherencia de un sistema formal no puede garantizar que lo que en él se prueba sea verdadero o falso. El sueño de Hilbert ya se estaba desvaneciendo cuando Turing publicó su artículo, en el que demostraba la insolubilidad del Entscheidungsproblem.

La solución propuesta por Turing consiste en la utilización de un modelo matemático capaz de simular el proceso de cálculo humano, descomponiéndolo en sus pasos finales.
La máquina consta de un cabezal de lectura y escritura con el que es capaz de leer y escribir en una cinta potencialmente infinita dividida, de manera discreta, en cajas. En cada instante de tiempo t 1 , la máquina se encuentra en un estado interno bien determinado s 1 , resultado del procesamiento realizado sobre los datos leídos.

El estado interno, o configuración, de un sistema es la condición en que se encuentran los componentes de la máquina en un instante dado de tiempo t . Los componentes a considerar son:

Entre todos los estados posibles, se distinguen los siguientes:

Implementar un algoritmo en este contexto significa realizar una de las cuatro operaciones elementales

Ejecutar una operación o 1 , entre los instantes de tiempo t 1 y t 2 , significa pasar del estado interno s 1 a s 2 . Más formalmente, esto se expresa en símbolos como: {s 1 , a 1 , or 1 , s 2 } para leerse como: en el estado interno s 1 la máquina observa el símbolo a 1 , realiza la operación o 1 y encuentra sí mismo en el estado interno s 2 .
Turing pudo demostrar que un instrumento así, con unas características tan rígidamente definidas, es capaz de realizar cualquier cálculo, pero no se quedó ahí; entendió que la computabilidad era un pariente cercano de la demostrabilidad y por lo tanto, así como Gödel había destruido los sueños de gloria de Russell y los Principia Mathematica de Whitehead , así sus máquinas podían cerrar definitivamente la cuestión del Entscheidungsproblem .

Definición

Se consideran múltiples variantes ( modelos ) del MdT que resultan tener el mismo alcance. Aquí partimos de una variante bastante simple que podemos llamar una máquina de Turing determinista de una cinta con instrucciones de cinco campos . Otras variaciones se presentan a continuación.

Introducción informal

La máquina puede operar sobre una cinta que se presenta como una secuencia de casillas en las que se pueden grabar símbolos de un alfabeto terminado bien determinado; está equipado con un cabezal de lectura y escritura (E/S) con el que puede realizar operaciones de lectura y escritura en una caja de cinta. La máquina evoluciona con el tiempo y en cualquier instante puede encontrarse en un estado interno bien determinado que forma parte de un conjunto finito de estados. Inicialmente se coloca una cadena en la cinta que representa los datos que caracterizan el problema que se envía a la máquina. La máquina también está equipada con un repertorio finito de instrucciones que determinan su evolución como consecuencia de los datos iniciales. La evolución se desarrolla por pasos sucesivos que corresponden a una secuencia discreta de instantes sucesivos. Las propiedades anteriores son comunes a muchas máquinas formales ( autómata de estados finitos , autómata de pila , ...). Una característica del MdT es la de tener un cinturón potencialmente infinito, es decir, se puede extender tanto como se quiera si se hace necesario.

Cada paso de la evolución está determinado por el estado actual s en el que se encuentra la máquina y por el carácter c que la cabeza de E/S encuentra en la caja de cinta en la que está posicionada y toma la forma de cualquier modificación del contenido de la misma. la caja, en el ''posible movimiento de la cabeza de una posición hacia la derecha o hacia la izquierda y en el eventual cambio de estado. Las acciones que se llevan a cabo en cada paso están determinadas por la instrucción, que suponemos única, que tiene como sus dos primeros componentes s y c ; los otros tres componentes de la declaración proporcionan el nuevo estado, el nuevo carácter y una solicitud para moverse hacia la izquierda, nulo o hacia la derecha en orden.

Una evolución de la máquina consiste en una secuencia de sus posibles "configuraciones", cada configuración consta del estado interno actual, el contenido de la cinta (una cadena de longitud finita) y la posición en la cinta del cabezal de E/S. En los casos más simples, la evolución se detiene en un determinado punto porque no se encuentra ninguna instrucción capaz de hacerla continuar. Puede tener un bloqueo en una configuración "útil" desde el punto de vista del problema que desea resolver; en este caso, lo que se registra en la cinta en el momento de la detención representa el resultado del procesamiento. No obstante, también puede existir una parada "inútil" que debe ser considerada como una conclusión errónea del tratamiento. Hay que decir de inmediato que también puede ocurrir que una evolución no termine nunca (Ver siguiente apartado y Problema de parada ).

Ambiente formal

Definimos una máquina de Turing determinista de una cinta e instrucciones de cinco campos , un término que abreviamos como MdT1n5i, una máquina formal de la siguiente forma:

es un conjunto finito llamado conjunto de estados de máquina ;

es un elemento de S llamado estado inicial de T ;

es un subconjunto de S llamado el conjunto de los estados finales de T ;

es un alfabeto finito llamado alfabeto de cinta T

es un carácter del alfabeto A llamado marca de celda vacía de la cinta T

se llama la función de transición de la máquina.

Si , el quíntuple correspondiente se puede considerar como la instrucción que se ejecuta cuando la máquina está en el estado s y la cabeza de E/S lee a en la casilla en la que está posicionada; implica la transición al estado t , la escritura del carácter b y:

Extensión del alcance y conjetura de Church-Turing

La importancia de MdT deriva de que permite realizar todas las elaboraciones realizadas por las máquinas (electrónicas o mecánicas) que han aparecido en la historia de la humanidad, incluidas las elaboraciones que se realizan hoy en día con las tecnologías más avanzadas y las computadoras de hoy, e incluso las pruebas matemáticas que la humanidad ha ido recopilando a lo largo de su historia.

De hecho, todas las máquinas que se conocen se remontan al modelo extremadamente simple de Turing. Por ejemplo, incluso las computadoras más complejas de la actualidad se pueden atribuir a este modelo:

Con este razonamiento se obtienen máquinas formales que, en principio, se remontan a las MdT introducidas inicialmente, pero que se pueden programar con mucha más facilidad y, sobre todo, que se pueden fabricar con las tecnologías disponibles en la actualidad. Demostrar que una de estas máquinas puede resolver un determinado problema significa demostrar que TM también puede resolverlo. La conclusión es que todos los cálculos que pueden realizar las máquinas que conocemos también pueden ser realizados por MdT.

Una máquina que le permite resolver todos los problemas que también puede resolver MdT se llama "equivalente de Turing". La conclusión es que todos los cómputos que puede realizar el MdT también pueden realizarlos todas las máquinas cuya equivalencia con el MdT sea capaz de demostrarse.

Por lo tanto, la importancia de MdT es doble: no solo es el modelo de máquina teórico más "poderoso" conocido, sino que también puede usarse para probar el poder de nuevos modelos teóricos. También es posible demostrar la equivalencia con el MdT usando un modelo más simple que ya se sabe que es equivalente a Turing. Esto le permite reutilizar fácilmente, para un determinado modelo de máquina, los resultados teóricos obtenidos para otros modelos de máquina.
Además, MdT y otros modelos se pueden utilizar para demostrar las capacidades computacionales de los lenguajes de programación (como se demuestran las capacidades de las respectivas máquinas abstractas ).

Todas estas consideraciones hacen razonable apoyar la conjetura de Church-Turing . Sin embargo, se refieren a la computabilidad de los algoritmos, y no a su manejabilidad : las máquinas equivalentes se fabrican de manera diferente y, por lo tanto, pueden realizar el mismo cálculo con un número diferente de pasos o desperdicio de recursos (memoria, tiempo y otros). Por ejemplo, un cálculo que la computadora actual realiza en unos pocos segundos requeriría una enorme cantidad de pasos si se realizara en un mecanismo equipado con dispositivos operativos extremadamente simples como los de TM. En resumen, diferentes máquinas pueden resolver los mismos problemas con programas que tienen diferente complejidad computacional .

El problema de la detención y su indecidibilidad

En algunas circunstancias puede ser útil considerar una MT que tiene una evolución ilimitada (de hecho, los recursos de espacio y tiempo disponibles para la máquina se consideran infinitos). Por ejemplo, es interesante hacer un MdT que genere los elementos de una sucesión de objetos (por ejemplo, los números primos posteriores, o los números de Mersenne posteriores , o los dígitos decimales posteriores de un número ) procedan "ilimitadamente" (es decir, " lo que es útil") irracional como pi ). En otros casos, sin embargo, una evolución ilimitada de una MT se considera un fracaso. Cuando quieres que una MT busque un elemento con unas determinadas características en un conjunto contable y prosigue con la búsqueda sin dar ninguna indicación, te encuentras en una situación decididamente insatisfactoria: no sabes si interrumpir un procesamiento inútil o volver a esperar. un resultado que podría proporcionarse después de más trabajo en un marco de tiempo aceptable.

Por lo tanto, es importante poder establecer si un MdT, u otro sistema formal equivalente (el "cálculo lambda" de Church, por ejemplo), cuando se le envía una cadena (de datos), se detiene o no. A esto se le llama problema de parada o problema de parada de la máquina de Turing. Hay casos en los que se demuestra o comprueba que existe una detención, casos en los que se demuestra que la evolución no se detiene sino que puede continuar indefinidamente y casos en los que no se sabe respuesta.

Parece razonable buscar un procedimiento general para decidir uno de estos problemas. Dado que los MdT demuestran ser capaces de resolver todos los problemas que pueden resolverse con los demás procedimientos conocidos, tiene sentido preguntarse si existe una máquina de Turing capaz de decidir para cualquier par (M, d) constituido por un MdT M y de una cadena de datos d si, cuando se suministra desde M, evoluciona hasta detenerse o no. Esta solicitud se hace aún más significativa por la existencia, demostrada por el propio Turing, de una máquina de Turing llamada universal , una máquina capaz de simular cualquier evolución de cualquier MdT (¡incluso sus propias evoluciones!). Bueno, Turing ha demostrado que la máquina de Turing universal no es capaz de decidir el problema de la detención en todos los casos. Así que ninguna máquina de Turing puede hacer eso. Este resultado negativo se expresa diciendo que el problema de la detención es Turing-indecidible . Si aceptamos la conjetura de Church-Turing sobre el alcance de la máquina de Turing, concluimos que el problema de detener la máquina de Turing es indecidible.

Este resultado negativo constituye un límite para todos los mecanismos computacionales; constituye un resultado limitante de gran importancia general y para el estudio de algoritmos. La importancia general depende del hecho de que todo procedimiento de demostración automático es equivalente a un cálculo que se puede realizar con una máquina de Turing. Cabe señalar que la indecidibilidad de Turing del problema de parada demuestra ser equivalente al teorema de incompletitud de Gödel , el primer resultado limitante fundamental para las matemáticas. También se encuentra en el estudio de los algoritmos y su complejidad que muchos otros resultados limitantes pueden deducirse bastante fácilmente de la indecidibilidad de la detención.

Historia

Máquina de computación

La noción de "máquina computacional" tiene un origen anterior a los trabajos de Turing, Robin Gandy (1919-1995) - alumno de Alan Turing (1912-1954) y posteriormente amigo de toda la vida [5] - remonta su linaje a partir de Charles Babbage (1834).

Así es como describe la " teoría de Babbage ": que todo el desarrollo y las operaciones de análisis ahora pueden ser ejecutados por maquinaria . [6] (Por lo tanto, toda la forma de desarrollar y realizar operaciones de análisis puede ser realizada por una sola máquina).

El análisis de Gandy del motor analítico de Babbage deriva las siguientes operaciones [7] :

  1. Las funciones aritméticas +, -, ×, donde - indica una resta "adecuada": x - y = 0 si y ≥ x.
  2. Cualquier secuencia de operaciones es una operación.
  3. Iteración de una operación (repetir n veces una operación P).
  4. Iteración condicional (repetir n veces una operación P condicionada al "éxito" de la prueba T).
  5. Transferencia condicional (es decir, "goto" condicional). [8]

o

  1. Las funciones aritméticas +, -, ×, donde - denota la resta "en el sentido propio": x - y = 0 si y ≥ x.
  2. Cualquier secuencia de operaciones es una operación.
  3. La iteración de una operación (repetir la operación P un cierto número de veces).
  4. La iteración condicionada (repetir varias veces una operación P condicionada por el "éxito" de la prueba T).
  5. La transferencia condicional (es decir, condicional " goto ").

Gandy argumenta que "las funciones que se pueden calcular a partir de (1), (2) y (4) son precisamente las calculadas por Turing". [7] .

También cita otras "máquinas informáticas universales", incluidas las de Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken ( 1937).

La constante fundamental es programar un número fijo de secuencias de operaciones aritméticas (incluso si las características importantes de la interacción condicional y la transferencia condicional para la teoría computacional de una máquina no se reconocen universalmente). [8]

El problema de decisión (Entscheidungsproblem): la décima pregunta de Hilbert

Si bien es innegable el valor de las preguntas planteadas por el célebre matemático David Hilbert en 1900, hay que tener en cuenta que un aspecto de la décima parte de los problemas que planteó derivó durante al menos treinta años sin fijarse de forma precisa.

La formulación original de Hilbert para el décimo problema es la siguiente:

10. Determinación de la solucionabilidad de una ecuación diofántica . Dada una ecuación diofántica con cualquier cantidad 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 resoluble en números enteros racionales. El Entscheidungsproblem [problema de decisión para la lógica de primer orden] se resuelve cuando conocemos un procedimiento que permite que cualquier expresión lógica dada 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. [9] (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 enteros racionales: diseñar un procedimiento mediante el cual sea posible establecer, en un número finito de operaciones, si el La ecuación es resoluble en enteros racionales. El Entscheidungsproblem (problema de decisión para la lógica de primer orden) se resuelve cuando llegamos a un procedimiento que nos permite decidir a través de un número finito de expresiones la validez o satisfacibilidad para cualquier expresión lógica dada. (... ) El Entscheidungsproblem debe ser considerado el principal problema de la lógica matemática (...)).

Ya en 1922 esta noción de Entscheidungsproblem fue desarrollada por Heinrich Behmann :

(...) la forma más general del Entscheidungsproblem [es] como sigue: Se requiere una prescripción general bastante definida que permita decidir en un número finito de pasos la verdad o falsedad de una afirmación dada puramente lógica... Behmann comenta que... el problema general es equivalente al problema de decidir qué proposiciones matemáticas son verdaderas. Si uno pudiera resolver el Entscheidungsproblem, entonces tendría un "procedimiento para resolver muchos (o incluso todos) los problemas matemáticos". [10]

((...) sigue la fórmula más general del Entscheidungsproblem: Se requiere una prescripción suficientemente definida y de aplicación general que nos permita decidir en un número finito de pasajes la verdad o falsedad de una afirmación puramente lógica dada. Behmann observa: ( (...) ...) el problema general coincide con el problema de decidir qué proposiciones matemáticas son verdaderas (...) Si alguien fuera capaz de resolver el Entscheidungsproblem, entonces tendría un "procedimiento para resolver la mayoría (o incluso todos) problemas matemáticos").

En 1928 en el Congreso Internacional de Matemáticos , el propio Hilbert "formuló su pregunta con bastante precisión. Primero, si las matemáticas son completas, (...) segundo, si es consistente, (...) tercero, si es decidible" (Hodges [ 11] ). Kurt Gödel respondió a las dos primeras preguntas en 1930 (en la misma conferencia donde Hilbert pronunció su discurso de despedida); el tercero, el Entscheidungsproblem, tuvo que esperar hasta mediados de la década de 1930. El problema era que una respuesta requería una definición precisa de " prescripción definida de aplicación general ", o, como la llamará el profesor Alonzo Church de Princeton, "computabilidad efectiva", y en 1928 no existía ninguna.

Sin embargo, en los años siguientes, Emil Post desarrolló una definición para "un trabajador capaz de moverse entre diferentes lugares, escribiendo y borrando signos de acuerdo con una lista de instrucciones" (1936), y de manera similar hicieron Church y algunos de sus estudiantes ( Stephen Kleene y JB Rosser ) con cálculo lambda y la teoría de funciones recursivas primitivas de Gödel (1934). El informe de Church (publicado en abril de 1936) resolvió el Entscheidungsproblem mostrando su indecidibilidad, superando al tiempo de Turing (cuya teoría se formuló en mayo de 1936 pero se publicó recién en 1937). (Mientras tanto, Post también trabajó en el tema, sin embargo, ubicándose en el otoño de 1936, y luego en Turing). Sin embargo, la obra de Turing difiere notablemente de las obras de Church y Post, caracterizándose por la construcción directa de un argumento que partía de los principios fundantes de la cuestión (Hodges [12] ).

La máquina de Alan Turing

En la primavera de 1935, Turing, como joven estudiante de maestría en King's College, Cambridge , aceptó el desafío. Había sido estimulado por las lecciones del lógico Max Newman , quien lo introdujo en la obra de Gödel y en el Entscheidungsproblem (problema de parada) [13] , las últimas fronteras del conocimiento matemático. Newman planteó la pregunta sobre el concepto de "proceso mecánico" como un medio para analizar el problema de Hilbert, una elección muy criticada por la comunidad matemática inglesa. En el obituario de Turing de 1955, Newman escribe:

A la pregunta '¿qué es un proceso "mecánico"?' Turing devolvió la característica respuesta 'Algo que puede ser hecho por una máquina' y se embarcó en la muy agradable tarea de analizar la noción general de una máquina de computación.

—Gandy pág. 74 [14]

Cuando se le preguntó "¿qué es un proceso mecánico?" Turing devolvió la respuesta característica "Algo que puede hacer una máquina" y se embarcó en la muy agradable tarea de analizar la noción general de una máquina informática.

Gandi escribe:

Supongo, pero no lo sé, que Turing, desde el comienzo de su trabajo, tuvo como objetivo una prueba de la indecidibilidad del Entscheidungsproblem. Me dijo que la 'idea principal' del artículo se le ocurrió cuando yacía en los prados de Grantchester en el verano de 1935. La 'idea principal' podría haber sido su análisis de la computación o su comprensión de que había una máquina universal. , y así un argumento diagonal para probar la insolubilidad (...)

- ibíd., p. 76 [15]

Supongo, pero no lo sé, que Turing, desde el comienzo mismo de su trabajo, tuvo como objetivo probar la indecidibilidad del Entscheidungsproblem. Me dijo que la idea principal del documento se le ocurrió cuando yacía en los prados de Grantchester en el verano de 1935. La idea principal puede haber sido su análisis del cálculo, o su comprensión de que había una máquina universal y por lo tanto un argumento diagonal para probar su insolvencia (...)

La idea principal de Turing era que el Entscheidungsproblem de Hilbert podía resolverse a través de un proceso mecánico por una máquina (que luego se teorizó como TM) y aunque le llegó como una iluminación juvenil de una gran mente, en realidad tenía más profundidad. De hecho, Turing había mostrado durante toda su vida un interés por las máquinas, a partir de reflexiones infantiles sobre la máquina de escribir de su madre , quien intentaba extrapolar sus características, que la determinaban precisamente como máquina [16] .

Su tesis doctoral, titulada " Sistemas de Lógica Basados ​​en Ordinales ", contiene la siguiente definición de una "función computable":

Se afirmó anteriormente que 'una función es efectivamente calculable si sus valores se pueden encontrar mediante algún proceso puramente mecánico'. Podemos tomar esta afirmación al pie de la letra, entendiendo por proceso puramente mecánico el que podría ser realizado por una máquina. Es posible dar una descripción matemática, en cierta forma normal, de las estructuras de estas máquinas. El desarrollo de estas ideas conduce a la definición del autor de una función computable ya una identificación de computabilidad con calculabilidad efectiva. No es difícil, aunque algo laborioso, probar que estas tres definiciones [la tercera es el cálculo λ] son ​​equivalentes.

- Turing (1939) en El indecidible [17]

Anteriormente se afirmó que "una función es realmente computable si sus valores pueden determinarse mediante un proceso puramente mecánico". Podemos tomar esta declaración literalmente, entendiendo por "proceso puramente mecánico" lo que podría realizar una máquina. Es posible proporcionar una descripción matemática, en alguna forma normal, de las estructuras de estas máquinas. El desarrollo de estas ideas conduce a la definición del autor de una función computable ya la identificación del concepto de computabilidad con el de computabilidad efectiva. No es difícil, aunque un poco laborioso, demostrar que estas tres definiciones [la tercera es el cálculo λ] son ​​equivalentes.

Cuando Turing regresó a Inglaterra, después de un período de entrenamiento en la universidad de Princeton , el gobierno británico lo empleó en el campo de guerra para descifrar los códigos secretos alemanes creados por la máquina criptográfica Enigma .

Luego estuvo involucrado en el diseño del ACE (Automatic Computing Engine): "La propuesta ACE [de Turing] era efectivamente autónoma y sus raíces no se encontraban en el EDVAC [la iniciativa estadounidense], sino en su propia máquina universal" (Hodges [ 18] ). Continuando así con el desarrollo de los argumentos sobre el origen y la naturaleza de lo que Kleene (1952) denominó como la “tesis de Turing”.

Pero lo que Turing demostró con su modelo de máquina computacional sólo apareció de forma definitiva en su artículo " Sobre los números computables, con una aplicación al problema Entscheidung " (1937). De hecho, en este artículo conceptualiza por primera vez lo que se convertirá en la máquina de Turing:

[que] el problema de Hilbert Entscheidung no puede tener solución... Por lo tanto, propongo mostrar que no puede haber un proceso general para determinar si una fórmula dada U del cálculo funcional K es demostrable, es decir, que no puede haber una máquina que, suministrada con cualquier U de estas fórmulas, eventualmente dirá si U es demostrable.

- El Indecidible [19]

[que] el "problema de parada" de Hilbert no puede tener una solución ... Propongo, por lo tanto, mostrar que no puede haber un proceso general para determinar si una fórmula U dada del cálculo funcional K es demostrable, es decir, que no puede haber ningún máquina a la que, dada cualquier U de estas fórmulas, eventualmente dirá si U es demostrable.

1937–1970: La "computadora digital", el nacimiento de la "tecnología de la información"

En 1937 en Princeton, mientras trabajaba en su tesis doctoral, Turing construyó un multiplicador eléctrico desde el principio, fabricando sus propios transmisores electromecánicos. "La tarea de Alan era incorporar el diseño lógico de una máquina de Turing en una red de transmisores operados por interruptores..." [20] . Mientras que Turing al principio parecía simplemente curioso, otros iban en la misma dirección tanto en Alemania ( Konrad Zuse , 1938) como en los Estados Unidos ( Howard Aiken y George Stibitz , 1937); los frutos de su trabajo fueron utilizados por los soldados del Eje y los Aliados en la Segunda Guerra Mundial [21] .

En la primera mitad de la década de 1950, Hao Wang y Marvin Minsky redujeron la máquina de Turing a una forma más simple (un precursor de la máquina desarrollada más tarde por Martin Davis ); al mismo tiempo, los investigadores europeos también estaban reduciendo la nueva computadora electrónica a un objeto teórico similar a lo que se denominó la "máquina de Turing".

A fines de la década de 1950 y principios de la de 1960, los desarrollos paralelos y coincidentes de Melzak y Lambek (1961), Minsky (1961) y Shepherdson y Sturgis (1961) impulsaron el trabajo europeo y redujeron la máquina de Turing a una computadora más intuitiva, similar a un modelo abstracto llamado "contador de máquina"; Elgot y Robinson (1964), Hartmanis (1971), Cook y Reckhow (1973) desarrollaron aún más el diseño con los modelos de "máquina de registro" y "máquina de acceso aleatorio", pero básicamente todos ellos son "máquinas de Turing de múltiples cintas". con conjuntos de instrucciones aritméticas adicionales.

1970-presente: la máquina de Turing como modelo computacional

Hoy en día, las máquinas de computación, registro y acceso aleatorio, y su procreadora máquina de Turing, siguen siendo los modelos elegidos por los teóricos que estudian cuestiones relacionadas con la teoría de la computación. En particular, la teoría de la complejidad computacional hace uso de la máquina de Turing .

Sobre la base de los objetos que se van a manipular en el cálculo (enteros no negativos o cadenas alfanuméricas), dos modelos han ganado una posición dominante en la teoría compleja basada en máquinas: la TM multicinta fuera de línea y la máquina de acceso aleatorio ( RAM) de Cook y Reckhow , aunque este último asume un papel principal solo en las áreas relacionadas con el análisis de algoritmos. [22]

Variantes de la máquina de Turing

En este párrafo se presentan en términos discursivos las principales variantes de la TM definidas anteriormente, dejando las consideraciones más precisas y completas para artículos específicos.

Máquina de Turing Multinaster

El MdT con más cintas difiere sustancialmente del clásico por el tipo de función de transición; este en el caso de las 3 cintas tiene la forma

.

Esta función hace que la transición dependa de lo que se lea en las casillas en las que se encuentran las cabezas de las distintas cintas y establece qué caracteres se deben cambiar en las distintas cintas y cómo se deben mover las cabezas en caso necesario.

Es bastante evidente que esta máquina es más fácil de usar que la clásica. P.ej. con él puede copiar fácilmente cadenas de una cinta a otra y con porciones de cinta puede hacer que estén disponibles secuencias de memorias que pueden abordarse con bastante facilidad. Con una máquina de tres cintas puede implementar muy fácilmente una operación aritmética como la suma de dos números expresados ​​por dígitos decimales. De igual forma y con las debidas precauciones y con el uso de otros registros apropiados, se puede entender que es posible implementar otras operaciones aritméticas u operaciones sobre entidades discretas.

Para demostrar que una máquina con varias correas P tiene la misma capacidad que las de una sola correa, es necesario identificar una de estas, denominémosla M, lo que permite simular sus evoluciones. Esta simulación se realiza simulando en una sola cinta de la M las múltiples cintas de la P. Es posible tener configuraciones de la M que simulen configuraciones de la P utilizando escrituras particulares que separan las zonas en las que se encuentran las diferentes cintas de la P se reproducen e indican las posiciones en las que encontrará los distintos cabezales de E/S. A cada paso de la P se hace corresponder una serie de pasos de la M con los que se disponen las diversas cintas y las posiciones de las cabezas relativas. Se puede entender cómo con un gran número de desplazamientos y cambios de estado se pueden simular los movimientos de P.

Máquina de Turing con memoria bidimensional

Permite simular con bastante facilidad máquinas con múltiples cintas y realizar elaboraciones gráficas. Otras variantes pueden hacer uso de memorias tridimensionales y similares.

Máquina de Turing no determinista

La máquina de Turing no determinista se diferencia de la determinista definida anteriormente por el hecho de que, en presencia de un estado determinado y una lectura de carácter determinada, permite más transiciones.

Definición

Una máquina de Turing no determinista T, con grado de no determinismo , se define como sigue:

donde las únicas diferencias con respecto a la definición inicial son la presencia del entero n y el género de la función de transición:

Por lo tanto, sus configuraciones consisten en conjuntos finitos de configuraciones deterministas, cuya cardinalidad podría crecer indefinidamente a medida que avanza la evolución.

Los cómputos que es capaz de realizar pueden describirse como conjuntos de cómputos desarrollados por réplicas de MdT determinista, réplicas que podrían ser necesarias en cada paso de la evolución. Se advierte que esta solicitud hoy en día no debe sorprender en absoluto, ya que se puede lograr con las técnicas de computadoras conectadas a la red y efectivamente implementadas en la práctica del procesamiento distribuido.

Equivalencia con TM clásica

Dado que toda máquina determinista puede considerarse una máquina no determinista particular, se trata de demostrar que con una máquina determinista M es posible simular el comportamiento de una máquina no determinista N. Más precisamente, supongamos que N es una máquina de una sola correa y que la M es una máquina que tiene una memoria bidimensional, una memoria similar a la disponibilidad de múltiples cintas cuyo número se puede aumentar. La máquina M es capaz de simular con cada uno de sus estados los múltiples estados de la máquina N y con sus muchas cintas las únicas cintas replicadas de la N. Para cada paso de la N, la M empareja una serie de pasos con los que realiza la evolucionan las diferentes cintas que representa en su memoria bidimensional y, en correspondencia con una transición no determinista de multiplicidad k, replica la cinta en cuestión, transformándola en las k cintas requeridas.

De esta forma podemos ver cómo la máquina M puede simular la N. Se observa que algunos pasos únicos de la máquina no determinista requieren un gran número de pasos y estados específicos de la determinista.

Equivalencia entre cintas MdT ak y MdT a una cinta

La capacidad computacional de un MdT no depende del número de cintas que utilice; esto se puede demostrar a través de la simulación. Denotamos con T k la máquina de Turing con k cintas y con T la que tiene una cinta. Escribimos la entrada de la máquina T k en la máquina T obviamente un símbolo para cada celda, cuando la máquina T lee el primer símbolo necesitará leer k caracteres para realizar un quíntuple de máquina T k , recordando el k-ésimo carácter leído cada vez ; habiendo verificado que se puede ejecutar el quíntuple, en este punto traerá de vuelta la cabeza de k celdas y podrá proceder con la ejecución del quíntuple sobreescribiendo los k caracteres; en este punto, el encabezado estará en la celda que contiene el último carácter escrito. Los pasos finales son el cambio de estado interno y el movimiento de la cabeza. Es fácil ver como el conjunto de estados de T tiene mayor cardinalidad que el conjunto de estados de T k.

Máquinas de Turing simplificadas

Las máquinas de Turing se pueden simplificar aún más, sin pérdida del alcance computacional. Las posibles simplificaciones son (no factibles al mismo tiempo):

  1. cinta ilimitada en una sola dirección;
  2. alfabeto de solo dos caracteres, uno de los cuales el símbolo en blanco;
  3. solo dos estados.

La prueba de equivalencia con la máquina definida inicialmente con las de características 2 y 3 constituye el primer teorema de Shannon .

Otro modelo simplificado de MdT es tener tres MdT que realicen operaciones elementales (escribir el carácter 1, escribir el símbolo en blanco, mover la cabeza hacia la derecha, mover la izquierda, ninguna operación) y obtener de estos un nuevo MdT al componer para la rama .

Máquina Universal de Turing

La máquina de Turing universal es la que calcula la función u, que a su vez es capaz de simular el comportamiento de cualquier máquina de Turing. La función u toma como entrada una codificación de la máquina M a ejecutar (es decir, un número que una vez decodificado proporciona el código de M) y una codificación de los parámetros iniciales a M.

Comparación con máquinas reales

La máquina de Turing, a pesar de ser una "máquina definida abstractamente" [23] , es un modelo excelente para describir máquinas reales. Aquí hay algunos argumentos:

  1. Todo lo que puede calcular una computadora real, lo puede hacer un MdT. Por ejemplo: "Una máquina de Turing puede simular cualquier tipo de subrutina que se encuentra en los lenguajes de programación, incluidos los procedimientos recursivos y cualquiera de los parámetros de paso conocidos del mecanismo" ( Hocroft y Ullman [24] ) . Incluso un autómata de estado finito (FSA) lo suficientemente grande puede imitar cualquier computadora real, descuidando el IO. Por lo tanto, un estatuto sobre las limitaciones de la máquina de Turing también se aplicaría a las computadoras reales.
  2. La diferencia está solo en la capacidad de una MT para manipular una cantidad ilimitada de datos. Sin embargo, dado un tiempo finito, un MdT (como una máquina real) puede procesar una cantidad finita de datos.
  3. Al igual que un MdT, una máquina real puede ampliar su espacio de almacenamiento según sea necesario mediante la adquisición de discos adicionales u otros sistemas de almacenamiento.
  4. Las descripciones de programas para máquinas reales, utilizando modelos abstractos simples, suelen ser mucho más complejas que las descripciones obtenidas utilizando la máquina de Turing. Por ejemplo, un MdT puede tomar unos pocos cientos de etapas que describen un algoritmo, mientras que un autómata determinista de estado finito (DFA) equivalente proporcionaría cuatrillones de ellas a partir de una máquina real dada. Esto hace que las representaciones de la DFA sean imposibles de analizar.
  5. Las máquinas de Turing describen algoritmos independientemente de la cantidad de memoria que utilicen. Cada máquina actual tiene límites de memoria limitados, pero estos límites pueden extenderse arbitrariamente con el tiempo. Las máquinas de Turing nos permiten producir declaraciones de algoritmos que (teóricamente) tendrán un valor eterno, independientemente de la evolución en la arquitectura convencional de la mecánica informática.
  6. Los MdT simplifican los postulados de los algoritmos. De hecho, los algoritmos que se ejecutan en una máquina abstracta equivalente a Turing son generalmente más abstractos que sus contrapartes en máquinas reales, porque tienen una precisión arbitraria de los posibles tipos de datos y nunca deben tener en cuenta condiciones imprevistas (incluidas, entre otras, casos de memoria limitada).

Notas

  1. ^ Máquina de Turing en "Enciclopedia de ciencia y tecnología" , en www.treccani.it . Consultado el 19 de julio de 2022 .
  2. ^ Douglas R. Hofstadter, Alan Turing: el enigma , Edición del centenario, Princeton University Press, 2012, ISBN  978-1-4008-4497-5 , OCLC  795331143 . Consultado el 19 de julio de 2022 .
  3. ^ Go¨del, Turing , CRC Press, 14 de octubre de 2011, págs. 23–53, ISBN 978-0-203-16957-5 . Consultado el 19 de julio de 2022 .  
  4. ^ ^ Máquina analítica de Babbage, 1834-1871. (Modelo de prueba) Archivado el 20 de septiembre de 2010 en Internet Archive . - Museo de Ciencias, Londres
  5. ^ Gandy, Robin Oliver, Sobre sistemas axiomáticos en matemáticas y teorías en física .
  6. ^ Robin Gandy, La confluencia de ideas en 1936 , p. 54.
  7. ^ a b Robin Gandy, La confluencia de ideas en 1936 , p. 53.
  8. ^ a b Robin Gandy, La confluencia de ideas en 1936 , págs. 52-53.
  9. ^ N. Dershowitz e Y. Gurevich, Una axiomatización natural de la computabilidad y prueba de la tesis de Church , 2008.
  10. ^ Robin Gandy, La confluencia de ideas en 1936 , p. 57.
  11. ^ Andrew Hodges, Alan Turing: El enigma , págs. 126-127.
  12. ^ A. Hodges, Alan Turing. Historia de un enigma , 1991, p. 112.
  13. ^ Andrew Hodges, Alan Turing: El enigma , p. 129.
  14. ^ Robin Gandy, La confluencia de ideas en 1936 , p. 74.
  15. ^ Robin Gandy, La confluencia de ideas en 1936 , p. 76.
  16. ^ Andrew Hodges, Alan Turing Historia de un enigma , págs. 133-134.
  17. ^ A. Turing, El indecidible , p. 160.
  18. ^ Andrew Hodges, Alan Turing: El enigma , p. 318.
  19. ^ A. Turing, El indecidible , p. 145.
  20. ^ Andrew Hodges, Alan Turing: El enigma , p. 138.
  21. ^ Andrew Hodges, Alan Turing: El enigma , págs. 298-299.
  22. ^ van Emde Boas, Modelos de máquinas y simulación , 1990.
  23. ^ AM Turing - Enciclopedia Treccani , en treccani.it .
  24. ^ Hopcroft y Ullman, Introducción a la teoría, lenguajes y computación de autómatas , p. 157.

Bibliografía

Libros

Artículos

Artículos relacionados

Máquinas equivalentes a MdT

Otros proyectos

Enlaces externos

Simuladores