1. En 1931, kurt Gödel publicó un artículo sobre las proposiciones formalmente indecidibles en Principia Mathematica y Sistemas Relacionados en donde se demuestra que toda formula axiomática contiene proporciones indecidibles; siempre habrá en ella afirmaciones verdaderas que no se pueden demostrar.
2. Origen
3. En 1937, Alan Turing publicó otro articulo famoso sobre los Números Calculables, que desarrollo en base al tema de Gödel y que puede considerarse el origen oficial de la informática teórica. En este artículo introdujo la máquina de Turing, una entidad matemática abstracta que formalizó el concepto de algoritmo, resultando precursor de las computadoras digitales.
4. Una máquina de Turing clásica de una cinta es una tupla de la forma T = (Σ, Q, q0, qf , δ),donde Σ = ∅ es un alfabeto finito que contiene un símbolo distinguido Π, llamado símbolo blanco Q = ∅ es el conjunto finito de estados, el cual incluye q0 y qf q0 es el estado inicial qf es el estado final de aceptación δ es una función de transición cuyo dominio es un subconjunto de Q × Σ y cuyo contradominio es Q × Σ × M. De tal forma que si δ está definida para el par (ℓ, s) ∈ Q × Σ y δ(ℓ, s) = (ℓ ´ , s´ , m) entonces • ℓ es el estado actual • s el símbolo que está leyendo la cabeza • ℓ ´ el estado al cual nos llevara la transición • s´ el símbolo que se escribirá • m el movimiento que realizara la cabeza. En nuestra definición consideramos que el alfabeto usado es {0, 1, Π } y que M = {←,→, −} es el conjunto de movimientos realizados por la cabeza lectora ya sea a la izquierda, a la derecha o permanecer en la misma posición. En adelante denotamos con MT al conjunto de máquinas de Turing. El proceso de ejecución de una máquina de Turing se formaliza mediante la relación de transición entre configuraciones instantáneas de acuerdo a la siguiente
5. Funcionamiento.
6. Definicion.
7. La 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, temporalmente se lee el símbolo sobre la casilla que está situado, en funciones de este símbolo que se lee y del estado en el que se encuentra se realizan las siguientes acciones.
8. Pasa a un nuevo estado
9. Imprime un símbolo en el lugar que acaba de leer
10. Se desplaza a la izquierda o derecha o bien la máquina se detiene.
