Máquina de Turing

Máquina de Turing es un término de la informática. Una máquina de Turing es un sistema de reglas, estados y transiciones más que una máquina real. Fue descrita por primera vez en 1936 por el matemático e informático inglés Alan Turing. Una máquina de Turing tiene dos objetivos: decidir lenguajes formales y resolver funciones matemáticas. Las máquinas de Turing son uno de los modelos formales más importantes en el estudio de la informática.

Modelo de una máquina de TuringZoom
Modelo de una máquina de Turing

Fundamentos comunes

Una máquina de Turing consta de los siguientes componentes (simplificados):

  • Un conjunto limitado de estados (con un estado marcado como estado de inicio; mientras se ejecuta, una máquina de Turing siempre tiene un estado actual)
  • Una cinta infinita con celdas de almacenamiento y un dispositivo de lectura/escritura que puede moverse en la cinta
  • Una definición de la llamada función de transición

Además, hay que definir un alfabeto de trabajo (conjunto de caracteres).

Cuando una máquina de Turing se pone en marcha, una palabra (del alfabeto de trabajo) debe estar presente en la cinta infinita de la máquina. El dispositivo de lectura/escritura en el primer carácter lee ahora el primer carácter y, dependiendo del estado actual de la máquina de Turing, el dispositivo de lectura/escritura sobrescribe el carácter con uno nuevo o mueve una celda a la izquierda o a la derecha. Además, se puede cambiar el estado actual de la máquina.

Máquinas de Turing que deciden los idiomas

Para la teoría de la decidibilidad se dice que una máquina de Turing decide un lenguaje si siempre es capaz de determinar si una palabra dada está contenida en un determinado lenguaje o no. Por lo tanto, la máquina suele tener dos estados especiales marcados como Aceptar y Rechazar. Al cabo de un tiempo se alcanzará uno de los dos estados (dependiendo de la palabra de entrada) y la máquina se detendrá. Si sólo se alcanza uno de los dos estados, se dice que la máquina de Turing semidecide un lenguaje.

Máquinas de Turing que computan funciones

Si una máquina de Turing se utiliza para el cálculo de funciones, sólo tiene un estado final. Cuando la máquina llega a ese estado se detiene y el resultado de la función (dependiendo de la entrada) se puede encontrar en la cinta.

Impacto de las máquinas de Turing

Las máquinas de Turing no se inventaron para ser construidas en la realidad, pero son muy importantes para la informática teórica, ya que son uno de los modelos más sencillos de ordenadores. La tesis de Church-Turing afirma que todos los ordenadores son tan potentes como las máquinas de Turing. Esto puede utilizarse para demostrar si un problema puede ser resuelto por un ordenador o no.

Variaciones

  • Una máquina de Turing puede consistir en múltiples cintas infinitas (y múltiples dispositivos de lectura/escritura). Sin embargo, se ha demostrado que estas máquinas sólo son tan potentes como las de una sola cinta. Las máquinas de varias cintas son útiles cuando se trata de problemas más complejos.
  • Si una máquina de Turing tiene una función de transición no determinista, puede haber múltiples transiciones de un estado a muchos otros al leer un carácter. De nuevo, esto no aumenta la potencia de las máquinas de Turing. Sin embargo, las máquinas de Turing no deterministas (como se denominan entonces) pueden disminuir el tiempo de cálculo en gran medida. Esta cuestión se trata en el debate P versus NP y aún no está resuelta. Sin embargo, la mayoría de los científicos asumen que las máquinas no deterministas pueden trabajar mucho más rápido en ciertos problemas.
  • Una máquina de Turing universal es una variación que puede simular una máquina de Turing con una entrada.

AlegsaOnline.com - 2020 / 2023 - License CC3