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.
- ¿Alguien ha explorado el uso de autómatas celulares 2D en una superficie esférica sintonizada para proyectar un universo 3D dentro que simule la gravedad?
- ¿Cuál es el uso de las matemáticas en el mundo real en informática?
- ¿Qué importancia tiene, si es que lo es, la teoría de grupos y el álgebra abstracta para comprender la programación funcional?
- ¿Qué clases de problemas no se pueden resolver con métodos de optimización?
- ¿Es P vs NP el problema más difícil e importante del Premio del Milenio?
——–
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.