Introducción
Para David Hilbert, un notable matemático, el hecho de que hubiera problemas que no contaran con una solución exacta, supuso una gran insatisfacción, porque él mismo pensaba en lo siguiente:
“Todo problema matemático definido debe ser necesariamente susceptible de un planteamiento exacto, ya sea en forma de una respuesta real a la pregunta planteada o debido a la constatación de la imposibilidad de resolverlo, a lo que se debería la falla necesaria de todos los intentos... una de las cosas que nos atrae más cuando nos dedicamos a un problema matemático es precisamente a que dentro de nosotros siempre escuchamos la llamada: e aquí el problema, busca la solución; puedes encontrarla por pensamiento puro, ya que en matemáticas no existe cosa alguna que no pueda conocerse”.
El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas menos "generales" que han resultado ser no computables.
Problemas No Computables
La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal.Como ejemplos de estos problemas podemos citar:
Básicamente, Turing definió las bases de las computadoras modernas y planteo un problema sobre ellas, llegando a la conclusión de que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (Halting problem); el problema de saber si un problema se cuelga cuando corre en la computadora. Turing demostró que el problema de la detención es indicidible, es decir, demostró que había problemas que una maquina no podía resolver.
2- El décimo problema de Hilbert es uno de los veintitrés que David Hilbert propuso al término del siglo XIX. Su enunciado original es:
"Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes numéricos racionales enteros:
Idear un proceso de acuerdo con el cual pueda determinarse, en un número finito de operaciones, si la ecuación es resoluble en números racionales enteros."
David Hilbert (1862-1943)
En términos más modernos, Hilbert solicitaba a sus colegas del futuro un algoritmo capaz de admitir como entrada (input) una ecuación diofántica cualquiera, y de devolver SÍ como resultado (output) si la ecuación procesada tenía soluciones en los enteros o NO si la ecuación procesada carecía de soluciones en los enteros.El problema no se resolvió hasta 70 años después, y en sentido negativo.
En 1970 Yuri Matiyasévich culminó más de veinte años de trabajo de varios matemáticos, entre ellos Martin Davis, Julia Robinson y Hilary Putnam, con la demostración de imposibilidad del décimo problema: ningún algoritmo es capaz de determinar la resolubilidad de cualquier ecuación diofántica. El planteamiento, desarrollo y demostración del problema tienen gran interés en matemática moderna, porque en ellos participan conceptos de teoría de números y de lógica matemática, y se abren nuevos campos de investigación en ambas disciplinas.
En 1997 fue seleccionando para la Academia rusa de las Ciencias. Actualmente dirige el Laboratorio de Lógica Matemática en LOMI, el cual se conoce como el Departamento de Petersburgo del Instituto de Matemáticas de Steklov de la Academia Rusa de las Ciencias, o el PDMI RAS.
3- Decibilidad de las teorías lógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una de las distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible.
Por otro lado, son muchos los problemas interesantes que se han demostrado computables. Todas las funciones construidas por recursividad primitiva o minimalización a partir de funciones calculables resultan ser calculables como consecuencia de los trabajos de Church y Turing. Pero además, otras funciones más complejamente definidas también son computables, siendo el resultado más significativo en relación con esta cuestión el dado por el siguiente teorema:
Primer teorema de Recursión.
Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos de una parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es una extension de esa función.
Este teorema recibe su nombre porque podemos definir una función mediante una ecuación recursiva más general que la permitida por la recursividad primitiva, a saber donde es un operador recursivo. El primer teorema de recursión nos dice que esta definición es posible; hay una función recursiva que satisface esta ecuación. Como en matemáticas se requiere que la definición sea unívoca, se dice que dicha ecuación define el menor punto fijo del operador .
A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva, esta mísma técnica es muy empleada en el campo de la complejidad algorítmica. Para asegurarse de que un problema está en una clase de complejidad, basta reducir el problema a otro de dicha clase sin más que asegurarse que la reducción se realiza en la correspondiente clase de complejidad.
4- Codigo Muerto.Cuando se utiliza el término de código muerto algunos autores hacen referencia a:
- código redundante.
- código inaccesible.
- código que no se usa.
Este término es asociado únicamente a aquel código que no es accesible desde ninguno de los caminos de ejecución posibles partiendo de los diferentes puntos de entrada naturales del Sistema de Información.
A pesar de que en un primer y rápido análisis podríamos concluir que el código muerto no entraña un verdadero peligro para un Proyecto de Desarrollo o de Mantenimiento de un Sistema de Información (a fin de cuentas, es un código que no se ejecutará), la verdad es otra: el código muerto, además de dejar en evidencia cierta dejadez por parte del Equipo del Proyecto, arrastra tras de sí graves problemas de mantenibilidad.
¿Es posible para un computador averiguar si existe código muerto en un programa?
Imagina una situación (no muy alejada de la realidad de muchos proyectos) en la que a ti, como desarrollador, te encargan modificar un código que tú no has desarrollado. Tras un examen más o menos exhaustivo, das con una porción de código que parece que no es ejecutada nunca. Te sientes tentado a eliminarla, pero en realidad no te atreves porque no estás seguro al 100 por ciento de que lo que tienes delante sea verdaderamente código muerto. Si finalmente optas por tentar la suerte, ni tan siquiera una batería de pruebas podrá asegurarte que no has añadida errores al eliminar el código (no hay que olvidar que, como ya avanzaba Dijkstra por el año 1969, las pruebas del software muestran la presencia de errores, no su ausencia).
No hay comentarios:
Publicar un comentario