La Máquina De Turing

La máquina de turing Diseñadores: Analía Caresano Carina Grignoli Cecilia Garrido Coordinadora: Margarita Díaz

La Máquina de Turing 

Modelo matemático abstracto.

 

Auge de la matemática en el siglo XX.

 

Creador Alan Turing.

 

Año 1936.

 

Autómata.

  



Determina si una secuencia es válida o no.

Máquina de computación lógica 



Surge a partir del estudios de los números computables.

 

Ideada como definición matemática y precisa de lo que es un algoritmo.

 

Descripción 

Cinta infinita dividida en casillas.  Todas

 

las celdas tienen el símbolo 0 (vacío).

Cabezal lector/escritor

Funcionamiento 

Lee la cinta hacia derecha o izquierda.

 

Lee el contenido, borra y escribe el nuevo valor.

  

   

Reconoce el lenguaje formal.

Elementos de la Máquina 

Estados

Conjunto finito  Símbolos de la cinta. 



   

   

Tabla de acción (instrucciones)

Tabla de acción 

Ejecución de instrucciones 1.

2.Estado 3.Valor (Carácter leido) 4.Nuevo estado 5.Nuevo Valor (Carácter a escribir) 6.Movimiento 

Ejemplo del funcionamiento: 1)

1)El estado es A, lee un cero; cambia al

A

v ... 0 0 0 0 0 1 0 0 0 0 ...

estado B, escribe un 1 y se mueve a la derecha 2)El estado es B, lee un cero; cambia al

2)

B v … 0 0 0 1 0 1 0 0 0 0 ...





3)

 A v ... 0 0 0 1 1 1 0 0 0 0 ...

4)

B

estado A, escribe un 1 y se mueve a la derecha

Operaciones 

Suma.

 

Multiplica.

 

Copia números.

  

 

Etc.

Ejemplo: 

Sumar 3 y 5

 

0000111011111000

 

0000011011111000

 

0000011111111000

¿Qué problemas puede resolver? 

cualquier problema bien definido al ejecutar un algoritmo.

 

Excepciones: constante de Chaitin  Algoritmo

  

 

definido, pero no computable.

¿Qué problemas NO puede resolver? 

EL ENTSCHEIDUNGSPROBLEM: (problema de decisión en alemán) Dada una frase decidir si es teorema.





EL PROBLEMA DE LA PARADA: Dado un programa y su entrada, decidir si ese programa terminará o si correrá indefinidamente.

Consecuencia en la actualidad 

Definición moderna de lo que es "Computable" se basa en este concepto.

 

Base de la teoría de computación.

 

Posibilita la idea de sistema operativo.

 

Instrumentos automáticos para cálculos.

 



Demostró que la mayoría de los números no son computables.

formalismos equivalentes: 

con varias cintas





con número limitado de estados y símbolos para la cinta.

 

con solo dos estados





probabilísticas





no determinísticas



•

Computador cuántico

Anexo: 

Premio U$25.000 a quien demostró que la 2.3 era una Máquina Universal de Turing.

 

Máquina mas simple.

  

Joven inglés de 20 años.

Fuentes 

www.wikipedia.com

 

www.biblioweb.com

 

www.rastersoft.com

     

www.wapedia.com