Texto1

la máquina de Turing (MT) como sustituto formal del concepto de algoritmo

0 0 1 1

0 1 0 1

r l h 0

1 0 1 0

índice de materias
• • • • • • • • fundamentos matemáticos Máquina de Turing URM, RAM, introducción histórica basados en lenguajes modelos de cálculo lenguajes WHILE y LOOP funciones µ-recursivas teorema de equivalencia indexaciones y universalidad problemas no resolublesel formalismo propuesto por Turing recibió el nombre de máquina

máquina creatividad
funcionamiento automático objetividad

la máquina de Turing contiene los elementos básicos para el cómputo
programa

condicionales

X almacenamiento

saltos

el concepto de MT se ilustra con un símil mecánico

...

1

1

0

1

1

0

0

0

1

0

1

0

0

...ingredientes básicos para operar con MT’s
U = {a1, ..., an} (a0 ≡ símbolo vacío) configuración conjunto finito de estados cinta infinita de cálculo estado inicial (cM) estado de parada expresión de cinta - paso de computación - instrucción parcial de cálculo - instrucción de cálculo

cuadrado escrutado (CE)∈[-∞,∞]

el conjunto de instrucciones está simplificado
Pasos de computación
ak → permiteescribir el símbolo k-ésimo en el CE r → situar la MT sobre el cuadrado a la derecha del CE l → situar la MT sobre el cuadrado a la izquierda del CE h → dar el cómputo por terminado

la configuración define completamente el estado del cómputo
K=(A, B, C) - A es el CE actual - B es la expresión de cinta actual - C es el estado actual la línea de la configuración k es la línea de la MT de laforma C B(A) b c'

la instrucción de cálculo está representada por una tabla
• la k-ésima instrucción parcial es una subtabla
k k ... k sn bn kn s0 s1 b0 b1 k0 k1

k es el estado actual si es el contenido del CE bi es la instrucción ki es el próximo estado

• la instrucción de cálculo es la unión de las instrucciones parciales

terminología relativa a MT’s
dada una MT M, un número A yuna función B • colocar M en la expresión de cinta B sobre el cuadrado A equivale a hacer K0=(A, B, CM) • M transita en un paso de cómputo de Kn a Kn+1, con Kn+1=F(Kn) • M cesa de operar en la expresión de cinta Bn y sobre el cuadrado An si tras el n-ésimo paso Kn=(An, Bn, Cn), y la línea de la configuración Kn contiene la instrucción h

expresiones matemáticas de la configuración consecutiva
A − 1 si b=l  A' =  A si b ≠ r ∧ b ≠ l  A + 1 si b=r   B ( x ) si x ≠ A  B' ( x ) =  B( x ) si x=A ∧ (b = r ∨ b = l ) b si x = A ∧ b ≠ r ∧ b ≠ l 

C ' = c'

la simplicidad del modelo contrasta con la complejidad de la computación
• función sucesor en decimal
0 0 0 0 0 0 0 0 0 0 0 * 0 1 2 3 4 5 6 7 8 9 l 1 2 3 4 5 6 7 8 9 0 0 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 * h 1 0 r 1 1 r1 2 r 1 3 r 1 4 r 1 5 r 1 6 r 1 7 r 1 8 r 1 9 r 1 2 2 2 2 2 2 2 2 2 2 2 * 0 1 2 3 4 5 6 7 8 9 1 l 2 3 4 5 6 7 8 9 0 1 2 1 1 1 1 1 1 1 1 2

dos MT’s son equivalentes si siguen la misma secuencia de estados
• M1 equivale a M2 si existe una aplicación biunívoca ϕ de los estados de M1 en los de M2, verificándose que
– toda línea de M1 de la forma c a b c’ se traduce en una línea de M2 ϕ(c) a bϕ(c’) – cM2 = ϕ(cM1)

interpretación de la equivalencia
• MT’s equivalentes generan la misma secuencia de pares (Ai, Bi) si se las coloca en la misma expresión de cinta y sobre el mismo cuadrado • si M1 da lugar a las configuraciones (Ai , Bi , Ci), y M2 equivale a M1 por la aplicación ϕ, y se coloca a M2 en B sobre el cuadrado A, M2 genera las configuraciones (Ai , Bi , ϕ(Ci))

equivalenciaen sentido amplio implica la misma transformación de símbolos
• M1 sobre U1 equivale en sentido amplio a M2 sobre U2 si existen aplicaciones biunívocas ϕ y ψ tal que
– ψ es una aplicación de U1 en U2 que verifica ψ(r) = r ψ(l) = l ψ(h) = h – ϕ es una aplicación de los estados de M1 en los de M2 de manera que toda línea de M1 c a b c’ se traduce en una línea de M2 ϕ(c) ψ (a) ψ (b) ϕ(c’) – cM2...