Cosas que las computadoras no pueden hacer

En 1982, Richard Feynman predijo una clase de problemas que no podrían ser tratados jamás por un ordenador, tras encontrar una limitación en la capacidad de estas. Feynman propuso que los ordenadores no podían ser aplicados en la simulación de fenómenos de naturaleza cuántica, es decir, los que se observan en los átomos y para los que la física clásica es insuficiente. Con esto quería decir que un fenómeno cuántico es no computable, y por tanto, no podía ser tratado con un ordenador convencional. Mientras que los ordenadores convencionales representan los datos como secuencias de ceros y unos, es decir bits, los ordenadores cuánticos lo hacen con qbits, estos pueden tener un valor igual a 0, 1 o cualquier otro estado superpuesto, es decir puede estar simultáneamente apagado o encendido, entre 0 y 1. Si bien se están haciendo avances en desarrollar computadoras cuánticas estamos muy lejos de ver una de estas funcionando. Kurt Gödel demostró en el famoso "teorema de incompletitud" que en los sistemas lógico-formales existen proposiciones verdaderas que aunque puedan expresarse en dicho sistema no pueden demostrarse en mismo. Además, considerado cualquier formalismo matemático, siempre hay problemas matemáticos que lo trascienden y que nos conduce a un sistema más potente donde se pueden resolver, por ende las computadoras no pueden resolver todos los problemas. También existen problemas conocidos como problemas no computables que no se pueden resolver mediante un algoritmo, un ejemplo de este tipo de problemas puede ser el de crear un programa que diga si otro programa termina o no. Supongamos que podemos hacer un programa que diga si otro programa termina o no. Luego, existe un programa H tal que, dado un programa Prog y una entrada x0, retorna uno si y sólo si Prog(x0) termina.Construyamos ahora un nuevo programa Q de manera tal que Q(Prog) termine si y sólo si H(Prog,Prog) = 0, y no termine si y sólo si H(Prog,Prog) = 1. Ahora bien, Q(Q) no puede terminar, pues eso implica que H(Q,Q) = 0 (Q no termina para la entrada Q). Q(Q) tampoco puede no terminar, pues eso implicaría que H(Q,Q) = 1(Q termina para entrada Q). Luego, el problema es indecidible. Vale aclarar que indecibilidad para Gödel significa que una fórmula A ni su negación son demostrables en el sistema y para Turing significa que no podemos dar una solución algorítmica.