Problemas Algorítmicos Computables

Introducción

El presente post nos muestra que existen funciones que no conocíamos y que son difíciles  de resolver mediante un algoritmo de algún lenguaje de programación.

No intentaremos resolverlos pero si veremos algunos que pueden resolverse, lo interesante de este tema es mostrar que existen diferentes funciones o problemas computables y parcialmente computables que han venido surgiendo desde hace algunos años y que gracias a algunas personas como Alan Turing, Kurt Gödel, nos han mostrado que hay soluciones para dichos problemas.

Funciones Computables

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing.

Un problema es computable cuando existe un procedimiento efectivo (algoritmo) que permite obtener, para cualquier entrada, una cadena  que le corresponde como solución del problema.

Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la Tesis de Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentemente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas con un oráculo por A o f. Tales funciones pueden ser llamadas A-computable o f-computable respectivamente. Antes de la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable.

Las funciones computables son usadas para discutir sobre computabilidad sin referirse a ningún modelo de computación concreto, como el de la máquina de Turing o el de la máquina de registros. Los axiomas de Blum pueden ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.

Según la Tesis de Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidas por funciones recursivas, cálculo lambda, o algoritmos de Markov.

Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, una máquina de Post, o una máquina de registros.

En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable es conocido como un problema de funciones. 

EJEMPLO: un ejemplo de función computable, es una máquina que devuelve el cambio (cajero automático)

Funciones Parcialmente Computables

Una función parcialmente computable  posee un algoritmo que nos permite computar su valor para elementos de su dominio, pero que nos tendrá computando eternamente si intentamos obtener un valor funcional para un elemento que no está en su dominio, sin asegurarnos nunca que no obtendremos un valor. En otras palabras, cuando es posible una respuesta, el algoritmo la provee; cuando no es posible, el algoritmo nos mantiene buscando la respuesta en vano por un tiempo infinito.

Si una función es parcialmente computable, la máquina que la calcula puede no parar,  o parar con una salida indefinida, para aquellos valores en los que la función no  esté definida.