Unidad 6: interpretaciones de ALA y MT

Question 1

Halting problem o problema de parada

Un ALA, cuando encuentra un HP?

Answer 1

Si bien no puede detenerse porque su cinta y su alfabeto son finitos, si en algún momentorepite una configuración puede detectar que ha entrado en un bucle

Question 2

Halting problem o problema de parada

Una MT, cuando encuentra un HP?

Answer 2

Si bién la MT no puede detenerse, al ser la cinta infinita, no puede siempre saberse si entro en un bucle. No existe un algoritmo o MT que decida in otra MT se detiene.