Teorema de Rice

Na teoria da computação, o teorema de Rice afirma que, para qualquer propriedade não-trivial de funções parciais, não existe um método geral e eficaz para decidir se um algoritmo calcula uma função parcial com essa propriedade. Aqui, uma propriedade de funções parciais é chamada trivial se ela vale para todas as funções parciais computáveis ou nenhuma, e um método de decisão eficaz é chamado geral se este decide corretamente para cada algoritmo. O teorema tem o nome de Henry Gordon Rice, é também conhecido como Teorema de Rice-Myhill-Shapiro. No título do teorema, depois de Rice, temos os matemáticos John Myhill e Norman Shapiro.

Introdução

Segue uma outra forma de declarar o teorema de Rice que é mais útil em teoria da computação:

Seja S um conjunto de linguagens que são não-triviais, o que significa:

existe uma máquina de Turing que reconhece uma linguagem em S (S é um conjunto de linguagens)
existe uma máquina de Turing que reconhece uma linguagem que não está em S

Então, é indecidível determinar se a linguagem decidida por uma máquina de Turing arbitrária encontra-se em S. Na prática, isso significa que não existe uma máquina que sempre pode decidir se a linguagem de uma dada máquina de Turing tem uma propriedade não-trivial. Casos especiais incluem a indecidibilidade de se saber se uma máquina de Turing aceita uma cadeia(String) específica, e se a linguagem reconhecida por uma máquina de Turing pode ser reconhecida por uma máquina trivial mais simples, como um autômato finito.

É importante notar que o teorema de Rice não diz nada sobre as propriedades das máquinas ou programas que não são propriedades de funções ou linguagens. Por exemplo, se uma máquina funciona há mais de 100 passos em uma entrada é uma propriedade decidível, mesmo que ele não seja trivial. Implementar exatamente a mesma linguagem, duas máquinas diferentes podem exigir um número diferente de passos para reconhecer a mesma entrada. Da mesma forma, se uma máquina tem mais de 5 estados é uma propriedade decidível. Quando uma propriedade é do tipo que qualquer uma das duas máquinas podem ou não tê-la, enquanto ainda não for implementada exatamente a mesma língua, a propriedade é das máquinas e não da linguagem, e Teorema de Rice não se aplica.

Usando a caracterização de Rogers de sistemas de programação aceitável, o Teorema de Rice pode essencialmente ser generalizado a partir de máquinas de Turing para a maioria das linguagens de programação dos computadores: não existe um método automático que decide com generalidade perguntas não-triviais sobre o comportamento de caixa-preta de programas de computador.

Como exemplo, considere a seguinte variante do problema da parada: Pegue a propriedade uma função parcial F se F é definido para o argumento 1. Isto é, obviamente, não trivial, uma vez que existem funções parciais que são definidos para 1 e outros que estão indefinidas em 1. O problema da 1-parada é o problema de decidir de qualquer algoritmo se define uma função com essa propriedade, ou seja, se o algoritmo para na entrada 1. Pelo teorema de Rice, o problema 1-parada é indecidível.

Declaração formal

Temos $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ que é um número de Gödel de funções computáveis; uma mapara dos números naturais para a classe $\mathbf {P} ^{(1)}$ de funções computáveis (parcial) unárias. Denote por $\phi _{e}:=\phi (e)$ a $e$ º (parcial) função computável.

Identificamos cada propriedade que uma função computável pode ter com o subconjunto de $\mathbf {P} ^{(1)}$ consistindo das funções com essa propriedade. Assim, dado um conjunto $F\subseteq \mathbf {P} ^{(1)}$ , uma função computável $\phi _{e}$ e tem a propriedade F se e somente se $\phi _{e}\in F$ . Para cada propriedade $F\subseteq \mathbf {P} ^{(1)}$ há um problema de decisão $D_{F}$ associado a se determinar, dado e, se $\phi _{e}\in F$ .

Teorema de Rice afirma que o problema de decisão $D_{F}$ é decidível (também chamado de recursivo ou computáveis) se e somente se $F=\emptyset$ ou $F=\mathbf {P} ^{(1)}$ .

Exemplos

De acordo com o teorema de Rice, se houver pelo menos uma função computável em uma determinada classe C das funções computáveis e outra função computável que não está em C, então o problema de decidir se um determinado programa calcula uma função em C é indecidível. Por exemplo, o teorema de Rice mostra que cada um dos seguintes conjuntos de funções computáveis é indecidível:

A classe de funções computáveis que retornam 0 para cada entrada, e seu complemento.
A classe de funções computáveis que retornam 0 para pelo menos uma entrada, e seu complemento.
A classe de funções computáveis que são constantes, e seu complemento.

Prova pelo teorema recursivo de Kleene

