(Falso?) Prueba de computabilidad de una función?

Considere , una función que devuelve 1 si n ceros aparecen consecutivamente en π . Ahora alguien me dio una prueba de que f ( n ) es computable:$f(n)$$n$$\pi$$f(n)$

O para todo n, aparece en π , o hay una am st 0 m aparece en π y 0 m + 1 no. Para la primera posibilidad f ( n ) : = 1 ; Para el segundo f ( n ) : = 1 iff n ≤ m , 0 en caso contrario.$0^n$$\pi$$0^m$$\pi$$0^{m+1}$$f(n) := 1$$f(n) := 1$$n \leq m$

El autor afirma que esto demuestra la computabilidad de , ya que existe un algoritmo para calcularlo.$f(n)$

¿Es correcta esta prueba?

Piénselo de esta manera, Mike: esta prueba se "ramifica" en múltiples casos posibles, uno de los cuales tiene que ser cierto (usando la ley del medio excluido que para cada proposición , p es verdadera o ¬ p es verdadera). Pero al final de cada una de estas ramas, siempre logras demostrar que la función f es computable. Por lo tanto, no importa cuál de los casos tenga realmente en la vida real, f debe ser computable. (Sin embargo, la razón precisa por la que f es computable será diferente, dependiendo de la rama).$p$$p$$\neg p$$f$$f$ $f$

Es correcto. Esto es lo mismo que lo siguiente: defina como la función constante x ↦ 0 si Dios existe, y x ↦ 1 si Dios no existe. La función resultante es una función constante, por lo tanto, computable. Lo que quizás no pueda hacer es asignar esa función, pero la función en sí es computable.$f(x)$$x \mapsto 0$$x \mapsto 1$

Aquí, una de las dos posibilidades es verdadera: o existe tal , o no existe. La función es la función constante x ↦ 1 o una función de umbral simple, definida con m .$m$$x \mapsto 1$$m$

Creo, y espero, que cada estudiante de informática se enfrenta a este problema que se siente como una paradoja. Es un muy buen ejemplo de la diferencia de computable en sentido TCS y computable en sentido práctico.

Mis pensamientos en ese entonces eran: "Sí, si supiera la respuesta, obviamente sería computable. ¿Pero cómo averiguarlo?" El truco es librarse de la ilusión de que tiene que descubrir si tiene esta propiedad o no. Porque esto, obviamente (léase: imho), no puede ser realizado por una máquina de Turing (siempre y cuando no tengamos más conocimiento del que tenemos sobre π ).$\pi$$\pi$

Considere su definición de computabilidad: decimos $f$ es (Turing-) computable si y solo si . Es decir, solo tienes que demostrar la existencia de una máquina de Turing adecuada, no dar una . Lo que usted, nosotros, intentamos hacer allí es calcular la máquina de Turing que calcula la función requerida. ¡Este es un problema mucho más difícil!$\exists M \in TM : f_M = f$

La idea básica de la prueba es: te doy una clase infinita de funciones, todas ellas computables (para mostrar; triviales aquí). Pruebo entonces que la función que está buscando está en esa clase (para mostrar; distinción de mayúsculas y minúsculas aquí). qed

Sí, es cierto, es computable. El problema es que su función realmente no está produciendo la solución a una familia infinita de problemas, la forma (digamos) de una función que calcula una solución al problema de detención es, por lo que no hay problema con el cálculo. En cambio, está representando en forma de función algún hecho matemático único con representación finita, ya sea un número entero o el hecho de que f es la función constantemente 1

Es posible codificar el problema de detención en números reales individuales , como el constante de Chaitan , pero los enteros siempre tienen representaciones finitas y, por lo tanto, pueden codificarse como Máquinas de Turing.$\Omega$

Encontrar el algoritmo correcto, por supuesto, podría ser un problema difícil. ¡Pero encontrar algoritmos correctos suele ser difícil!

publicar un poco viejo, pero quería publicar otra respuesta.

Esta es una prueba no constructiva (o argumento) de computabilidad. Simplemente dice que la función debe existir en algún sentido ya que puedo representarla (o indexarla más correctamente), en el conjunto (o universo) de funciones computables. Sin embargo, ni construye la máquina en sí (es decir, el algoritmo), ni el índice (suponiendo una enumeración efectiva de máquinas computables). La frase inglesa " gracias por nada ", parece en estos casos más apropiada, como la siguiente:

-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

Las personas en la historia de las matemáticas han discutido bastante sobre la validez real (o rango de validez) y el significado de tales argumentos. El resultado final es que el mismo tipo de argumentos reaparecen en los teoremas de incompletitud de Goedel y se vuelven contra esta "suposición de universo cerrado" .

Si no te gustan tanto estos argumentos, no te culparía.