- Alan Turing, establece la relación entre la lógica y la computación electrónica, plantea la famosa Máquina de Turing, la cual es la base de la Teoría de la Computación actual.
- Turing es, considerado El padre de la Teoría de la Computación.
- El punto de partida de la teoría de la computación fueron las cuestiones fundamentales que David Hilbert (1845-1918) formuló en 1928, el "Entscheidungsproblem".
- Las primeras noticias en contra surgen en 1931 con Kurt Gödel (1906-1978) y su Teorema de Incompletitud (1931): "Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo".
- Los resultados de Gödel prueban que no sólo no existe un algoritmo que pueda demostrar todos los teoremas en matemáticas sino que además no todos los resultados son demostrables.
LA MÁQUINA DE TURING
- La máquina de Turing es una caja negra (Tan simple como una máquina de escribir y tan compleja como un ser humano) Capaz no sólo de leer y escribir un alfabeto de símbolos finito a partir de una cantidad finita pero muy grande de cinta de papel, sino de modificar su propia configuración o "Estado mental".
- La máquina de Turing se convirtió en un instrumento ideal para probar si un procedimiento es efectivamente computable o no.
- Es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos.
FUNCIONAMIENTO
- Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de una cinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1.
- Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (Lo cambia o no, 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 para, dejando el resultado al lado izquierdo por ejemplo.
- Una instrucción típica podría ser: 01->11011i
No hay comentarios:
Publicar un comentario