O problema de parada limitada é decidível. Por que isso não entra em conflito com o teorema de Rice?

9

Uma declaração do teorema de Rice é apresentada na página 35 de "Complexidade computacional: uma abordagem moderna" (Arora-Barak):

Uma função parcial a partir de {0 0,1 1} a {0 0,1 1} é uma função que não está necessariamente definido em todas as suas entradas. Dizemos que um TM M calcula uma função parcial f se para cada x em que f está definido, M(x)=f(x) e para cada x em que f não está definido entra em um loop infinito quando executado na entrada . Sex S f S α M α SMxSé um conjunto de funções parciais, definimos ser a função booleana que na entrada saídas 1 sse calcula uma função parcial em . O teorema de Rice diz que, para todo S não trivial , a função f SfSαMαSSfS não é computável.

A Wikipedia afirma que os idiomas das máquinas com limite temporal são EXPTIME completos. Espero que esse idioma se pareça com {(α,x,n):Mα aceita em menos de etapas . Portanto, seja um DTM que decida esse idioma limitado em tempo exponencial. Parece que este DTM está decidindo alguma propriedade para TODAS as máquinas de turing, então minha intuição me diz que o teorema de Rice impede essa decisão. Mas obviamenten } M Mxn}MM calcula uma função total.

O que estou perdendo na relação entre essa linguagem e o teorema de Rice?

ttbo
fonte

Respostas:

13

O idioma

{(α,x,n):Mα aceita x é menos que n passos}

não é um conjunto de índices, ou seja, não é da forma

euP={MM é TM, fP. fM=f}

para um conjunto de (recursivas parcial) funções , com f M a função (parcial) calculado por TM M . Teorema de Rice faz declarações única sobre tais L P ; muitas reformulações "intuitivas" não são úteis. Veja também aqui .PfMMeuP

Observe que este não é apenas um detalhe técnico aqui. O teorema de Rice não se aplica a

,eu={MM aceita M é menos que M passos}

ou. Você pode ver o porquê?

Para cada máquina em você pode facilmente construir muitas máquinas que aceitam a mesma língua, mas são executados por mais de M passos, e, portanto, não estão em L . Portanto, L não é um conjunto de índices.euMeueu

é decidível, usando o mesmo argumento do idioma original que estamos discutindo.eu

Rafael
fonte
+1. Especialmente para o hiperlink que provavelmente se aplica aqui também. No entanto, tentei contribuir com uma análise "intuitiva" como uma resposta alternativa de qualquer maneira.
Jirka Hanika
6

O teorema de Rice diz que você não pode dizer nada sobre o comportamento final de um programa quando ele é executado para o infinito - não importa como você classifique os programas, haverá dois programas que convergirão para o mesmo comportamento final (função computada ), embora você os tenha classificado de maneira diferente.

Mas deixar os programas rodarem até o infinito é essencial. Para descobrir o que eles fazem nos primeiros passos, você pode apenas simulá-los nos primeiros n passos e então terminar dando o seu veredicto sobre o comportamento do programa. Simulação semelhante até o infinito não funcionar, porque se o programa simulado nunca terminar em uma entrada simulada, seu classificador também divergirá, em vez de fornecer uma classificação.nn

Jirka Hanika
fonte
5

Primeiro, as palavras no seu idioma não são codificações de máquinas, elas contêm mais informações, portanto você não pode aplicar diretamente o teorema de Rice. Dito isto, o teorema de Rice fala sobre a impossibilidade de raciocinar sobre a função calculada por uma máquina de Turing (a saber, se está em algum conjunto ). Este não é o caso aqui, pois, como Raphael mencionou, existem duas máquinas M , M que computam a mesma função, mas uma está no seu idioma e a outra não (aqui estou ignorando a questão sintática, e esqueci o fato de que x , nSM,Mx,nfazem parte da entrada). O ponto é que a propriedade que você está vendo aqui é mecânica e não semântica (as máquinas podem calcular a mesma função, mas de uma maneira diferente).

Ariel
fonte
O primeiro argumento é formalista, mas correto. O segundo argumento me confunde (não tenho certeza de que poderia definir rigorosamente localidade / globalidade; e não sei o que significa calcular uma função "a partir de um conjunto de funções").
Jirka Hanika
O primeiro argumento é de fato meramente sintático, como Raphael mencionou em sua resposta. A questão local / global foi feita para indicar a diferença entre raciocinar sobre o resultado de uma única entrada e todas as entradas (eu não quis dizer isso em sentido formal, pode significar algo mais em um contexto diferente). Calculando uma função a partir de um determinado conjunto significa simplesmente que você perguntar se a função computada por está em S . MαS
Ariel #
O teorema de Rice NÃO exige que se raciocine sobre o comportamento da máquina em todas as entradas. Por exemplo, é impossível classificar programas com base no fato de eles aceitarem quando executados na entrada "5". Ou melhor, você pode definir uma classificação que ignore o comportamento da maioria das entradas, mas a classificação ainda não é recursiva.
Jirka Hanika
Isso foi realmente confuso, já que é possível definir como o conjunto de funções que emitem 1 em alguma entrada fixa. Obrigado por levantar a questão. S1 1
Ariel #
3

O teorema de Rice diz que, para qualquer conjunto não trivial de linguagens , o conjunto de máquinas de Turing que reconhecem uma linguagem em  L é indecidível. A Wikipedia diz que um idioma específico é decidível. Portanto, não há contradição.eueu

David Richerby
fonte