Implicações do teorema de Rice

Toda vez que acho que entendo o que o teorema de Rice significa, encontro um contra-exemplo para me confundir. Talvez alguém possa me dizer onde estou pensando errado.

Vamos usar uma propriedade não trivial do conjunto de funções computáveis, por exemplo, deixe . Obviamente, é infinito contável e há também um número infinito contável de funções computáveis não em .$L = \{ f : \mathbb{N} \to \mathbb{N} \;|\; \text{f is a computable and total function} \}$$L$$L$

Agora vamos considerar uma linguagem de programação completa sobre um conjunto finito de instruções e o conjunto de programas sintaticamente corretos , com. Se eu puder escolher a semântica da minha linguagem como quiser, também posso numerar os programas como quiser e, portanto, deve ser possível projetar uma linguagem de programação em que algum subconjunto dos programas calcule exatamente algum subconjunto arbitrário das funções computáveis, como desde que a cardinalidade corresponda. Por exemplo, deixe , e cada programa calcula uma função total. Desde, esse idioma deve existir.$\Sigma$$P \subseteq \Sigma^*$$|P| = |\mathbb{N}|$$P_{pal} = \{ w \in \Sigma^* \;|\; w\text{ is a palindrome} \}$$p \in P_{pal}$$|P_{pal}| = |L|$

No entanto, é obviamente computável em turing e, como , teríamos um programa que decide a propriedade não trivial , o que não é possível de acordo com o teorema de Rice.$isPalindrome(w)$$isPalindrome(w) \iff isTotal(w)$$L$

Onde está o erro na minha dedução? Isso significa que não há linguagem de programação em que cada programa palindrômico (ou melhor, de qualquer estrutura computável) calcule exatamente as funções totais (ou melhor, qualquer conjunto de funções computáveis)? Isso realmente me deixa perplexo.

O que você esquece é que todos os mapeamentos que você usa precisam ser computáveis. Quando você declara que as cardinalidades correspondentes garantem a existência de um mapeamento, isso pode ser verdade, mas é improvável que o mapeamento seja computável, precisamente porque isso permitiria uma contradição com o teorema de Rice. Na computabilidade (pelo menos pelo que sei), tudo é finito ou infinitamente contável. Portanto, a existência de mapeamentos geralmente não é um problema. O problema é se é computável.

Em outras palavras, certamente existe um mapeamento (na verdade incontáveis ​​muitos) que associa precisamente palavras palindrômicas às funções computáveis ​​totais. Mas, dado esse palindrom$w$, que o mapeamento associa a uma função $f_w$ não há como você usar esse mapeamento para obter o resultado da aplicação $f_w$a algum argumento. Seu mapeamento não fornece nenhuma maneira de identificar a função ou computar com ela. Seu idioma possui semântica não computável.

Também posso numerar os programas como quiser e, portanto, deve ser possível projetar uma linguagem de programação em que algum subconjunto dos programas calcule exatamente algum subconjunto arbitrário das funções computáveis, desde que a cardinalidade corresponda.

Para alguns conjuntos de funções, isso funciona; não para os outros . Mas uma nova linguagem de programação é uma nova numeração de alguns programas, e não é sobre isso que o teorema de Rice fala.

Para o propósito do teorema de Rice, consideramos apenas as enumerações de Gödel de todas as funções recursivas parciais e, em seguida, ele afirma apenas algo sobre conjuntos de índices , ou seja, conjuntos de todos os índices nessa enumeração de funções no conjunto fornecido.

Isso não cobre todos os conjuntos de índices; e isso é bom, porque certamente existem muitas propriedades decidíveis dos programas. Veja também aqui .

Nem toda enumeração de programas é "aceitável", pois nem toda enumeração permitiria calcular efetivamente a função associada ao programa a partir do índice do programa. Em outras palavras, você não teria máquinas universais (propriedade utm). A segunda propriedade geralmente necessária para "aceitar" a enumeração é a propriedade smn: você precisa poder calcular o índice de instâncias de programa de maneira uniforme e eficaz.

É possível provar (teorema da equivalência de Roger) que qualquer par de enumerações que usufruem utm e smn é recursivamente isomórfico, ou seja, você tem uma maneira eficaz de traduzir programas entre as duas enumerações. Isso torna sua teoria independente de enumeração.

Isso já é suficiente para enfatizar a relevância de utm e smn, os dois teoremas básicos da abordagem "abstrata" da computabilidade.

O teorema de Roger é apresentado como um exercício (sic!) Em seu livro Teoria das funções recursivas e computabilidade efetiva (exercício 2-10, p. 41). Mas a prova não é muito difícil, de fato.

Encontrei este interessante artigo de Udi Boker e Nachum Dershowitz, que aborda o problema que tive, entre outras coisas. Na introdução, eles afirmam que (ênfase minha)

O que se quer dizer com dizer que "$f$é computável ”? Um provavelmente significa que existe uma máquina de Turing$M$, de tal modo que $M$ calcula $f$, usando alguma representação de sequência do domínio $D$. Mas quais são as representações de string permitidas? Obviamente, permitir uma representação arbitrária (qualquer injeção de$D$ para $\Sigma^*$) é problemático - tornará qualquer função de decisão “computável”. Por exemplo, ao permutar o domínio dos códigos de máquina, a função de parada pode se transformar na função de paridade simples [...]

e mais

Outra abordagem é permitir apenas representações "naturais" ou "eficazes". No entanto, no contexto da definição da computabilidade, é necessário recorrer a uma noção vaga e indefinida de "naturalidade" ou "efetividade", derrotando assim o próprio objetivo de caracterizar a computabilidade.

o que explica o que babou chama de "semântica computável". O artigo também contém esta citação de Michael Rescorla:

Sugerirei que as supostas análises conceituais envolvendo a tese de Church geram uma circularidade sutil, mas ineliminável: elas caracterizam a noção intuitiva de computabilidade, invocando a noção intuitiva de computabilidade [...] Damos à sintaxe uma semântica primitiva. Eu afirmo que [...] devemos exigir que a correlação semântica entre entidades sintáticas e entidades não sintáticas seja computável. Mas a análise proposta não ilumina a computabilidade de maneira não circular.

Portanto, de acordo com os autores, a definição formal comum de uma função computável depende da intuição informal sobre o que significa computabilidade, o que explica o que me intrigou nas numerações de gödel.