Diferencia entre revisiones de «La tesis de Church-Turing/Introducción»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 7:
* '''Primer nivel:''' divide los problemas en tres clases:
* '''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.
== Conclusiones Obtenidas ==
Tras varios intentos, Alan Turing consiguió
Si nos apoyamos en la noción intuitiva de algoritmo, nunca seríamos capaces de probar que algún problema no posee una solución de carácter algorítmica. Por ello, primero es necesario estudiar todas las clases de algoritmos posibles. Este fue el camino escogido por Turing para refutar el problema decisorio.
Línea 26 ⟶ 25:
La teoría de la computabilidad es conocida, también, como la teoría de las funciones recursivas. Esta disciplina contempla la existencia de procedimientos puramente mecánicos para resolver diferentes problemas.
Aunque esta teoría pertenece, principalmente, al campo de las matemáticas puras es especialmente importante para aquellos que no son matemáticos puesto que se encuentra muy relacionada tanto con determinadas cuestiones filosóficas como con la teoría de los computadores digitales.
Algunos de los resultados que se encuentran englobados dentro de la teoría de la computabilidad, pero que se encuentran relacionados con la filosofía, son:
▲• La existencia de problemas absolutamente insolubles
▲• 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. Esta afirmación hace que se refuerce la idea (sobre todo, de aquellas personas que trabajan con computadores digitales) de que es posible crear un ordenador de propósito general que, además, se podría programar para ser utilizado en cualquier ordenador digital determinístico que nos podamos imaginar.
| |||