¿Por qué las funciones totales no son enumerables?
29
Aprendimos sobre el concepto de enumeraciones de funciones. En la práctica, corresponden a lenguajes de programación.
En un comentario pasajero, el profesor mencionó que la clase de todas las funciones totales (es decir, las funciones que siempre terminan para cada entrada) no es enumerable. Eso significaría que no podemos idear un lenguaje de programación que nos permita escribir todas las funciones totales pero no otras, ¡lo cual sería bueno tener!
Entonces, ¿cómo es que (aparentemente) tenemos que aceptar el potencial de no terminación si queremos una potencia computacional decente?
Debido a la diagonalización. Si fuera una enumeración computable de todas las funciones computables totales de N a N , de modo que cada f e fuera total, entonces g ( i ) = f i ( i ) + 1 también sería un total computable función, pero no estaría en la enumeración. Eso contradiría los supuestos sobre la secuencia. Por lo tanto, ninguna enumeración computable de funciones puede consistir exactamente en el total de funciones computables.(fe:e∈N)NNfeg(i)=fi(i)+1
Supongamos que pensamos en una función computable universal , donde "universal" significa que h es una función binaria computable y que por cada función unaria computable total f ( n ) hay alguna e tal que f ( i ) = h ( e , i ) para todo i . Entonces también debe haber alguna e tal que g ( n ) = h ( e , n )h(e,i)hf(n)ef(i)=h(e,i)ieg(n)=h(e,n)no es una función total, debido al párrafo anterior. De lo contrario, daría una enumeración computable de las funciones unarias computables totales que incluye todas las funciones unarias computables totales.h
Por lo tanto, el requisito de que cada función sea un sistema de funciones es total es incompatible con la existencia de una función universal en ese sistema. Para algunos sistemas débiles, como las funciones recursivas primitivas, cada función es total pero no hay funciones universales. Los sistemas más fuertes que tienen funciones universales, como la computabilidad de Turing, simplemente deben tener funciones parciales para permitir que exista la función universal.
Solo quería agregar que alguien encontró lo que parece ser un vacío en la diagonalización. Si usa una representación escrita para el programa, puede usar el sistema de tipos para no permitir la diagonalización y crear un autointerpretador total. Vea Romper la barrera de la normalización: un autointerpretador para F-omega para más detalles.
hatch22
Por supuesto, el Sistema F no es un sistema completo de Turing. El papel que vinculó es interesante; parece que se las arreglan para aprovechar la no completitud de Turing de una manera interesante.
Carl Mummert
No entiendo por qué "entonces también sería una función computable total". Si g es una función computable total, entonces ∃ k , f k = g , entonces evaluar g ( k ) requiere evaluar g ( k ) = f k ( k ) + 1 = g ( k ) + 1g(i)=fi(i)+1g∃k,fk=gsol( k )sol( k ) = fk( k ) + 1 = g( k ) + 1: conttradiction. Por lo tanto, parece que si hay una enumeración de funciones computables totales, ni siquiera podemos construir , de modo que no podemos llegar a una contradicción para refutar la hipótesis inicial (podemos llegar a una contradicción, pero simplemente refuta que g sea computable total). solsol
agemO
E incluso el uso de una diagonal desplazada para evitar este problema parece conducir a contradicciones.
agemO
10
Para ser claros, necesitamos distinguir las funciones matemáticas (las llamaré funciones y, a menudo, son incontables, por lo que no son enumerables) y funciones que puede escribir: las llamaré programas o también funciones computables .
Un subconjunto de un conjunto numerable E se llama computable si hay un programa que, dado un elemento x de E responde "sí" si x ∈ S y "no" si x ∉ S . (Y siempre tiene que responder algo) Un conjunto se llama recursivamente enumerable si el programa está autorizado a no responder en lugar de decir "no". (es equivalente a requerir que el programa imprima todos los elementos de S en cualquier orden)SmiXmix ∈ Sx ∉ SS
El conjunto de todos los programas que son totales en un conjunto finito es enumerable porque puede escribir un intérprete que simplemente ejecute el programa en todos los elementos del conjunto finito y devuelva "sí" si todos terminan. (Pero no puedo ver si alguno de ellos no)
Su profesor dijo que el conjunto de todos los programas que son totales en un conjunto infinito no es enumerable porque no puede simplemente ejecutar su programa en un número infinito de elementos.
Pero esto no significa que esto sea malo:
Por ejemplo, el conjunto si todos los programas que son demostrablemente totales es enumerable porque puede enumerar todas las pruebas y verificar mecánicamente si prueban que su programa es total.
Incluso un conjunto enumerable no sería práctico, ya que es posible que tenga que esperar para siempre sin estar seguro de si el procedimiento finalizaría algún día. No veo cómo usar un programa que enumere todas las funciones totales ...
¡Hay algunos lenguajes de programación donde todo lo que escribes está garantizado para terminar solo con la escritura estática! Incluso hay algunos que te garantizan un enlace polinómico. Por ahora, en su mayoría son académicos, escribir en ellos probablemente te hará sentir más las limitaciones que escribir en Python, pero hay muchos investigadores trabajando en esto.
Entonces, para responder a su pregunta: en cierto sentido, sí. La no terminación potencial es necesaria para completar Turing (la potencia de cálculo más alta por ahora). Pero no encuentro esto directamente relevante al hecho de que las funciones totales son enumerables o no. ¡Aún puedes escribir todos los programas totales!
"porque no puede simplemente ejecutar su programa en un número infinito de elementos": este es un argumento débil, ya que es posible que no necesite hacer esto si puedo recuperar toda la información que necesito del programa en sí. Vea aquí una pregunta que ilustra el peligro de su razonamiento.
Raphael
En efecto. No afirmé que fuera una prueba (como siempre debes construir un argumento diagonal) y tal vez no debería haber usado la palabra "porque". Estaba tratando de responder a su pregunta que (pensé) no era sobre una prueba de la declaración de su profesor sino sobre por qué la terminación entra en conflicto con el poder computacional.
Para ser claros, necesitamos distinguir las funciones matemáticas (las llamaré funciones y, a menudo, son incontables, por lo que no son enumerables) y funciones que puede escribir: las llamaré programas o también funciones computables .
Un subconjunto de un conjunto numerable E se llama computable si hay un programa que, dado un elemento x de E responde "sí" si x ∈ S y "no" si x ∉ S . (Y siempre tiene que responder algo) Un conjunto se llama recursivamente enumerable si el programa está autorizado a no responder en lugar de decir "no". (es equivalente a requerir que el programa imprima todos los elementos de S en cualquier orden)S mi X mi x ∈ S x ∉ S S
El conjunto de todos los programas que son totales en un conjunto finito es enumerable porque puede escribir un intérprete que simplemente ejecute el programa en todos los elementos del conjunto finito y devuelva "sí" si todos terminan. (Pero no puedo ver si alguno de ellos no)
Su profesor dijo que el conjunto de todos los programas que son totales en un conjunto infinito no es enumerable porque no puede simplemente ejecutar su programa en un número infinito de elementos.
Pero esto no significa que esto sea malo:
Por ejemplo, el conjunto si todos los programas que son demostrablemente totales es enumerable porque puede enumerar todas las pruebas y verificar mecánicamente si prueban que su programa es total.
Incluso un conjunto enumerable no sería práctico, ya que es posible que tenga que esperar para siempre sin estar seguro de si el procedimiento finalizaría algún día. No veo cómo usar un programa que enumere todas las funciones totales ...
¡Hay algunos lenguajes de programación donde todo lo que escribes está garantizado para terminar solo con la escritura estática! Incluso hay algunos que te garantizan un enlace polinómico. Por ahora, en su mayoría son académicos, escribir en ellos probablemente te hará sentir más las limitaciones que escribir en Python, pero hay muchos investigadores trabajando en esto.
Entonces, para responder a su pregunta: en cierto sentido, sí. La no terminación potencial es necesaria para completar Turing (la potencia de cálculo más alta por ahora). Pero no encuentro esto directamente relevante al hecho de que las funciones totales son enumerables o no. ¡Aún puedes escribir todos los programas totales!
fuente