máquina de Turing

En informática teórica , una máquina de Turing es un modelo abstracto del funcionamiento de dispositivos informáticos mecánicos , como una computadora . Este modelo fue ideado por Alan Turing en 1936, con el fin de dar una definición precisa al concepto de algoritmo o "procedimiento mecánico". Todavía se usa ampliamente en la informática teórica , especialmente en los campos de la complejidad algorítmica y la computabilidad .

Originalmente, el concepto de máquina de Turing, inventado antes que la computadora, se suponía que representaba a una persona virtual realizando un procedimiento bien definido, cambiando el contenido de las cajas de una cinta infinita, eligiendo este contenido de un conjunto finito de símbolos . Por otro lado, en cada etapa del procedimiento, la persona debe colocarse en un estado particular entre un conjunto finito de estados. El procedimiento está formulado en términos de pasos elementales como: "si estás en el estado 42 y el símbolo contenido en la celda que estás mirando es" 0 ", reemplaza este símbolo con un" 1 ", ve al estado 17 , y ahora mira el cuadrado adyacente a la derecha ”.

La tesis de Church postula que cualquier problema computacional basado en un procedimiento algorítmico puede ser resuelto por una máquina de Turing. Esta tesis no es un enunciado matemático, ya que no supone una definición precisa de los procedimientos algorítmicos. Por otro lado, es posible definir una noción de “sistema de programación aceptable” y demostrar que la potencia de tales sistemas es equivalente a la de las máquinas de Turing (son Turing-completas ).

Definición

Aunque su nombre de "máquina" pueda llevar a pensar lo contrario, una máquina de Turing es un concepto abstracto, es decir, un objeto matemático. Una máquina de Turing tiene los siguientes componentes:

Una cinta infinita dividida en cuadrados consecutivos. Cada caja contiene un símbolo de un alfabeto finito dado. El alfabeto contiene un símbolo especial llamado "símbolo en blanco" ('0' en los ejemplos que siguen) y uno o más símbolos más. Se supone que la cinta es infinitamente larga a la izquierda o a la derecha, en otras palabras, la máquina siempre debe tener suficiente longitud de cinta para funcionar. Consideramos que las casillas de la cinta contienen por defecto el “símbolo blanco”;
Un cabezal de lectura / escritura que puede leer y escribir símbolos en la cinta y moverse a la izquierda o derecha de la cinta;
Un registro de estado que almacena el estado actual de la máquina de Turing. El número de estados posibles es siempre finito y existe un estado especial llamado "estado de inicio" que es el estado inicial de la máquina antes de su ejecución;
Una tabla de acciones que le dice a la máquina qué símbolo escribir en la cinta, cómo mover el cabezal de reproducción (por ejemplo, " " para un cuadro a la izquierda " " para un cuadro a la derecha) y cuál es el nuevo. Estado , dependiendo del símbolo leído en la cinta y del estado actual de la máquina. Si no existe ninguna acción para una combinación dada de un símbolo de lectura y un estado actual, la máquina se detiene. $\ flecha izquierda$ $\ flecha correcta$

Definicion formal

Se pueden dar varias definiciones formales cercanas entre sí de una máquina de Turing. Aquí se elige uno de ellos, relativamente común. Una máquina de Turing es un quintillizo donde: ${\ Displaystyle (Q, \ Gamma, q_ {0}, \ delta, F)}$

$Q$ es un conjunto finito de estados ;
$\Gama$ es el alfabeto de trabajo de los símbolos de la banda, que contiene un símbolo particular (llamado en blanco ) ; $B$ $B \ in \ Gamma$
$q_0$ es el estado inicial , ; $q_ {0} \ in Q$
$\ delta: Q \ times \ Gamma \ to Q \ times \ Gamma \ times \ {\ leftarrow, \ rightarrow \}$ es la función de transición ;
$F$ es el conjunto de estados de aceptación (o terminales finales) . $F \ subseteq Q$

Es un modelo de una máquina de Turing completa y determinista; es decir, está definida y es única. ${\ Displaystyle \ forall q \ in Q, \ forall \ gamma \ in \ Gamma, \ delta (q, \ gamma)}$