Um corolário para o teorema recursivo de Kleene declara que para cada número de Gödel $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ de funções computáveis e cada função computável $Q(x,y)$ , há um índice $e$ tal que $\phi _{e}(y)$ retorna $Q(e,y)$ . (A seguir, diremos que $f(x)$ "retorna" $g(x)$ se qualquer $f(x)$ = $g(x)$ , ou ambos $f(x)$ e $g(x)$ são indefinidos.) Intuitivamente, $\phi _{e}$ e é um "quine", uma função que retorna o seu próprio código fonte (número de Gödel), exceto que ao invés de devolvê-lo diretamente, $\phi _{e}$ passa seu número de Gödel para Q e retorna o resultado.

Deixe $F$ ser um conjunto de funções computáveis tal que $\emptyset \neq F\neq \mathbf {P} ^{(1)}$ . Então existem funções computáveis $f\in F$ e $g\notin F$ . Suponha que o conjunto de índices $x$ tal que $\phi _{x}\in F$ é decidível; então, existe uma função $Q(x,y)$ que retorna $g(y)$ se $\phi _{x}\in F$ , $f(y)$ de outra forma.

Pelo corolário do teorema recursivo, existe um índice $e$ tal que $\phi _{e}(y)$ retorna $Q(e,y)$ . Mas se $\phi _{e}\in F$ , então $\phi _{e}$ é a mesma função que $g$ , e portanto $\phi _{e}\notin F$ ; e se $\phi _{e}\notin F$ , então $\phi _{e}$ é $f$ , e portanto $\phi _{e}\in F$ . Em ambos os casos, temos uma contradição.

Prova por redução ao problema da parada

Prova (esboço)

Suponha, por concretude, que temos um algoritmo para analisar um programa p e que seja possível determinar infalivelmente se p é uma implementação da função quadrática, que recebe como entrada um número inteiro d e retorna d². A prova funciona se temos um algoritmo para decidir qualquer outra propriedade não trivial de programas, e será dado, em geral, abaixo.

A alegação é que podemos converter nosso algoritmo para a identificação de programas quadráticos que identificam as funções que param. Vamos descrever um algoritmo que tem como entradas a e i e determina se o programa "a" para quando é alimentado com a entrada i.

O algoritmo é simples: vamos construir um novo programa t que (1) temporariamente ignora sua entrada, enquanto ele tenta executar o programa a sobre a entrada i, e então, se este para, (2) retorna o quadrado de sua entrada. Claramente, t é uma função para computação de números quadrados se e somente se a etapa (1) para. Desde que assumimos que podemos identificar infalivelmente programas deste tipo, podemos determinar se t é um programa desse tipo e, portanto, se o programa a para na entrada i. Note que não precisamos realmente executar t; só precisamos decidir se é um programa quadrático, e, por hipótese, sabemos como fazer isso.

 t(n) {
     a(i)
     return n×n
 }

Este método não depende especificamente de ser capaz de reconhecer as funções que computam quadrados; enquanto alguns programas podem fazer o que estamos tentando reconhecer, podemos adicionar uma chamada para a para obter o nosso t. Poderíamos ter um método para o reconhecimento de programas que computam raízes quadradas, ou programas para o cálculo da folha de pagamento mensal, ou programas que param quando é dada a entrada "Abraxas", ou programas que cometem erros de limites de matriz; em cada caso seríamos capazes para resolver o problema da parada da mesma forma.

Prova formal

Para a prova formal, os algoritmos são presumidos para definir funções parciais sobre strings e são representados por strings. A função parcial calculado pelo algoritmo representado por uma string a é denotada F_a. Este prova é por reductio ad absurdum (redução ao absurdo): vamos supor que existe uma propriedade não-trivial que é decidido por um algoritmo, e depois mostrar que podemos decidir o problema da parada, que não é possível, e, portanto, uma contradição.

Suponha que P(a) é um algoritmo que decide alguma propriedade não trivial de F_a. Sem perda de generalidade, podemos supor que P (não-para) = "não", com não-para pode ser a representação de um algoritmo que nunca para. Se isso não for verdade, então este irá realizar a negação da propriedade. Uma vez que P que decide uma propriedade não-trivial, segue-se que há uma string b que representa um algoritmo e P(b) = "sim". Podemos então definir um algoritmo H(a, i ) como segue:

1. construir uma string t que representa um algoritmo T(j) tal que

T primeiro simula o cálculo de F_a(i)
então T simula o cálculo de F_b(j) e retorna o seu resultado.

2. return P(t).

Agora podemos mostrar que H decide o problema da parada:

Suponha que o algoritmo representado por a para na entrada i. Neste caso F_t = F_b e, devido a P(b) = "sim" e a saída de P(x) depende apenas de F_x, segue-se que P(t) = "sim" e, portanto, H(a, i) = "sim".

Suponha que o algoritmo representado por a não para na entrada i. F_t = F_no-halt, ou seja, a função parcial que nunca é definida. Uma vez que P(não-para) = "não" e a saída de P(x) depende apenas de F_x, segue-se que P(t) = "não" e, portanto, H(a, i) = "não".

Uma vez que o problema da parada é conhecido por ser indecidível, esta é uma contradição e na suposição de que existe um algoritmo P(a) que decide uma propriedade não-trivial para a função representada por a deve ser falso.

Teorema de Rice e conjunto de índices

