Funciones matemáticas no computables

Question

Estaba leyendo esto en mis notas, pero no tiene ningún sentido para mí:

Sin embargo, supongamos que x un alfabeto para escribir nuestros programas (por ejemplo, 8 bits ASCII). Como cada programa individual tiene una longitud nula, podemos poner todos los programas posibles en una lista lista ordenada. Para cualquier carácter xed longitud k, sólo hay un conjunto nito de programas posibles. Por lo tanto, podemos escribir todos los programas escribiendo primero todos los programas de 1 carácter, luego todos los programas de 2 caracteres, y y así sucesivamente. En otras palabras, hay una biyección entre los enteros y el conjunto total de programas. Pero esto significa que el número de funciones es incontable, mientras que el número de programas es sólo contablemente innato. Por tanto, en debe haber funciones matemáticas que no podemos calcular con ningún (nite-length) programa.

¿Qué es exactamente lo que se dice? ¿Por qué se sostiene? Parece que no debería. En algunos casos, un programa de sólo 30-40 caracteres puede calcular miles de millones de números. Tal vez con el hardware actual no sea posible computar algunos números, pero teóricamente, esto no debería ser un problema, ¿verdad?

Answer 1

Cantor's argumento diagonal puede utilizarse para demostrar que el número de funciones de $\mathbb{N}$ a $\mathbb{N}$ es incontable. Sin embargo, de esas funciones, el número de funciones que pueden ser calculadas por cualquier programa de ordenador es contable porque sólo hay un número contable de programas de ordenador. Por lo tanto, existen funciones que no pueden ser calculadas por un programa de ordenador; de hecho, "la mayoría" de las funciones tienen esta propiedad. Un ejemplo explícito es el función de castor ocupado .

No se trata de computar números sino de computar secuencias de los números, y es una limitación fundamental de la computación.

Answer 2

He aquí una analogía que puede resultar útil: hay números racionales que pueden representarse como el cociente de dos enteros: 1/2, 3, 5/6, etc. Esto puede verse como todos los números que pueden ser impresos por "programas" que sólo tienen acceso al operador "división". Está claro que algunos números no pueden ser impresos por un programa que sólo tenga esta operación - $\pi$ por ejemplo, no puede.

Ahora supongamos que añadimos toda la potencia de la aritmética: se puede especificar un número como "la raíz de $x^2-2x+3$ ". Estos son los números algebraicos. Podemos imprimir más números de esta manera, pero no todos. $\pi$ de nuevo no puede ser impreso por este tipo de programa, ya que es trascendental.

Como último recurso, permitimos cualquier operación que pueda imprimir un número arbitrario de dígitos en un tiempo finito. Ahora podemos encontrar valores como $\pi$ y $e$ ya que existen fórmulas para ello. Pero podemos imprimir todo ¿valores?

La respuesta es no. Como ha indicado, hay "demasiados" números y muy pocos programas. No se trata simplemente de que no hayamos descubierto (o creado) alguna operación: aunque dupliquemos el número de símbolos en nuestro lenguaje, eso sólo aumenta la cantidad de números que podemos escribir en una cantidad finita, y hay una cantidad infinita de espacio para compensar.

En lugar de hablar de programas, otra forma de expresarlo es: "para cada número real, ¿hay algún finitario descripción de la misma?" Por ejemplo $e=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n$ - aunque $e$ tiene un número infinito de dígitos, podemos describirlo utilizando sólo un número finito de símbolos. La prueba que comentas muestra que debe haber algunos números que no admiten una descripción finita.

Answer 3

Cada cadena (que se analiza) representa un programa que calcula una función sobre $\rm\:\mathbb N$ . El argumento muestra que el número de funciones representables por tal lenguaje es contable porque el número de cadenas de programas en el lenguaje es contable (nótese que algunos programas pueden calcular la misma función). Pero hay un número incontable de funciones en $\rm\:\mathbb N\:$ por diagonalización (du-Bois-Reymond, Cantor). Por lo tanto, hay funciones no computables por ningún programa en el lenguaje.

Quizá le resulte útil considerar un lenguaje más explícito. Por ejemplo, considere un lenguaje que represente polinomios con coeficientes naturales. Un argumento análogo muestra que tales polinomios son contables, por lo que podemos enumerarlos, es decir, podemos indexar los polinomios por naturales: $\rm\ f_i(x),\ \:i\in \mathbb N\:.\ $ Por diagonalización podemos construir una función no polinómica sobre $\rm\:\mathbb N\:,\:$ Por ejemplo $\rm\;\ g(n)\ :=\ f_n(n)+1\:.\ $ Tenga en cuenta que si $\rm\ f_i = g\ $ entonces $\rm\ f_i(i) = g(i) = f_i(i) + 1\:,\ $ una contradicción. Por lo tanto, $\rm\:g\:$ no es igual a ninguna función polinómica $\rm\:f_i\:.$

Answer 4

Está buscando el Problema de detención y Lógica de orden superior .

En realidad, no se pueden contar las funciones a través de sus representaciones como programas, porque no se pueden comparar todos los comportamientos de los programas ni averiguar todos los programas que no se detienen en absoluto. Podrías definir una función que no sólo es indefinida en algunos o muchos de los incontables puntos, sino que además no se puede demostrar que sea indefinida en esos puntos. Si pudieras, entonces podrías contar las funciones de la Lógica de Primer Orden, pero todavía no las de la Lógica de Orden Superior (¿Lógica de Segundo Orden?) y superiores.

Además, hay funciones que no pueden expresarse en absoluto como programas, como la "función del castor ocupado": Describe para cada n el mayor número finito de pasos después de los cuales se detiene cualquier programa de longitud n. El programa de esta función debería tener una longitud de descripción infinita para ser correcto. La función del castor ocupado podría resolver el problema de detención a través del tiempo de espera, si fuera expresable como un programa (finito).

Lo que puedes contar, que son los códigos fuente de todos los programas. De manera similar, todas las funciones pueden ser representadas como una cantidad finita de tiza - en infinitas formas diferentes. Pero incluso con esto, sólo pueden ser descritas pero no siempre en todas sus propiedades demostradas, porque existen teoremas que son verdaderos aunque no puedan ser demostrados, y porque la posibilidad de una demostración no siempre implica la existencia de un ejemplo demostrado. Para compararlo con la función del castor ocupado: Existen funciones que necesitarían una cantidad infinita de tiza para ser probadas (en otras palabras: no pueden ser probadas) pero no para ser descritas; mapear esas funciones a programas requeriría probarlas primero (→ imposible o el programa no se detendrá) o implicaría probarlas (→ descripción infinita del programa). Como ejemplo: Pensemos en un programa H que recibe la descripción de otro programa P como entrada y necesita calcular una propiedad existente pero no demostrable de ese programa P (como que se detenga o no) y por tanto no se detendría a sí mismo; la función podría definirse simplemente sobre esa propiedad existente, lo que la convierte en otra cosa que este programa H que no se detiene.