El lenguaje generado por una maquina de Turing son las palabras formadas (cada una) por todo lo que queda en la cinta al llegar al estado final.
Cada palabra generada es una distinta ejecución que ha dejado distintos carácteres en la cinta.
Se dice que una MT calcula una funcion φ(w) = w' donde w' es lo que queda en la cinta.
Decimos que una maquina M es M(w)↓ si M con entrada w PARA en algun momento. Es M(w)↑ si NO PARA (bucle).
φMw↓ si φM sí está definida (M llega a estado final).
φMw↑ si φM no está definida (M no llega a estado final).
φM (w)↓ => M(w)↓ pero no al revés ( <= ).
DEF: Un lenguaje L es semi-deducible si existe M tal que LM = L
DEF: Una función f es calculable si existe M tal que φM = f
DEF: Un lenguaje es deducible si existe M tal que LM = L y M siempre para. 0
- Cualquier algoritmo puede ser simulado por una MT (Tesis de Church-Turing)
- Podemos suponer que los estados de una MT son numeros naturales w € Σ*
- Supondremos que las entradas son "correctas"
- Trabajamos con MT en "alto nivel"
- Las MT se pueden ordenar y codificar. Este proceso es constructivo -> existe una MT que recive como entrada otra MT y devuelve su número (número de Gödel)
- Existe uan MT que simula cualquier otra MT con cualquier entrada -> Máquina Universal U(m, w) donde m es una MT i w es la entrada de m. U simula m con la entrada w.
- Existe una MT que simula cualquier otra MT con cualquier entrada i cualquier número de pasos -> Máquina Reloj R(m, w, t) donde t es el número de pasos a simular. Si la ejecucion de m con entrada w es infinita, la ejecución de U(m, w) también lo es. La Máquina Reloj sirve para parar donde queramos.
Si:
- Mn es la MT de posición n
- Ln es el lenguaje reconocido por la MT de posición n
- φn es la función calculada por la MT de posición n
Entonces:
- L semi-deducible ≣ ∃ n : Ln = L
- f calculable ≣ ∃ n : φn = f
- L decidible ≣ ∃ n : Ln = L ^ ∀ n : Mn(M)↓