Perplejo por el teorema de Rice

37

Resumen: Según el teorema de Rice, todo es imposible. ¡Y sin embargo, hago cosas supuestamente imposibles todo el tiempo!


Por supuesto, el teorema de Rice no dice simplemente "todo es imposible". Dice algo más específico: "Cada propiedad de un programa de computadora no es computable".

(Si desea dividir pelos, cada propiedad "no trivial". Es decir, propiedades que todos los programas posses o no hay programas poseen son trivialmente computable. Pero cualquier otra propiedad no es computable.)

Eso es lo que dice el teorema, o parece decir. Y presumiblemente un gran número de personas muy inteligentes han verificado cuidadosamente la exactitud de este teorema. ¡Pero parece desafiar completamente la lógica! ¡Existen numerosas propiedades de los programas que son triviales para calcular! Por ejemplo:

  • ¿Cuántos pasos ejecuta un programa antes de detenerse? Decidir si este número es finito o infinito es precisamente el problema de detención, que no es computable. ¡Decidir si este número es mayor o menor que algunos finitos es trivial! Simplemente ejecute el programa por hasta pasos y vea si se detiene o no. ¡Fácil!nn

  • Del mismo modo, ¿utiliza el programa más o menos de unidades de memoria en sus primeros pasos de ejecución? Trivialmente computable.nm

  • ¿El texto del programa menciona una variable llamada ? Un análisis textual trivial revelará la respuesta.k

  • ¿El programa invoca el comando ? Nuevamente, escanee el texto del programa buscando ese nombre de comando.σ

Veo un montón de propiedades que lo hacen parecer no computables así; por ejemplo, ¿cuántas adiciones realiza una ejecución completa del programa? Bueno, eso es casi lo mismo que preguntar cuántos pasos realiza el programa, que es prácticamente el problema de detención. Pero parece que hay un montón de propiedades de programas que son realmente fáciles de calcular. Y, sin embargo, el teorema de Rice insiste en que ninguno de ellos es computable.

¿Que me estoy perdiendo aqui?

Orquídea matemática
fuente
8
"Según el teorema de Rice, todo es imposible". - No "Cada propiedad de un programa de computadora no es computable". - No Sin embargo, no estás solo: la mayoría de los estudiantes se encuentran con este concepto erróneo.
Raphael

Respuestas:

36

Para los propósitos de esta discusión, un "programa" es un fragmento de código que siempre toma un número entero como entrada y se ejecuta para siempre o devuelve un número entero. Decimos que dos programas y g son extensionalmente iguales si calculan la misma función, es decir, para cada número n , tanto f ( n ) como g ( n ) se ejecutan para siempre, o ambos terminan y generan el mismo número.fgnf(n)g(n)

Una propiedad extensional de los programas es una propiedad que respeta la igualdad extensional, es decir, si f y g son extensionalmente iguales, entonces ambos tienen la propiedad P o ambos no la tienen.PfgP

Aquí hay algunos ejemplos de propiedades no extensivas:

  1. El programa se detiene en pasos. (Siempre podemos modificar un programa a uno extensivamente igual que se ejecute más tiempo).n
  2. El programa usa menos de celdas de memoria dentro de los primeros m pasos de ejecución. (Siempre podemos modificar un programa a uno extensionalmente igual para que use algo de memoria sin una buena razón).nm
  3. El texto del programa menciona una variable llamada k. (Podemos cambiar el nombre de las variables).
  4. ¿El programa invoca el comando . Esto puede depender un poco de lo que es σ , pero si es algo que puede simularse de alguna manera, entonces podemos evadir σ y aún así tener un programa que es extensionalmente igual al original.σσσ

Estoy seguro de que ha notado que enumeré precisamente sus supuestos contraejemplos al teorema de Rice, que dice:

Teorema (Rice): una propiedad extensible computable de los programas, ya sea de todos los programas o de ninguno.

Hay otra forma de explicar esto: debe distinguir entre un programa y la función que calcula. Muchos programas diferentes calculan la misma función (todos son extensionalmente iguales). El teorema de Rice trata sobre las propiedades de las funciones, no sobre las propiedades de los programas que las computan.

Andrej Bauer
fuente
No puedo obtener esta respuesta ... (Lo siento si estoy preguntando lo mismo, pero sería bueno aclarar este punto). Dice que puede modificar esos programas cambiando su sintaxis para obtener un equivalente extensional , pero ¿cómo verificar que esos son equivalentes extensionales en primer lugar? No puede usar un programa para comparar si las funciones de esos programas en general tienen ambas propiedades, por lo que cuando dice "modificarlo" creo que es posible porque son ejemplos simples (¿agregaría "modificarlo cuidadosamente"? O usar un "bien" IDE para ello "? ..) Creo que una vez que se modifica no se puede verificar en general , entonces, tal vez Rice aguante.
Hernan_eche
1
n+m=m+n
Además, está cometiendo un extraño salto de razonamiento en su razonamiento: dado que la igualdad extensional no es decidible, el teorema de Rice podría ser falso. ¿Cómo es eso? Y solo porque la igualdad extensional es indecidible, eso no significa que no haya instancias que podamos decidir. Los que mencioné, podemos decidirlos.
Andrej Bauer
36

Malentendido fundamental:

Cada propiedad de un programa de computadora no es computable

PRE

{MfMP}

P

El teorema de Rice trata las propiedades semánticas (propiedades de la función calculada por un programa, por ejemplo, dominio o rango de valores). A lo que se refiere son propiedades sintácticas (propiedades del programa , como el tiempo de ejecución o cuántas variables se utilizan).

Parece que no se sabe mucho por las propiedades sintácticas; ver a esta pregunta .

Rafael
fuente
1
Me perdí después de la primera oración más o menos. Lo siento. ¿Alguien puede explicar la diferencia entre una propiedad semántica y sintáctica?
MathematicalOrchid
@MathematicalOrchid: Puedes ignorar esa oración con seguridad; El primer párrafo contiene toda la información que necesita. Voy a elaborar, de todos modos.
Raphael
2
Semántico = sobre lo que hace el programa. Sintáctico = sobre cómo se ve el programa.
reinierpost