Perplexo com o teorema de Rice

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!$n$$n$

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

• 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.$\sigma$

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?

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 $f$$g$$n$$f(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 $P$$f$$g$$P$

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.)$n$$m$
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.σ $\sigma$$\sigma$$\sigma$

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.

Incompreensão fundamental:

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

$\emptyset \subset P \subset \mathsf{RE}$

$\qquad \displaystyle \{ \langle M \rangle \mid f_M \in P \}$

$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 .