Las flechas en la definición de representan los dos posibles movimientos del cabezal de lectura / escritura, es decir, el movimiento hacia la izquierda y el movimiento hacia la derecha. El significado de esta función de transición se puede explicar en el siguiente ejemplo: significa que si la máquina de Turing está en el estado y lee el símbolo , entonces escribe en lugar de , va al estado y luego mueve su cabezal de reproducción hacia la izquierda. $\delta$ $\ delta (q_ {1}, x) = (q_ {2}, y, \ leftarrow)$ $q_ {1}$ $X$ $y$ $X$ $q_ {2}$

El funcionamiento de la máquina de Turing es entonces el siguiente: en cada etapa de su cálculo, la máquina evoluciona según el estado en el que se encuentra y el símbolo inscrito en la caja de la cinta donde se encuentra el cabezal de lectura. Estos dos datos se utilizan para actualizar el estado de la máquina mediante la función de transición. En el momento inicial, la máquina está en estado y el primer símbolo de la cinta es la entrada del programa. La máquina se detiene cuando entra en un estado terminal. El resultado del cálculo es entonces la palabra formada por los símbolos leídos sucesivamente por la máquina. $q_0$

Podemos restringir un alfabeto de las posibles entradas en la definición. Por tanto, es posible trabajar con más precisión en este alfabeto reservando ciertos símbolos del alfabeto completo para los pasos de cálculo de la máquina. En particular, el símbolo blanco no debe formar parte de la entrada y, por lo tanto, puede definir el final de esta última . $\ Sigma$ $\Gama$ $B$

El primer ejemplo a continuación usa una versión ligeramente diferente de una máquina de Turing en la que una máquina se detiene si está en un estado terminal y lee un cierto carácter en la cinta (aquí el símbolo blanco). El segundo ejemplo a continuación es el primer ejemplo histórico que da Turing en su artículo de 1936: es una máquina que no se detiene.

Ejemplos de

Duplica el número de '1'

La siguiente máquina de Turing tiene un alfabeto {'0', '1'}, siendo '0' el "símbolo blanco". Suponga que la cinta contiene una serie de '1' y que el cabezal de lectura / escritura está inicialmente por encima del '1' situado más a la izquierda. Esta máquina tiene el efecto de duplicar el número de '1', insertando un '0' entre las dos series. Por ejemplo, "111" se convierte en "1110111".
El conjunto de posibles estados de la máquina es {e1, e2, e3, e4, e5} y el estado inicial es e1.
La tabla de acciones es la siguiente:

Ejemplo de una tabla de transición

Estado antiguo	Leer símbolo	Símbolo escrito	Movimiento	Nuevo estado
e1	0	(Detener)
e1	1	0	Derecha	e2
e2	1	1	Derecha	e2
e2	0	0	Derecha	e3
e3	1	1	Derecha	e3
e3	0	1	Izquierda	e4
e4	1	1	Izquierda	e4
e4	0	0	Izquierda	e5
e5	1	1	Izquierda	e5
e5	0	1	Derecha	e1

Ejecutar esta máquina para una serie de dos '1 sería (la posición del cabezal de lectura / escritura en la cinta está escrita en letras rojas y en negrita):

Ejecución (1)

Escenario	Estado	Cinta
1	e1	1 1
2	e2	0 1
3	e2	01 0
4	e3	010 0

Ejecución (2)

Escenario	Estado	Cinta
5	e4	01 0 1
6	e5	0 1 01
7	e5	0 101
8	e1	1 1 01

Ejecución (3)

Escenario	Estado	Cinta
9	e2	10 0 1
10	e3	100 1
11	e3	1001 0
12	e4	100 1 1

Ejecución (4)

Escenario	Estado	Cinta
13	e4	10 0 11
14	e5	1 0 011
15	e1	11 0 11
	(Detener)

El comportamiento de esta máquina se puede describir como un bucle:

Inicia su ejecución en el estado e1, reemplaza el primer 1 por un 0.
Luego usa el estado e2 para moverse hacia la derecha, saltando los 1 (solo uno en este ejemplo) hasta que encuentra un 0 (o un espacio en blanco) y entra en el estado e3.
El estado e3 luego se usa para omitir la siguiente secuencia de 1 (inicialmente ninguno) y reemplazar el primer 0 encontrado con un 1.
El estado e4 permite volver a la izquierda hasta encontrar un 0 y cambiar al estado e5.
El estado e5 permite volver a moverse hacia la izquierda hasta encontrar un 0, inicialmente escrito por el estado e1.
Luego, la máquina reemplaza este 0 por un 1, se mueve una celda hacia la derecha y pasa nuevamente al estado e1 para una nueva iteración del ciclo.

