Máquina de Turing

Conceptos de informática

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

De autómatas a máquinas de Turing

  • Autómatas finitos: Memoria limitada; manejan lenguajes regulares.
  • Autómatas con pila: Memoria con pila; manejan lenguajes libres de contexto.
  • Máquina de Turing: Memoria ilimitada (cinta infinita); resuelve todos los problemas computables.

Una ilustración de Alan Turing

Conceptos de informática

¿Qué es una Máquina de Turing?

Un diagrama que muestra cómo funciona una Máquina de Turing

Máquina de Turing

  • Máquina abstracta con cinta infinita.
  • Lee y escribe símbolos.
  • Puede simular cualquier algoritmo.
Conceptos de informática

Máquinas de Turing por analogía

Una cocina con una persona cocinando una receta como analogía de una Máquina de Turing

Cocina y cocinero como Máquina de Turing

  • La encimera es la cinta.
  • Las secciones de la encimera son las celdas.
  • Los ingredientes son los símbolos.
  • El cocinero es el cabezal que lee y escribe.
  • El recetario es el programa que guía todo el proceso.
Conceptos de informática

¿Por qué es importante una Máquina de Turing?

Máquina de Turing y computabilidad

  • Puede simular cualquier algoritmo
  • Define el límite de lo que un ordenador puede resolver
  • Introduce los problemas indecidibles (p. ej., el problema de la parada)
  • Sienta las bases de la teoría de la computación moderna
Conceptos de informática

El problema de la parada

  • La pregunta: ¿Podemos predecir si un programa se detendrá o correrá para siempre con una entrada dada?
  • El hallazgo de Turing: No existe un algoritmo universal que lo resuelva para todos los programas.
  • Resultado: El problema de la parada es indecidible; algunos problemas no tienen solución algorítmica.
  • Implicaciones: Estos límites afectan a la criptografía y la IA

Un diagrama que muestra qué es el problema de la parada

Conceptos de informática

¡Vamos a practicar!

Conceptos de informática

Preparing Video For Download...