Significado intuitivo del concepto de "computable"

Question

Mi pregunta es una pregunta de seguimiento a esta: ¿Cómo demostrar que una función es computable?

La pregunta original era:

Es el siguiente función $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable?

El aceptó respuesta fue que esta función es computable porque es la constante de 1 o de la función de la función que es de 1 en todas partes, excepto en la entrada 0.

Según mi profesor en la universidad, esta respuesta es de hecho correcta. Pero no entiendo la intuición detrás de él.

Hasta donde yo sé, "computable" significa (entre otras cosas) de que existe un algoritmo que realmente puede calcular la función. Yo realmente no se cómo un algoritmo sería en este caso. Obviamente, si $x\geq 1$, el algoritmo puede volver 1. Pero si la entrada es 0, el algoritmo tendría que simular $\phi_0(0)$. Si $\phi_0$ termina en la entrada 0, entonces el algoritmo puede volver 1. Pero si $\phi_0$ no termina en la entrada 0, el algoritmo se ejecutará para siempre y no volver nunca 0.

Así que mi forma de entender el concepto "computable" está en conflicto con su significado real. Alguien puede explicar que el error en mi razonamiento se encuentra?

Answer 1

Lo que tienes es una definición de una función de $g$, no de un algoritmo para el cálculo de la misma. La definición está escrito en el lenguaje de las matemáticas, donde "$a$ o $b$" es equivalente a "$b$ o $a$", no en un lenguaje de programación, donde "$a$ o $b$" podría significar "evaluar primero la $a$, y si es cierto, entonces la afirmación es verdadera, de lo contrario evaluar $b$ y dejar que sea el valor de verdad de la afirmación". En particular, el primer caso de la definición no significa "en primer lugar, calcular $\varphi_x(x)$, y si se detiene, mira a ver si $x\ge 1$; si es así, vuelva $1$".

En relación a lo que el formalismo adoptamos - máquinas de Turing, cálculo lambda, de transformación gramáticas, etc. - $\varphi_0(0)\!\!\downarrow$ tiene algún valor de verdad $tv$. Podemos ya sé lo que es (se detiene rápidamente, o seguramente no halt), puede que no sabemos todavía (no se ha detenido todavía), o tal vez nunca lo sabremos (porque realmente es falso). En cualquier caso, $g$ es igual a una de las dos funciones computables, cada uno de los cuales tiene un algoritmo trivial que no le hace caso acerca de $\varphi_0$ y cómo se comportan en la entrada de $0$. Cualquiera que sea la función $g$ es, es computable. Solo que uno es depende de $tv$, por lo que no puede ser capaz de decir que la función $g$ es en realidad.

Esto es una reminiscencia de la muy no constructiva prueba de que hay irrationals $x,y$ tal que $x^y$ es racional: si ${\sqrt 2}^{\sqrt 2}$ es racional, deje $x=y={\sqrt 2}$; de lo contrario, deje $x={\sqrt 2}^{\sqrt 2}, y = {\sqrt 2}$. (De hecho, la diversión se ha echado a perder: alguien se ha demostrado que el ${\sqrt 2}^{\sqrt 2}$ es irracional. Así que quizás ${\sqrt 3}^{\sqrt 2}$, de aquí en adelante :) de igual manera, la definición de $g$ no es constructivo: se utiliza la ley de medio excluido de una forma esencial. La prueba de que $g$ existe (es decir, que es aún bien definida) es un no constructiva existencia de prueba de un algoritmo, no de un algoritmo.

Answer 2

Una función no es la misma cosa que las palabras usadas para describir. La función es sólo la asignación de las entradas en salidas. Que la asignación puede ser descrito en una infinidad de maneras diferentes. Por ejemplo, la identidad de la función podría ser descrito como "Dado $x$, la salida $x$", o como "Dado $x$, añada $5$$x$. Ahora multiplique $x$$3$, y restar $15$. Ahora divida por $3$. Salida el resultado."

La pregunta "¿es esta la función computable" significa "¿existe un algoritmo que pasa a producir la misma salida de esta función para todas las entradas", y no "¿existe un algoritmo que asemeja a esta descripción de la función", porque usted se está preguntando acerca de la función, no la particular descripción de la misma.