Maquinas de Turing

1. ¿Que es?

1.1. Computacionalmente

1.1.1. Automata que se mueve sobre una secuencia lineal de datos

1.1.1.1. En cada instante la maquina puede leer un solo dato de la secuencia

1.1.1.1.1. Realiza acciones de acuerdo a una tabla

1.2. Fisicamente

1.2.1. Cinta divida en casillas con un simbolo en cada una de estas

1.2.1.1. Donde actua un dispositivo que cambia de estados

1.2.1.1.1. Lee simbolos

1.3. Componentes

1.3.1. Control finito

1.3.2. Cabeza Lectora

1.3.2.1. Lectura y escritura

1.3.3. Cinta

1.3.3.1. Longitud infinita a la derecha

1.3.3.2. Contiene caracteres y palabras de entrada

2. Representación

2.1. Grafica

2.1.1. .

2.1.2. .

2.2. Fisica

2.2.1. .

2.2.2. .

2.2.3. .

2.3. Grafos

2.3.1. .

2.3.2. .

3. 7-tupla de Turing

3.1. Q

3.1.1. Conjunto finito de estados

3.2. Σ

3.2.1. Alfabeto de maquina o entrada

3.3. Γ

3.3.1. Conjunto finito de simbolos de la cinta

3.4. s

3.4.1. Estado inicial

3.5. b

3.5.1. Simbolo denominado blanco

3.5.1.1. Se puede repetir infinitas veces

3.6. F

3.6.1. Estado final o de aceptación

3.7. δ

3.7.1. Función de transición

4. Clasificación

4.1. Multicinta

4.2. No determinista

4.3. Multidimensional

4.4. Con multiples cabezales

4.5. Offline

4.6. Con movimiento stay

4.7. Con cinta infinita en ambos lados

4.8. Con cinta multipista

4.9. Multidimensionales

4.10. Universal

4.11. Cuantica

5. Alan Turing

5.1. Paddington, Londres (1912-1953)

5.1.1. Matemático

5.1.2. Lógico

5.1.3. Cientifico de la computación

5.1.4. Filosofo

5.1.5. Criptógrafo

5.2. Articulo Numeros Calculables, 1937,

5.2.1. Considerado Origen de la informatica teoirca

5.3. Padres de la ciencia de la Computación

5.4. Influencia en la formalización

5.4.1. Computación

5.4.2. Algoritmo

6. Funcionamiento

6.1. Cabezal lee el contenido

6.1.1. Borra el contenido anterior

6.1.2. Escribe un nuevo valor

6.2. Avanzar cabezal

6.2.1. Hacia la derecha

6.2.2. Hacia la izquierda

6.3. Se determina Computo

6.3.1. Apartir de la tabla de estados

6.3.1.1. De la forma

6.3.1.1.1. (estado, valor) (nuevo estado, nuevo valor, dirección)

6.3.1.2. Toma parametros

6.3.1.2.1. Estado actual de la maquina

6.3.1.2.2. Caracter leido de la cinta

7. Función

7.1. Reconocer Lenguajes

7.1.1. Regulares

7.1.2. Infinitivamente Recursivos

7.1.2.1. Por lo tanto es superior

7.1.2.1.1. Automatas con pilas

7.1.2.1.2. Automata Infinito