Máquina De Turing
Enviado por l_maya • 27 de Marzo de 2015 • 233 Palabras (1 Páginas) • 280 Visitas
La máquina de Turing fue inventada por Alan Turing en 1937. Es un modelo matemático abstracto que formaliza el concepto de algoritmo. También es un dispositivo que transforma un Input en un Output después de algunos pasos. Tiene un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene el Input.
La máquina de Turing o MT con una sola cinta, puede ser definida como una séptupla M= (Γ,Σ, •,Q,q0,f,F) donde :
1. Γ es el alfabeto de símbolos de la cinta
2. Σ ⊂ Γ es el alfabeto de símbolos de entrada
3. • ∈ Γ es el símbolo blanco que no pertenece a Σ
4. Q es un conjunto finito de estados
5. q0 ∈ Q es el estado inicial
6. F ⊆ Q es el conjunto de estados finales
7. f es una función de transición parcial
Tanto el Input como el Output constan de números en código binario. Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. Luego, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior. Ejecuta alguna operación con ese bit y lo cambia dependiendo de su estado interno. Después se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final, se detiene dejando el resultado al lado izquierdo. Una instrucción típica podría ser: 01 11011i.
...