Otros

Máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo estáconformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco(normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichosestados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres(la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto deentrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha(solo unacelda a la vez), repitiendo esto según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

Definición BasicaUna máquina de Turing con una sola cinta puede ser definida como una septupla 7tupla[pic], donde
• [pic]es un conjunto finito de estados.
• [pic]es un conjunto finito de símbolosdistinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
• [pic]es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. ([pic])
• [pic]es elestado inicial.
• [pic]es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
• [pic]es el conjunto de estados finales de aceptación.• [pic]es una función parcial denominada función de transición, donde [pic]es un movimiento a la izquierda y [pic]es el movimiento a la derecha.
Existen en la literatura un abundantenúmero de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo [pic]como símbolo de "no movimiento" en un paso de cómputo.