Perplexo com o teorema de Rice

37

Resumo: De acordo com o teorema de Rice, tudo é impossível. E, no entanto, faço essas coisas supostamente impossíveis o tempo todo!


Obviamente, o teorema de Rice não diz simplesmente "tudo é impossível". Diz algo bastante mais específico: "Todas as propriedades de um programa de computador não são computáveis".

(Se você deseja dividir os cabelos, todas as propriedades "não triviais". Ou seja, as propriedades que todos os programas possuem ou que nenhum programa possui são trivialmente computáveis. Mas qualquer outra propriedade não é computável.)

É o que o teorema diz, ou parece dizer. E, presumivelmente, um grande número de pessoas muito inteligentes verificou cuidadosamente a correção desse teorema. Mas parece desafiar completamente a lógica! Existem inúmeras propriedades de programas que são triviais para calcular !! Por exemplo:

  • Quantas etapas um programa executa antes de parar? Decidir se esse número é finito ou infinito é precisamente o Problema da Parada, que não é computável. Decidir se esse número é maior ou menor que algum finito é trivial! Basta executar o programa por até etapas e ver se ele pára ou não. Fácil!nnn

  • Da mesma forma, o programa usa mais ou menos que unidades de memória em seus primeiros passos de execução? Trivialmente computável.mnm

  • O texto do programa menciona uma variável chamada ? Uma análise textual trivial irá revelar a resposta.k

  • O programa chama o comando ? Mais uma vez, verifique o texto do programa procurando esse nome de comando.σ

Eu posso ver muitas propriedades que fazem olhar não-computável bem; por exemplo, quantas adições uma execução completa do programa executa? Bem, é quase o mesmo que perguntar quantas etapas o programa executa, que é praticamente o Problema da Parada. Mas parece que há um monte de propriedades do programa que são muito, muito fáceis de calcular. E, no entanto, o teorema de Rice insiste que nenhum deles é computável.

O que estou perdendo aqui?

MathematicsOrchid
fonte
8
"Segundo o teorema de Rice, tudo é impossível." -- Não. "Todas as propriedades de um programa de computador não são computáveis." -- Não. Você não está sozinho: a maioria dos estudantes encontra esse equívoco.
Raphael

Respostas:

36

Para os fins desta discussão, um "programa" é um pedaço de código que sempre aceita um número inteiro como entrada e é executado para sempre ou retorna um número inteiro. Dizemos que dois programas de e são extensionalmente igual se computar a mesma função, ou seja, para cada número ou ambos e correr para sempre, ou ambos terminar e saída o mesmo número.g n f ( n ) g ( n )fgnf(n)g(n)

Uma propriedade extensional de programas é uma propriedade que respeita a igualdade extensional, ou seja, se e são extensionalmente iguais, então ambos têm a propriedade ou ambos não a possuem.f g PPfgP

Aqui estão alguns exemplos de propriedades não- dimensionais:

  1. O programa pára dentro de etapas. (Podemos sempre modificar um programa para um extensionally igual que seja executado por mais tempo.)n
  2. O programa usa menos de células de memória nas primeiras etapas de execução. (Nós sempre podemos modificar um programa para um extensionally igual para que ele consuma alguma memória sem uma boa razão.)mnm
  3. O texto do programa menciona uma variável chamada k. (Podemos renomear variáveis.)
  4. O programa chama o comando . Isso pode depender um pouco do que é , mas se é algo que pode ser simulado de alguma forma, podemos fugir do e ainda ter um programa que é extensionalmente igual ao original.σ σσσσ

Tenho certeza que você notou que listei precisamente seus supostos contra-exemplos ao teorema de Rice, que diz:

Teorema (Rice): Uma propriedade extensional computável de programas retém todos os programas ou nenhum.

Há outra maneira de explicar isso: você precisa distinguir entre um programa e a função que ele calcula. Muitos programas diferentes calculam a mesma função (todos são extensionalmente iguais). O teorema de Rice é sobre propriedades de funções, não sobre propriedades de programas que as computam.

Andrej Bauer
fonte
Não consigo obter esta resposta .. (Desculpe se estou perguntando o mesmo, mas seria bom esclarecer esse ponto). Ele diz que você pode modificar esses programas alterando sua sintaxe para obter um equivalente extensional , mas como verificar esses são equivalentes extensional em primeiro lugar? Você não pode usar um programa para comparar se essas funções em geral têm essas duas propriedades; portanto, quando você diz "modificá-lo", acho possível porque são exemplos simples (você adiciona "modifique-o com cuidado"? Ou usa um "bom IDE para isso "? ..) Eu acho que uma vez modificado, você não pode verificar em geral , então, talvez Rice aguente.
Hernan_eche 16/06
1
n+m=m+n
Além disso, você está cometendo um salto estranho no raciocínio: como a igualdade extensional não é decidível, o teorema de Rice pode ser falso. Como assim? E apenas porque a igualdade extensional é indecidível, isso não significa que não haja nenhuma instância dela que possamos decidir. Os que eu mencionei - nós podemos decidir isso.
Andrej Bauer
36

Incompreensão fundamental:

Todas as propriedades de um programa de computador não são computáveis

PRE

{MfMP}

P

O teorema de Rice lida com propriedades semânticas (propriedades da função calculada por um programa, por exemplo, domínio ou faixa de valor). A que você se refere são propriedades sintáticas (propriedades do programa , como tempo de execução ou quantas variáveis ​​são usadas).

Não se sabe muito sobre propriedades sintáticas; veja esta pergunta .

Rafael
fonte
1
Eu me perdi depois da primeira frase mais ou menos. Desculpe. Alguém pode elaborar a diferença entre uma propriedade semântica e uma sintática?
MathematicalOrchid
@ MathematicsOrchid: Você pode ignorar com segurança essa frase; o primeiro parágrafo contém todas as informações necessárias. Eu vou elaborar, de qualquer maneira.
Raphael
2
Semântica = sobre o que o programa faz. Sintático = sobre a aparência do programa.
Reinierpost