Sistemas computaconales

Demostración del problema del paro (Halting problem) problem
Introducción a las ciencias de la computación
Antonio López Jaimes

UNIVERSIDAD AUTÓNOMA METROPOLITANA UNIDAD IZTAPALAPADefinición del problema
• El problema del paro consiste en determinar si una máquina de Turing cualquiera se detendrá ante cualquier entrada dada. • Es decir, si existe una máquina MTh capaz de determinar sicualquier otra máquina se va a detener o no. • Es conocido que el problema del alto es indecidible.

10-oct-05

2

Demostración de la indecibilidad
• Para demostrar que el problema del alto esindecidible tenemos que probar la siguiente afirmación:
– NO existe una máquina MTh que tomando como entrada cualquier máquina MT0, termine después de un tiempo finito y responda ‘SÍ’ cuando MT0termine y ‘NO’ cuando MT0 no termine.

10-oct-05

3

Funcionamiento de la máquina hipotética MTh
Si MTh existe ⇒ el problema es decidible

Cuando MT0 termina

SÍ

MT0

¿MT0 termina?

MThNO
Si MTh NO existe ⇒ el problema es indecidible
10-oct-05

Cuando MT0 no termina
4

Estrategia de la demostración
• Por contradicción demostraremos que no existe una máquina MTh queresuelva el problema del alto. • Hipótesis: – Supondremos que existe MTh.

• Al final llegaremos a una contradicción derivada de esta hipótesis.
10-oct-05 5

Estrategia de la demostración
•Construyamos una nueva máquina MTs que se comporte de la siguiente manera:
– La nueva máquina MTs tomará como entrada una máquina dada MT0. – MTs ejecutará la máquina MTh y le dará como entrada la máquinaMT0. Por hipótesis, MTh terminará en algún momento y responderá ‘SÍ’ o ‘NO’ (según MT0 termine o no). – Si MTh dice ‘SÍ’, entonces MTs entra en un ciclo infinito y no termina. – Si MTh dice ‘NO’,entonces MTs se detiene inmediatamente (la salida no importa).
10-oct-05 6

La nueva máquina MTs MTs
Si MT0 termina

MTs NO termina

MT0

SÍ

MTh
NO Si MT0 no termina MTs termina

Si MT0...