Ensayo: tesis de church-turing y la no computabilidad

Ensayo:” Tesis de Church-Turing y la No Computabilidad”

Al hablar sobre la tesis de Church-Turing y no Computabilidad nos referimos a la parte de la computación llamada Teoría de laComputabilidad, que estudia los problemas de decisión que pueden ser resueltos con un algoritmo (o su equivalente, una maquina de Turing). Esta teoría inicio con los trabajos de Hilbert en 1928, cuya intensiónera crear un modelo matemático formal, completo y consistente, en el que a través de un algoritmo, se pudiese determinar la veracidad o falsedad de cualquier proposición formal, al cual se le llamo“problema de decisión”. Si Hilbert hubiera cumplido su objetivo significaría que cualquier problema bien definido se resolvería simplemente al ejecutar dicho algoritmo, desgraciadamente, pocos años despuésvarios investigadores (Kurt Gödel, Turing y Church principalmente) demostraron que era imposible, pues existen problemas indecidibles.
En 1930, Gödel publica su “Teorema de la Incompletitud” con elcual demuestra que es imposible resolver el sistema propuesto por Hilbert, el cual expresa que: “todo sistema de primer orden consistente que contenga los teoremas de la aritmética, cuyo conjunto deaxiomas sea recursivo no es completo”. Su demostración se basa en la construcción de una fórmula que es satisfactoria pero que no puede ser probada por el sistema, y como consecuencia, no es posibleencontrar el sistema formal deseada por Hilbert. Tiempo después, Turing con su máquina (llamada maquina de Turing) y Church con el cálculo Lambda (forma de definir funciones), reafirmaron la teoríade Gödel ya que Church demostró que tanto las funciones-definibles como las funciones recursivas de Herbrand-Gödel son equivalentes. Aunque, cada uno hizo su investigación de forma independiente sellego a la conclusión de que ambas tesis eran equivalentes (Tesis de Church-Turing), pues tienen el mismo poder para resolver problemas y se puede formular como sigue, “Una función de enteros...