1. Alan Turing
1.1. 23 de junio de 1912 - 7 de junio de 1954
1.2. Uno de los padres de la ciencia de la informática y pionero de la informática moderna
1.3. Fue criptógrafo, informático teórico, logico y matemático
1.4. Reconocido por El problema de la parada, Maquina de Turing, Descifrar Enigmas y el Test de Turing
1.4.1. La Prueba o Test de Turing al procedimiento desarrollado por Alan Turing para identificar la existencia de inteligencia en una máquina
2. ¿Que es?
2.1. Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos.
2.2. Un autómata capaz de reconocer lenguajes formales
2.2.1. Los lenguajes recursivamente enumerables (según la jerarquía de Chomsky)
2.3. Una máquina de Turing con una sola cinta puede ser definida como una 5-tupla M={Q,Σ,S,F,δ}
2.3.1. Q es un conjunto finito de estados
2.3.2. Σ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
2.3.3. S ∈ Q es el estado inicial.
2.3.4. F ⊆ Q es el conjunto de estados finales de aceptación.
2.3.5. δ es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.
2.4. Representación Grafica
2.4.1. Diagrama de transición
3. Componentes
3.1. Tabla de instrucciones
3.1.1. Normalmente son 5 tuplas
3.1.1.1. Teniendo un estado y el símbolo
3.1.1.1.1. Le indica a la MT hacer la siguiente en secuencia
3.1.2. A veces son 4 tuplas
3.2. Cabezal
3.2.1. Lee el contenido de una celda o escribir en ella
3.2.2. Mueve la cinta derecha/izquierda
3.2.2.1. Una a la vez
3.3. Cinta
3.3.1. Se divide en celdas, una al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito
3.4. Registro de estado
3.4.1. Almacena el estado de la máquina de Turing, uno de los estados finitos
3.4.1.1. Inicia con un estado especial
4. Clasificación
4.1. Máquina de Turing con Directiva de Permanecer
4.2. Máquina de Turing Multipista
4.3. Máquina de Turing de Cinta infinita en una Dirección
4.4. Máquina de Turing en Dos direcciones
4.5. Máquina de Turing Multicinta
4.6. Máquina de Turing muldimensional
4.7. Máquina de Turing No determinista
5. Una Máquina de Turing puede considerarse como una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que, en cada instante, lee un símbolo de la casilla sobre la que está situado.
6. ¿Como funciona?
6.1. La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido
6.1.1. Borra el contenido anterior y escribe un nuevo valor.