miércoles, 3 de febrero de 2010

Demostraciones de tipo Cantor en lógica

En la teoría de computación hay un tipo de funciones que se llaman funciones recursivas primitivas.

Hofstadter utiliza lo que él llama el lenguaje BuD para explicar estas funciones. El lenguaje BuD consta de bucles delimitados. Es decir, lo que en los lenguajes informáticos suelen ser los bucles FOR. Es decir, bucles que tienen un número finito de pasos (en cambio, los bucles while, pueden tener un número infinito de pasos, de manera que, a priori, no es fácil saber si un bucle while acabará, o seguirá funcionando ad infinitum).

Las funciones recursivas totales son funciones que cumplen la siguiente condición: para todo x que pertenece al dominio, existe una y en el rango, tal que y=f(x). Es decir, para todo valor, el programa acaba parando en un tiempo finito.

Las funciones estrictamente parciales son funciones tales que, para algún valor del dominio el programa se pierde en un bucle infinito. Para algún valor x que pertenece al dominio, no existe ningún y en el rango, tal que y= f(x). (Si bien, en general, se llama funciones parciales tanto a las totales como a las parciales)

Hay una demostración de que existen funciones recursivas totales que no son recursivas primitivas.

La demostración se desarrolla así:

1) existe una enumeración recursiva de las funciones recursivas primitivas (es decir, estas funciones se pueden ordenar por orden alfabético). uno se puede imaginar estas funciones como programas de ordenador, cada uno con un número P[1], P[2], P[3], etc... También podemos imaginarlos como funciones, f[1], f[2], f[3]...

2) Cada programa debe aceptar un número natural como input. Por ejemplo, si P[2], es el programa que suma a cada número 1, entonces, el resultado de P [2][3], es 4, y el resultado de P[2][n] es (n+1). Igualmente, la función f[1], con input 1, podríamos llamarla f[1] (1).

3) hora, supongamos que existe una función tal que f(x)= f[x](x) +1. Ahora supongamos que f(x) es una función recursiva primitiva. Pero entonces f(x) debe ser f[1] o f[2],... o f[n]. Pero ¡no puede serlo! Porque, para todo n, f[n] es igual a f[n] (n) + 1. Por tanto, f(n) no está en la lista de las funciones recursivas primitivas.

El resultado demuestra que existen funciones recursivas totales que no son recursivas primitivas.

No hay comentarios: