Maquinas De Turing

Máquina de Turing

Para otros usos de este término, véase Turing (desambiguación).

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.

La máquina de Turing fue descrita por Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society,1 La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.

Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en:

...una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.2 (Turing 1948, p. 61)

Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una teoría formal de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing capturan, de hecho, la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una definición precisa de un algoritmo o 'procedimiento mecánico'.

Estudiando sus propiedades abstractas, la máquina de Turing produce muchas perspectivas en las ciencias de la computación y en la teoría de la complejidad.

Índice

[ocultar]

• 1 Historia

• 2 Descripción informal

• 3 Definición formal

o 3.1 Funcionamiento

o 3.2 Representación como diagrama de estados

o 3.3 Descripción instantánea

• 4 Ejemplo

• 5 Modificaciones equivalentes

o 5.1 Máquina de Turing con movimiento stay o "esperar"

o 5.2 Máquina de Turing con cinta infinita a ambos lados

o 5.3 Máquina de Turing con cinta multipista

o 5.4 Máquina de Turingmulticinta

o 5.5 Máquina de Turing multidimensional

• 6 Máquina de Turing determinista y no determinista

• 7 Problema de la parada (haltingproblem)

• 8 Codificación de una máquina de Turing

• 9 Máquina de Turing universal

• 10 Máquina de Turing cuántica

• 11 Véase también

• 12 Referencias

o 12.1 Notas al pie

o 12.2 Bibliografía

• 13 Enlaces externos

Historia[editar]

Estatua de Turing en la Universidad de Surrey.

Representación artística de una máquina deTuring.

Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, withanapplicationtothe Entscheidungsproblem, publicado por la Sociedad Matemática de Londres en 1936, en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver.

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.

Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing.3

La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible.

Descripción informal[editar]

Aquí se muestra el estado interno (q1) dentro del cabezal, y la ilustración describe la cinta como siendo infinita y lledada previamente con '0', el símbolo sirviendo como blanco. El estado completo del sistema (su configuración) consiste del estado interno, el contenido de las casillas sombreadas incluyendo

...