Teorema de Rice pode ser sucintamente expressos em termos de conjuntos de índices:

Temos que ${\mathcal {C}}$ seja uma classe das funções recursivas parciais com índice de conjunto $C$ . Então $C$ é recursivo se e somente se $C=\emptyset$ ou $C=\mathbb {N}$ .

onde $\mathbb {N}$ é o conjunto dos números naturais, incluindo o zero.

Uma analogia do Teorema de Rice para conjuntos recursivos

Podemos considerar o teorema de Rice como a afirmação da impossibilidade de efetivamente decidir para qualquer conjunto recursivamente enumerável se ele tem uma determinada propriedade não trivial^[1]. Nesta seção, damos um análogo ao teorema de Rice para conjuntos recursivos, em vez de conjuntos recursivamente enumeráveis^[2]. Em termos gerais, o análogo diz que se podemos efetivamente determinar para qualquer conjunto recursivo se ele tem uma certa propriedade, então, finitamente, muitos inteiros podem determinar se um conjunto recursivo tem a propriedade. Este resultado é análogo ao teorema original de Rice, pois ambos afirmam que a propriedade é "decidível" só se for possível determinar se um conjunto tem essa propriedade através da análise para no máximo um número finito i (para qualquer i, para o teorema original), se i pertence ao conjunto.

Suponha $W$ ser uma classe (chamada de jogo simples e pensado como uma propriedade) de conjuntos recursivos. Se $S$ é um conjunto recursivo, então para algum $e$ , uma função computável $\phi _{e}$ é a função característica de $S$ . Chamamos $e$ como um índice de característica de $S$ . (Há um número infinito de tais $e$ .) Vamos dizer que a classe $W$ é computável se existe um algoritmo (função computável) que decide para qualquer inteiro não negativo $e$ (não necessariamente um índice de característica),

se $e$ é um índice característico de um conjunto recursivo pertencente a $W$ , então o algoritmo dá "sim";
se $e$ é um índice característico de um conjunto recursivo não pertencente a $W$ , então o algoritmo dá "não";

Um conjunto $S\subseteq \mathbb {N}$ estende uma string $\tau$ de 0's e 1's, se para qualquer $k<|\tau |$ (o comprimento de $\tau$ ), o $k$ th elemento de $\tau$ é 1 se $k\in S$ ; é 0 caso contrário. Por exemplo, $S=\{1,3,4,7,\ldots \}$ estende a string 01011001. Uma string $\tau$ é vencedor na determinação se qualquer conjunto recursivo estendendo $\tau$ pertence a $W$ . Uma seqüência $\tau$ é perdedor na determinação se nenhum conjunto recursivo estendendo $\tau$ pertence a $W$ .

Nós podemos agora enunciar o seguinte teorema análogo de Rice (Kreisel, Lacombe e Shoenfield de 1959^[3], Kumabe e Mihara, 2008^[4])):

Uma classe $W$ de conjuntos recursivos é computável se e somente se houver um conjunto recursivamente enumerável $T_{0}$ de perdedores na determinação de strings e um conjunto recursivamente enumerável $T_{1}$ de vencedores na determinação de strings, de tal forma que qualquer conjunto recursivo estende uma string em $T_{0}\cup T_{1}$ .

Este resultado tem sido aplicado a problemas fundamentais na escolha social computacional (de forma mais ampla, a teoria algorítmica dos jogos). Por exemplo, Kumabe e Mihara (2008^[4], 2008^[5]) aplicam este resultado em uma investigação aos números Nakamura para jogos simples na teoria dos jogos cooperativos e teoria da escolha social.

Notas

↑ Um conjunto $S\subseteq \mathbb {N}$ é recursivamente enumerável se $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ para algum $e$ , onde $W_{e}$ é o domínio ${\textrm {dom}}\,\phi _{e}$ (o conjunto de entradas $x$ tais que $\phi _{e}(x)$ é definido) de $\phi _{e}$ . O resultado para conjuntos recursivamente enumeráveis pode ser obtido a partir de funções computáveis, considerando a classe $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ , onde $C$ é a classe dos conjuntos recursivamente enumeráveis.
↑ Um conjunto recursivamente enumerável $S\subseteq \mathbb {N}$ é um conjunto recursivo se o seu complemento é recursivamente enumerável. Equivalentemente, $S$ é recursivo se sua função característica é computável.
↑ Kreisel, G., Lacombe, D., Shoenﬁeld, J.R., 1959. Partial recursive functionals and effective operations. In: Heyting, A. (Ed.), Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, pp. 290–297.
↑ ^a ^b Kumabe, Masahiro; H. Reiju (1 de fevereiro de 2008). «Computability of simple games: A characterization and application to the core». Journal of Mathematical Economics. 44 (3–4): 348-366. doi:10.1016/j.jmateco.2007.05.012
↑ Kumabe, Masahiro; H. Reiju (11 de março de 2008). «The Nakamura numbers for computable simple games». Social Choice and Welfare (em inglês). 31 (4): 621-640. ISSN 0176-1714. doi:10.1007/s00355-008-0300-5