Computabilidad:
Decir que un problema es computable o no computables se refiere a que si un problema tiene o o no una solución algorítmica.
Más allá de las capacidades de las computadoras actuales y las sorprendentes aplicaciones creadas, existen problemas para los cuales no existe una solución algorítmica aun. Pero para decir que un problema no es computable se requiere demostrar que nunca se podrá encontrar
ningún algoritmo para resolver el problema planteado.
Algunos ejemplos de este tipo de problemas son:
• Décimo problema de Hilbert: Resolver una ecuaci´on diof´antica con más de una incógnita.
Esto significa encontrar soluciones enteras de una ecuación de la forma
P(x1, x2, . . .) = 0, donde P es un polinomio con coeficientes enteros.
• Problema de la parada.
Determinar si un algoritmo a finaliza o no cuando opera sobre una entrada
de datos d.
Números pedrisco:
Como ejemplo de la dificultad de examinar un algoritmo y decidir si concluirá tarde o temprano, consideremos la siguiente función t: IN → IN:
Partiendo de un número natural cualquiera, le aplicamos t cuantas veces sea
necesario, hasta llegar a 1. Esta sencilla sucesión genera números que saltan un número de veces impredecible de manera que cabe preguntarse si todo natural n alcanza el 1 tras una cantidad
finita de aplicaciones de t, o por el contrario existe alguno que genera términos que saltan indefinidamente.
Se ha comprobado, por medio de computadoras, que la sucesión llega a 1 para números naturales muy grandes. Sin embargo, aun no se
ha podido demostrar para todos los n.
A continuación, compartimos el código en C de la aplicación de la función de Pedrisco. Este programa solicitará el ingreso de un numero natural y luego le aplicará la función un número indeterminado de veces hasta llegar a 1. Finalmente, Mostrará por pantalla la cantidad de veces que se aplicó la función y la cantidad de veces que se proceso un número par o impar.
CÓDIGO EN C:
RESULTADO DE SU EJECUCIÓN CON EL NÚMERO 27 DE EJEMPLO:
ENLACE PARA DESCARGAR CÓDIGO:
Comentarios
Publicar un comentario