Diferencia entre revisiones de «La tesis de Church-Turing/Introducción»

* '''Tercer nivel:''' se consideran el resto de problemas, como por ejemplo, los que requieren un tiempo linealmente proporcional a sus tamaños.

 

 

Una de las preguntas que Hilbert planteó fue si las matemáticas eran completas, es decir: si cada proposición podía ser demostrada o refutada dentro de las matemáticas.

 

* Teorema de la incompletitud de Gödel

 

Otro de los resultados más importantes de esta teoría es la existencia de las máquinas universales de Turing, esto es, máquinas que simulan ser una máquina de Turing recibiendo en su entrada (en la cinta) todo lo relativo a la máquina a imitar, pero que tienen un conjunto finito que no debe ser modificado.