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

 

* '''Primer nivel:''' divide los problemas en tres clases:

** ''Primer tipo:'' Problemas imposibles

** ''Segundo tipo:'' Problemas que se pueden ejecutar si disponemos de recursos ilimitados.

** ''Tercer tipo:'' Problemas que se pueden ejecutar incluso si tenemos recursos limitados.

* '''Segundo nivel:''' se consideran los problemas en función del tiempo que tardan en ejecutarse. Este tipo de enunciados se conocen con el nombre de problemas indecidibles, los impracticables y los solucionables.

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