Máquina de Turing

Plan your projects and define important tasks and actions

Get Started. It's Free
or sign up with your email address
Rocket clouds
Máquina de Turing by Mind Map: Máquina de Turing

1. ¿Que es?

1.1. Un dispositivo

1.1.1. Que manipula símbolos sobre una tira de cinta

1.1.1.1. Siguiendo con una tabla de reglas

1.1.2. Hipotético que representa una máquina de computación

1.1.2.1. capaz de

1.1.2.1.1. Implementar todo problema matemático representable en un algoritmo

1.1.3. Cuya función es

1.1.3.1. Transformar una entrada en una salida

1.1.3.1.1. Mediante unos pasos

1.2. Es el elemento central de estudio de la teoría de la computación

1.2.1. puede utilizarse para

1.2.1.1. Explicar las funciones de una CPU

1.3. Un autómata capaz de reconocer lenguajes formales

1.3.1. como los son

1.3.1.1. Los lenguajes recursivamente enumerables (según la jerarquía de Chomsky)

1.3.1.1.1. es superior al

2. Componentes de la MT

2.1. Una tabla finita de instrucciones

2.1.1. Normalmente son 5 tuplas

2.1.1.1. A veces son 4 tuplas

2.1.1.2. Teniendo un estado y el símbolo

2.1.1.2.1. Le indica a la MT hacer la siguiente en secuencia

2.2. El cabezal

2.2.1. Lee y escribe símbolos en la cinta

2.2.2. Mueve la cinta derecha/izquierda

2.2.2.1. Una celda a la vez

2.3. Una cinta

2.3.1. Dividida en celdas llenas de un bit cada una

2.3.1.1. Un poco parecido a un vector de lleno de números binarios

2.3.1.2. Por la que el cabezal

2.3.1.2.1. Lee el contenido

2.3.1.2.2. Borra el contenido

2.3.1.2.3. Escribe un nuevo valor

2.4. Registro de estado

2.4.1. Almacena el estado de la maquina

2.4.2. Inicia por un estado que es especial

3. Inventada por Alan Turing

3.1. Uno de los padres de la ciencia de la informática

3.2. Pionero de la informática moderna

3.3. Nacimiento

3.3.1. 07/06/1954 Reino Unido

3.4. Fallecimiento

3.4.1. 07/06/1954 Reino Unido

3.5. Fue

3.5.1. Criptógrafo

3.5.2. Informático teórico

3.5.3. Lógico

3.5.4. Matemático

3.6. Mejor conocido por

3.6.1. El Problema de la parada

3.6.2. El Maquina de Turing

3.6.3. Descifrar Enigma

3.6.4. El Test de Turing

4. Clasificación

4.1. Máquina de Turing Multicinta

4.1.1. tiene

4.1.1.1. n cintas

4.1.1.1.1. Infinitas a ambos lados

4.1.1.2. n cabezales de L/E

4.1.2. Única entrada de información en la primera cinta

4.1.3. Pasos de asociación a cada transición

4.1.3.1. Transición de estado

4.1.3.2. Cada cabezal

4.1.3.2.1. Escribe un símbolo en la celda en que este ubicado

4.1.3.2.2. Es independiente con movimiento

4.2. Máquina de Turing No Determinista

4.2.1. Tiene una cinta limitada a la izquierda

4.2.2. se caracteriza por que

4.2.2.1. Puede tener diferentes transiciones

4.2.2.1.1. desde

4.3. Máquina de Turing Multidimensional

4.3.1. La cinta es un array

4.3.1.1. n dimensiones de celdas

4.3.2. Teniendo encenta el estado y el símbolo que se lea

4.3.2.1. Hay una movimiento diferente a la MT unidimensinal

4.3.2.1.1. La transición puede ser en cualquier dirección existente

4.3.3. La entrada esta sobre un eje

4.3.3.1. El cabezal inicia a la izquierda de la entrada

4.4. Máquina de Turing con Multiples Cabezales

4.4.1. tiene

4.4.1.1. n cabezales de L/E y una sola cinta

4.4.1.1.1. Los cabezales operan de forma independiente

4.4.1.1.2. Puede moverse

4.5. Máquina de Turing Offline

4.5.1. tiene

4.5.1.1. una cinta especial de solo lectura

4.5.2. El cabezal solo se mueve a la derecha

4.5.3. No se mueve de la zona delimitada

4.5.3.1. por un par de símbolos especiales