¿Qué es un cálculo?

La mayoría de las veces el cálculo se realiza en tres formas equivalentes: máquinas de registro, máquinas de torneado y cálculo lambda. También puede tener cosas como máquinas Oracle, que pueden calcular problemas arbitrarios con su Oracle incorporado, pero no son tan útiles para observar las propiedades del lenguaje de programación del mundo físico.

Una función es computable en una máquina abstracta dada si puede escribir un programa que realice la función, es decir, toma las entradas de la función y genera lo mismo que la función.

Usted demuestra que una función es indiscutible asumiendo que tiene dicho programa y luego encuentra una contradicción. La contradicción clásica es encontrar una correlación con el problema de detención, que se sabe que no se puede calcular en una máquina de registro. O muchas veces, los problemas surgen cuando ejecuta un programa en su propio código.

Permítanme darles un ejemplo de una función no computable de la máquina de registro: F toma el contenido inicial de todos los registros y el código del programa, y ​​emite un límite en el valor máximo en cualquier registro si ese valor es finito.

F es indiscutible porque puede usarse para resolver el problema de detención. Suponga que F nos da el límite máximo N. Luego hay P * (N ^ R) posibles estados en el cálculo, donde P es la longitud del código del programa y R es el número de registros. Itere el programa P * (N ^ R) + 1 veces.

Si se detiene antes de esto, entonces sabemos que el programa se detendrá. Si no lo hace, ha visitado un estado determinista dos veces en su ejecución, lo que demuestra que hay un bucle y que no se detendrá. F se ha utilizado para resolver el problema de detención de esta manera y, por lo tanto, no es computable.