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

Contenido eliminado Contenido añadido
Sin resumen de edición
Línea 1:
== Texto de titular ==
En primer lugar sevamos introduciráa brevementeintroducir el concepto de teoría de la computabilidad, lopara queayudarnos nosa permitirácomprender situarnos en el tema que vamos aeste tratarartículo.
 
 
Línea 6 ⟶ 7:
== Nociones Básicas acerca de la Teoría de la Computabilidad ==
 
La Teoría de la Computabilidad está compuesta por unalos serie de líneas directrices en las que podemos distinguir diferentessiguientes niveles:
 
* '''Primer nivel:''' divide los problemas en tres clases:
** ''Primer tipo:'' Problemas imposibles, no tienen solución.
** ''Segundo tipo:'' Problemas queejecutables se pueden ejecutarsolo si disponemos de recursos ilimitados.
** ''Tercer tipo:'' Problemas que se pueden ejecutarejecutarse inclusosin sinecesidad tenemosde recursos limitadosilimitados.
* '''Segundo nivel:''' se consideran los problemasclasifican en función del tiempo que tardan en ejecutarse. Este tipo de enunciados seSe conocen con el nombre de problemas indecidibles, los impracticables y loso solucionables.
* '''Tercer nivel:''' secomprende consideran el resto deaquellos problemas, comoque por ejemplo, los que requierenrequiere un tiempo linealmente proporcional a sussu tamañostamaño.
 
== La incompletitud ==