Implicações do teorema de Rice

8

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 .eu={f:NN|f é uma função computável e total}eueu

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.ΣPΣ|P|=|N|Ppumaeu={WΣ|W é um palíndromo}pPpumaeu|Ppumaeu|=|eu|

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.EusPumaeuEundrome(W)EusPumaeuEundrome(W)EusTotumaeu(W)eu

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.

Stefan Lutz
fonte
2
De todos os seus comentários, parece-me que você realmente não entende o que é computabilidade. Verifique a definição de computabilidade; certifique-se de entender o que é uma máquina universal de Turing e como ela funciona; certifique-se de entender os pontos finos das enumerações, em particular as enumerações Gödel (com a propriedade smn!). O teorema de Rice é muito simples quando o básico é entendido, mas tem poucas implicações ... o que você está tentando fazer, é o meu pressentimento.
Raphael

Respostas:

6

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 palindromw, que o mapeamento associa a uma função fw não há como você usar esse mapeamento para obter o resultado da aplicação fWa 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.

babou
fonte
Isso faz sentido. Isso significa que o teorema de Rice não é aplicável a linguagens com semântica não computável ou são linguagens com semântica não computável um conceito geralmente "proibido" (no sentido de que os resultados da teoria da computabilidade geralmente não são aplicáveis ​​a eles)?
Stefan Lutz
11
Semântica não computável é uma expressão que inventei na intuição. A semântica é geralmente definida como um mapeamento da sintaxe (leia o número de Gödel) para algum domínio de valor (leia a função computável). Minha expressão é um pouco de oxímoro, porque uma numeração de Gödel deve ser definida para que as funções associadas possam ser computadas. Eu estava tentando dar uma intuição ao que você estava fazendo, o que na verdade era uma coisa errada a se fazer. Mas você deve se abster de usar esse "conceito". Sim: tome-o como um conceito proibido, pelo motivo que você declara.
babou
Talvez haja outro mal-entendido da minha parte aqui, mas se eu considerar a semântica uma composição de duas funções, o primeiro programa de mapeamento -> número de gödel e o segundo número de gödel -> função computável como você a descreveu, então a numeração de gödel poderia facilmente seguir sua definição, mas o primeiro mapeamento seria computável se tivermos "semântica computacional". Ainda pode ser um conceito inútil, mas não há problema em defini-lo, ou existe?
Stefan Lutz
Não tenho certeza de como responder. Sua construção me deixa desconfortável. Para mim, a sintaxe do programa em algum idioma é o número de Gödel. Acabei de ler o texto como um grande número em algum sistema de numeração em que todos os meus caracteres são considerados dígitos. Portanto, considero um único mapeamento. Por outro lado, se você me der uma enumeração de funções, li o número como algum tipo de representação sintática. Eu apenas tento evitar fazer a diferença. Agora, você pode introduzir mapeamentos bijetivos intermediários (computáveis) de N para N, e isso não mudará muito.
Babou 01/03/2015
"Acabei de ler o texto como um número grande em algum sistema de numeração em que todos os meus caracteres são considerados dígitos" - você pega o programa como uma string como entrada e como um número, onde cada programa corresponde exatamente a um número ( = bijeção). Além disso, você declara "algum esquema de numeração"; portanto, não importa realmente como exatamente essa codificação funciona, desde que seja computável, não é? Desculpe por ser tão persistente, mas eu realmente quero entender isso.
Stefan Lutz
2

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 .

Rafael
fonte
11
"Uma nova linguagem de programação é uma nova numeração de alguns programas." - se eu considerar uma linguagem completa, isso não significa que ele contém todas as funções computáveis? De qualquer forma, acho que meu mal-entendido era que as numerações de Gödel não teriam que ser computáveis.
Stefan Lutz
@Skrjiban Toda linguagem de programação adequada é uma enumeração Gödel. (Para ser claro, as numerações de Gödel são parcialmente computáveis ​​por necessidade.)
Raphael
2

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.

Andrea Asperti
fonte
1

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 TuringM, 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 deD para Σ) é 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.

Stefan Lutz
fonte
11
Não é tão parecido com o que expliquei nos últimos dois comentários que lhe enviei. Afirmei que é a tese da CT que fornece a definição de computabilidade e, portanto, a pedra fundamental do resto, embora improvável. Eu estava esperando que você respondesse a esses comentários. - - - - - - Outro ponto é que não vejo como isso pode ser uma resposta para sua pergunta. Sua pergunta foi sobre um erro no seu raciocínio e você não foi a pessoa que encontrou esse erro.
babou
Lamento se o ofendi, seus comentários foram claramente úteis! Eu queria responder que a existência de um compilador computável da linguagemeu para eu deve ser equivalente à existência de um intérprete computável para eu, o que me fez pensar sobre o que seria um intérprete "computável", o que me fez pensar em como uma numeração de gödel poderia ser "computável", o que me levou ao artigo acima. Se isso já era o que você quis dizer, eu aparentemente não consegui ver.
27515 Stefan Lutz
Mas você está certo, é o que tornou claramente compreensível para mim, mas não responde à pergunta inicial. Marcarei sua resposta como aceita.
Stefan Lutz
Bem, você agradeceu a mim e Raphael. Mas a maneira de agradecer às pessoas aqui é votar nelas ou aceitar sua resposta. A menos que você tenha uma resposta muito melhor à pergunta original, você deve demonstrar apreço pelas contribuições positivas. Pelo menos esse é o meu entendimento. Pessoalmente, nunca voto negativo nas pessoas como protesto a muitas pessoas incompetentes que votam descuidadamente. Ciência é diálogo, não voto. Quanto à definição de computável, observe os comentários que eu enviei. O próprio conceito é estranho porque definido pela Tese de Church-Turing. Boa sorte.
babou 3/03/2015