Este proceso se repite hasta que e1 cae en un 0 (es el 0 del medio entre las dos secuencias de 1); en este momento, la máquina se detiene.

Calcular un tercio en binario

En el siguiente ejemplo, la máquina de Turing tiene una cinta vacía y le permite construir la secuencia 01010101010101 ...

Ejemplo de una tabla infinita

Estado antiguo	Símbolo escrito	Movimiento	Nuevo estado
Para	0	Derecha	B
B	1	Derecha	Para

La ejecución de esta máquina sería (la posición del cabezal de lectura / escritura en la cinta está escrita en negrita y magenta ):

Ejecutando la máquina infinita

Escenario	Estado	Cinta
1	Para	0
2	B	0 1
3	Para	01 0
4	B	010 1
5	Para	0101 0
6	B	01010 1
7	Para	010101 0
8	B	0101010 1
...	...	01010101 ...

El comportamiento de esta máquina se puede describir como un bucle infinito:

Comienza su ejecución en el estado a, agrega un 0 y se mueve hacia la derecha.
Luego pasa al estado b, agrega un 1 y se mueve hacia la derecha.
Vuelve al estado ay repite el primer paso.

Esta máquina es la contraparte del cálculo de un tercio cuya escritura en binario es 0.010101010101 ...

Máquinas universales de Turing

Como muestra Alan Turing en su artículo fundamental, es posible crear una máquina de Turing llamada "máquina de Turing universal" que sea capaz de "simular" el comportamiento de cualquier otra máquina de Turing. "Simular" significa que si la máquina de Turing universal recibe como entrada una codificación de una máquina T y datos D , produce el mismo resultado que la máquina T a la que se le darían los datos D como entrada .

Una máquina de Turing universal tiene la capacidad de calcular cualquier cosa que sea computable: entonces decimos que es Turing completo . Al proporcionarle la codificación adecuada, puede simular cualquier función recursiva , analizar cualquier lenguaje recursivo y aceptar cualquier lenguaje parcialmente decidible . Según la tesis de Church-Turing , los problemas que pueden ser resueltos por una máquina universal de Turing son exactamente los problemas que pueden ser resueltos por un algoritmo o por un método de cálculo concreto .

Realización de una máquina de Turing

Una máquina de Turing es un objeto de pensamiento: su cinta es infinita y, por lo tanto, la memoria de una máquina de Turing es infinita. Una máquina de Turing nunca genera un desbordamiento de memoria , a diferencia de una computadora cuya memoria es finita. Al olvidar este problema de memoria, podemos simular una máquina de Turing en una computadora moderna.

También es posible construir máquinas de Turing puramente mecánicas. Así, la máquina de Turing, objeto de pensamiento, ha sido cosificada en numerosas ocasiones utilizando técnicas a veces bastante originales, de las que a continuación se exponen algunos ejemplos:

En abril 2011, Jim MacArthur hizo una máquina Turing mecánica compacta de 5 símbolos con rodamientos de bolas como portador de información en la cinta.
En marzo 2012, con motivo del año de Turing (en) , un equipo de estudiantes de la École normale supérieure de Lyon produjo una máquina de Turing completamente hecha de piezas de Lego sin electrónica.

En diciembre 2013, un prototipo experimental para hacer realidad las máquinas de Turing (electromecánicas: fabricadas con tecnologías de la era de Turing), con una cinta circular y de relativamente fácil programación. Diseñado en dos partes transportables, se puede utilizar para presentaciones y lecciones.
En octubre de 2020, una máquina educativa de Turing diseñada por Thierry Delattre (Dunkerque), programable para algoritmos con un máximo de 12 estados y con un alfabeto de 3 símbolos. Se pueden almacenar 50 algoritmos en la memoria. Una versión con 22 estados y 8 símbolos data de febrero de 2021.

Referencias y bibliografía

Referencias

