Maquinas De Turing

Unidad 5. Máquinas de Turing
M. En C. José Francisco Delgado Orta.

1

Contenido
 Maquinas de Turing.
 Cómputo de una función parcial con una máquina de Turing.

 Combinación de máquinasde Turing.  Máquinas de Turing con cintas múltiples.  Máquinas de Turing no deterministas.  Máquinas de Turing Universales.

2

Máquinas de Turing
 Prueba de Turing

Máquina lectora decintas

3

La cinta
La máquina de Turing posee una cinta dividida en celdas, cada celda es capaz de almacenar un símbolo.
Además posee una cabeza lectora/escritora que lee y escribe un símbolo enla cinta. Inicialmente la cinta contiene b en todas sus celdas. La función de transición transforma pares (q, ) en ternas de la forma (p, t, X), donde p es el siguiente estado, t es el símboloescrito en la cinta y X es el movimiento de la cabeza lectora/escritora, que puede ser L o R.

a

b

b Estado interno q1

(q1, a) = (q5, b, R)

b

b

b Estado interno q5

Posición de lacabeza lectora/escritora

Posición de la cabeza lectora/escritora

4

Definición
Definimos una máquina de Turing como una 7-tupla donde M = (Q, , , s, b, F, ),

Q es un conjunto finito deestados es un alfabeto de entrada es un alfabeto llamado alfabeto de la cinta s Q es el estado inicial b es el símbolo blanco F Q es el conjunto de estados finales o de aceptación d: Q Q {L, R} es unafunción parcial que se llama función de transición

5

Representación instantánea
Se puede dar una descripción instantánea de la máquina de Turing similar a la de los ADPND, para la transiciónanterior sería

(q1, abb) ├─ (q5, bbb) el carácter subrayado indica la posición de la cabeza lectora/escritora.

Otra posibilidad es anteponer el estado actual al carácter señalado por la cabezalectora/escritora como se muestra

q1abb ├─ bq5bb
6

Máquinas de Turing como aceptadores de lenguajes
Sea M = (Q, , , s, b, F, ) una máquina de Turing. Entonces el lenguaje aceptado por M es L(M) =...