Intuitivamente, ¿qué es una función computable?

Básicamente, una función es computable si hay una forma finita de calcular cada uno de sus valores. En realidad, no tiene que calcular cada valor, solo tiene que tener un algoritmo que lo haga.

Por lo tanto, se dice que calcular pi es computable, porque podemos calcular tantos dígitos o pi como desee.

Eso es todo lo que significa que una función sea computable.

——–

Proponer una función no computable es un desafío. Si quieres ver uno sigue leyendo.

Una explicación del problema de detención para los laicos

Considere el conjunto de programas Java. Este es un conjunto infinito, porque Java no limita el tamaño de sus programas. Pero sí requiere que cada programa Java tenga un número finito de caracteres, de lo contrario, ¿quién podría escribir un programa que sea infinitamente largo?

El conjunto de programas Java es infinitamente contable porque se pueden enumerar en orden de cantidad de caracteres que contienen. Considere esta lista de programas Java en orden de tamaño, J1, J2, J3, …

Aquí le mostramos cómo obtener un número inconfundible.

Vamos a crear un número al que llamaremos x y será entre 0 y 1 con solo 0 y 1 en él. Entonces se verá más o menos así:

x = .1101001011 …

Aquí se explica cómo crearlo.

Mire el primer programa Java en la lista, J1. (Este será el programa Java más corto posible). Ahora preguntamos si este programa termina en todas las entradas legales. Si es así, ponga un 1 en primer lugar a la derecha del punto decimal. Como este primer programa literalmente no hace nada, terminará, por lo que nuestro número, x, comenzará así:

x = .1 …

Ahora el siguiente programa en esta lista tampoco hace nada, por lo que termina. Así podemos actualizar x para:

x = .11 …

Y así mantenemos esto para cada programa Java en la lista. Ponemos un 1 en el enésimo lugar decimal de x si ese programa Java, Jn, termina en todas las entradas legales y 0 si no lo hace.

Pero aquí está el problema. Alan Turing demostró lo que ahora llamamos ‘El problema de la detención’. Mostró que no existe un algoritmo para determinar si algún programa terminará en todas las entradas o no. Por lo tanto, no existe un algoritmo que pueda calcular cada dígito dado de x. Entonces x es un número no computable.

Tenga en cuenta que x está bien definido. El enésimo dígito de x es 1 si el enésimo programa Java se detiene en todas las entradas y 0 en caso contrario. Cualquier programa debe detenerse o no.

Entonces, nuestro problema no es con x, se debe al hecho de que ciertos números no son computables.

Una función computable es una función que devuelve un resultado computable para cada parámetro de entrada posible.

Dado que los símbolos pueden representar números y los números pueden representar símbolos, la computabilidad, al menos en teoría, puede expresarse como resultado de un número que es computable.

En “Sobre números computables”, Alan Turing definió un número computable como uno que puede escribirse usando un número finito de dígitos.

Entonces, una función computable produce resultados para un número finito de dígitos para todas las entradas posibles y con un número finito de pasos.

O, se ha demostrado que es infinito en ambos casos, como se sabe que pi es computable, por ejemplo, aunque requiere una memoria infinita para computar. Para obtener más información, consulte el problema de detención.

Una función [math] f [/ math] es computable si existe un algoritmo que, dado cualquier argumento [math] x [/ math], eventualmente devolverá el valor [math] f (x) [/ math]. Si pensamos en los algoritmos como programas, entonces intuitivamente, una función [matemática] f [/ matemática] es computable si podemos escribir un programa que lo haga en cualquier entrada significativa [matemática] x [/ matemática] salida [matemática] f (x )[/mates].