(en) Harry R. Lewis y Christos Papadimitriou , Elementos de la teoría de la computación . Prentice-Hall , 1982; segunda edición, septiembre de 1997.
"final" , CNRTL: "De hecho, no está flotando entre el final y final : el 1 st parece ser el plur. del lang. Tribunal. y escritores, el segundo de lingüistas y economistas ” .
Kévin Perrot, “ Calculabilidad. Curso 1: Máquinas de Turing ” , en univ-mrs.fr ,primavera 2019(consultado en noviembre de 2020 )
(en) Jim MacArthur, " Turing Machine " , en srimech.blogspot.fr ,8 de junio de 2012(consultado el 20 de febrero de 2018 ) .
" Proyecto RUBENS " , en rubens.ens-lyon.fr ,marzo 2012(consultado el 20 de febrero de 2018 ) .
David Larousserie, Le Monde , " Una máquina completamente mecánica a la que no le falta aire " , en lemonde.fr ,22 de junio de 2012(consultado el 20 de febrero de 2018 ) .
Marc Raynaud, " A Programmable Prototype to Realize the Turing Machine " , en machinedeturing.org (consultado el 19 de febrero de 2018 ) .
Ouest-France , " Marc Raynaud, un culto inventor matemático " , en ouest-france.fr ,14 de febrero de 2018(consultado el 14 de septiembre de 2020 ) .
" Turing Machine - Code tiene animaciones de luz atractivas, cálculos matemáticos en números binarios, series de números o cualquier otra aplicación que pueda inventar en su tiempo libre". » (Consultado el 19 de marzo de 2021 )

Bibliografía

Manuales

Olivier Carton, Lenguajes formales, computabilidad y complejidad: licenciatura y maestría en matemáticas o informática, opción informática de la agregación de las matemáticas , París, Vuibert ,2008, 237 p. ( ISBN 978-2-7117-2077-4 , SUDOC 128299258 ) ;
Jean-Michel Autebert, Computabilidad y decidabilidad , París, Masson,1992, 118 p. ( ISBN 978-2-225-82632-0 , SUDOC 002676494 ) ;
Éric Jacopin, Les machines de Turing: Introducción a la caracterización de la complejidad de un problema , Toulouse, Éditions Cépaduès ,2009, 264 p. ( ISBN 978-2-85428-865-0 , SUDOC 132323214 ) ;

Turing

Alan Turing y Jean-Yves Girard , La machine de Turing , París, Éditions du Seuil,1995, 192 p. [ detalle de la edición ] ( ISBN 9782020369282 ) ; este trabajo incluye en particular una traducción al francés (por Julien Basch y Patrice Blanchard) del artículo original, así como una corrección por Emil Post de los errores que allí aparecen;
(en) Alan Turing, " Sobre números computables, con una aplicación al problema de Entscheidung ", Actas de la Sociedad Matemática de Londres, Serie 2 , vol. 45,1936, p. 230-265 ( leer en línea ) ;
(fr) Alan Turing, Précis of 'Computable Numbers' ( leer en línea ). - Un borrador para una Nota a las Interpretaciones de la Academia de Ciencias de París.

Kleene

Stephen Cole Kleene , Introducción a las metamatemáticas , Amsterdam, Holanda Septentrional,1952, x + 550 p. ( SUDOC 005505526 , presentación en línea ) - Numerosas reimpresiones, en 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009 en particular por Wolters-Noordhoff (Groningen) ( ISBN 0720421039 ) , según el aviso Sudoc. Muchas traducciones.
(en) , (fr) Stephen Cole Kleene, Lógica matemática , Dover ,1967- Reimpresión Reimpresión de Dover, 2001, ( ISBN 0-486-42533-9 ) . Traducción al francés de Jean Largeault , Logique mathématique , Armand Colin, 1971 y Gabay 1987 ( ISBN 2-87647-005-5 ) .

: documento utilizado como fuente para este artículo.

Ver también

enlaces externos

La película "La máquina de Turing realizada" de Christophe Gombert y Hugo Deboise para ver en línea de forma gratuita.
El genio interrumpido de Alan Turing : presentación y bibliografía de una conferencia de la BnF a cargo de Bernard Chazelle , programada para el19 de marzo de 2014
Hamdi Ben Abdallah, “ ¿Cómo funciona una máquina de Turing? », Intersticios ,22 de marzo de 2013( leer en línea ), artículo que permite probar una máquina de Turing.