O que sabemos sobre versões restritas do problema de parada

( ATUALIZAÇÃO : uma pergunta melhor formada é colocada aqui, pois os comentários para a resposta aceita abaixo mostram que essa pergunta não está bem definida)

A prova clássica da impossibilidade do problema de parada depende de demonstrar uma contradição ao tentar aplicar o algoritmo de detecção de parada a si próprio como entrada. Veja o plano de fundo abaixo para obter mais informações.

A contradição demonstrada se aplica devido a um paradoxo auto-referencial (como a frase "Esta frase não é verdadeira"). Mas se proibimos estritamente essas auto-referências (isto é, aceitamos o fato de que essas auto-referências não podem ser interrompidas), que resultado nos resta? O problema de parada para o conjunto restante de máquinas sem auto-referência pode ser interrompido ou não?

As perguntas são:

Se considerarmos um subconjunto de todas as máquinas de Turing possíveis, que não são auto-referenciadas (ou seja, não se consideram entradas), o que sabemos sobre o problema de interrupção desse subconjunto?

ATUALIZAR

Talvez uma melhor reformulação do que eu busco seja uma melhor compreensão do que define um conjunto decidível. Eu estava tentando isolar a prova clássica de indecidibilidade porque ela não adiciona nenhuma informação sobre a indecidibilidade, exceto nos casos em que você executa o HALT em si.

Antecedentes: Supondo que haja uma contradição de que existe uma máquina de Turing que pode decidir sobre a entrada que é uma codificação para uma máquina de Turing e , independentemente de parar. Em seguida, considere uma máquina de Turing que pega e e usa para decidir se pára ou não, e então faz o oposto, ou seja, pára se não parar e não parar se pára. Então demonstra uma contradição, pois $Q$ $M$ $X$ $M(X)$ $K$ $M$ $X$ $Q$ $M(X)$ $K$ $M(X)$ $M(X)$ $K(K)$ $K$ deve parar se não parar e não parar quando parar.

Motivação: um colega está trabalhando na verificação formal de sistemas de software (especialmente quando o sistema já está comprovado no nível do código-fonte e queremos reprová-lo por sua versão compilada, para neutralizar problemas do compilador) e, no caso dele, ele se preocupa com uma conjunto especial de programas de controle incorporados para os quais sabemos com certeza que não seriam auto-referenciados. Um aspecto da verificação que ele deseja executar é se é garantido que o programa compilado será interrompido se o código-fonte de entrada terminar.

ATUALIZAR

Com base nos comentários abaixo, esclareço o significado de máquinas de Turing sem auto-referência.

O objetivo é defini-lo como o conjunto que não leva à contradição colocada na prova (cf. "Antecedentes" acima). Pode ser definido da seguinte maneira:

Supondo que exista uma máquina de Turing que decida o problema de parada para um conjunto de máquinas de Turing , então não fará referência própria a se excluir todas as máquinas que invocam em (direta ou indiretamente). (Claramente, isso significa que não pode ser um membro de ) $Q$ $S$ $S$ $Q$ $Q$ $S$ $Q$ $S$

Para esclarecer sobre o que significa chamar em indiretamente: $Q$ $S$

A chamada de em é indicada por uma máquina de Turing com um conjunto de estados e algumas possíveis entradas iniciais possíveis na fita (correspondendo a qualquer membro de ), com a cabeça inicialmente no início dessa entrada. Uma máquina chama em "indiretamente" se houver uma sequência (finita) de etapas que levaria para tornar sua configuração "homomórfica" à configuração inicial de . $Q$ $S$ $Q$ $S$ $W$ $Q$ $S$ $W$ $Q(S)$

ATUALIZAÇÃO 2

A partir de uma resposta abaixo, argumentando que existem infinitas máquinas de Turing executando a mesma tarefa e, portanto, não é único, alteramos a definição acima dizendo que não é uma única máquina de Turing, mas o conjunto (infinito) de todas as máquinas que computam a mesma função (HALT), em que HALT é a função que decide o que uma máquina de Turing para em uma entrada específica. $Q$ $Q$

ATUALIZAÇÃO 3

A definição de homomorfismo da Máquina de Turing:

A TM A é homomórfica a TM B se o gráfico de transição de A for homomórfico ao de B, no sentido padrão de homomorfismos de gráficos com nós E arestas marcados. Um gráfico de transição (V, E) de uma TM é tal que V = estados, E = transição arcos entre estados. Cada arco é rotulado com o símbolo (S, W, D), S = lido na fita e W = o símbolo a ser gravado nela, e D = a direção em que a cabeça é exibida.

computability lo.logic M. Alaggan
fonte

"o conjunto restante de não-auto-referência" Antes que eu possa discutir com sensibilidade esse conjunto, gostaria de uma definição de "auto-referência". No entanto, acho que será algo complicado de definir?

Sam Nead 9/11/10

Existem estudos de programas de interrupção comprovadamente (embora essa classe não inclua todos os programas de interrupção). Basicamente, eles são um par de um programa e uma prova de que ele para. Por exemplo, se não me engano, o Agda permite apenas programas que são interrompidos. Eu acho que as pessoas que trabalham com lógica e linguagens de programação têm mais a dizer sobre isso.

Tsuyoshi Ito

@M. Alaggan. Agora eu quero uma definição de "invoca

indiretamente", que eu suspeito de ser tão difícil de definir como o original "auto-referência" :)

Q

$Q$

S

$S$

Rob Simmons

Isso levanta uma questão interessante: todas as provas de incomputabilidade (indecidibilidade) são rastreáveis ao método de diagonalização de Cantor? Existe alguma prova de indecidibilidade que não dependa direta ou indiretamente do método de diagonalização?

Mohammad Al-Turkistany

Questões possivelmente relacionadas: existe um análogo da teoria da complexidade do teorema dos arrozes na teoria da computabilidade? , MO: perfeição, problemas mais difíceis .

Kaveh

Respostas:

Acho que vai demorar um pouco mais de trabalho para chegar a uma pergunta "bem definida". Em particular, isso é problemático:

A chamada de Q em S é indicada por uma máquina de Turing Q com um conjunto de estados e algumas possíveis entradas iniciais possíveis na fita (correspondendo a qualquer membro de S), com a cabeça inicialmente no início dessa entrada. Uma máquina W chama Q em S "indiretamente" se houver uma sequência (finita) de etapas que W levaria para tornar sua configuração "homomórfica" à configuração inicial de Q (S).

Um problema é que existem infinitas máquinas de Turing que calculam a mesma função. No argumento da diagonalização padrão, posso apenas substituir a sub-rotina Q por outra decisão para o HALT, já que existem infinitamente muitas delas. Ou uma função que é computávelmente equivalente a HALT. Portanto, não está totalmente claro para mim como definir sua noção de "invocação indireta".

Uma pergunta diferente pode ser: para quais conjuntos de máquinas de Turing o problema de parada é decidível? Aqui há uma abundância de respostas: TMs restritas a recursos (por exemplo, use apenas espaço f (n), onde f é alguma função computável específica), TMs que são operacionalmente restritas de alguma maneira específica (por exemplo, a cabeça de leitura se move apenas em uma direção), etc. Outra questão interessante é se a participação nesse conjunto restrito é decidível ou se você deve se restringir a "prometer problemas", onde você garante apenas uma resposta correta em alguns subconjuntos "prometidos" de entradas, mas não verifica Filiação.

Mark Reitblatt
fonte

Q

$Q$

H

$H$

Não é tão simples assim. Sua definição é paradoxal agora, pois você está procurando um HALT computável. Mas se isso é computável, qualquer função computável é equivalente a ela. Mas se o seu conjunto de entradas contiver problemas semi-computáveis (TMs), você terá uma contradição, pois a decisão do problema de interrupção de tal TM forneceria um procedimento de decisão para esse problema.

1) Um HALT incontestável não significa indecidibilidade? Eu estava assumindo que um HALT computável existe, esperando por contradição. 2) Não estou familiarizado com o conceito de que todas as funções computáveis são computáveis equivalentes umas às outras, eu estava citando você, e significa que é uma função que resolve o problema HALT. Aparentemente, λx.1 é computável, mas não decide HALT. Corrija-me se eu estiver errado, por favor. Sobre os problemas semi-computáveis, o HALT pode executar um número infinito de etapas, o que ainda não levaria a uma contradição na prova original de que o HALT não é decidível.

M. Alaggan

1) Certo. Mas o problema está tentando definir sua noção de "não-auto-referência". Ou é uma restrição fraca, que permite a diagonalização como argumentei, ou é uma restrição forte que elimina tudo. 2) é simples. "Computável equivalente" significa aproximadamente que existe um mapeamento computável de um para o outro que preserva as respostas. Mas se eu puder calcular uma resposta, posso trapacear e tornar o mapeamento trivial. 3) Se o TM que decide a HALT não terminar por si só, não é uma decisão da HALT.

Outra coisa um pouco confusa é a fusão da MT com o problema de decisão calculado por eles. Não é normal falar que uma MT é equivalente computacionalmente uma à outra. Em vez disso, as funções calculadas por eles podem ser equivalentes (ou iguais). O problema é que tentar dizer que uma MT não simula outra é difícil de definir em geral, sem dar algo concreto para separar as funções calculadas por elas. Por exemplo, um Log-space TM não pode simular um TM resolvendo um problema de espaço EXP.

Se entendi sua motivação corretamente, parece que esse é um problema de "correção do compilador" mais do que um problema de "problema de parada restrita". Você tem uma propriedade (terminação) que você provou para algum programa Prog de nível de origem que deseja estender ao código compilado para obter a mesma propriedade de compilado (Prog) . Mas o compilador pode (em geral) executar coisas arbitrariamente ridículas, como implementar um tempo de execução completo (por exemplo, a JVM), compilar seu programa final em um bytecode da JVM e depois despejar um executável que inicia a JVM e o alimenta como seu bytecode compilado.

Na prática , provavelmente é bem possível utilizar o conhecimento implícito que você possui sobre como o seu compilador trabalha para implementar algum procedimento de verificação que prova que os programas compilados estão corretos, dados os programas de origem corretos (de fato, muitas ferramentas de verificação automática para programas estão utilizando conhecimento implícito do "compilador" de algoritmo para código no cérebro dos programadores). No entanto, em geral, você provavelmente está procurando um problema de correção do compilador. Pelo que entendi, existem duas maneiras clássicas de fazer isso.

Uma opção é ter um compilador que tome como entrada o programa Prog e a prova termine (Prog) e saia compilado (Prog) e termine (compilado (Prog)) - a última é uma prova que pode ser verificada duas vezes independentemente de o compilador. O artigo clássico sobre isso é Necula e Lee . Acredito que seja o design e a implementação de um compilador de certificação .

Como alternativa, você pode provar um fato sobre a função compiles () - que sempre que compiles () está fornecendo uma entrada final, ela produz uma saída final. Uma introdução acessível a essa maneira de pensar sobre a correção do compilador é o artigo CACM de Xavier Leroy, Verificação formal de um compilador realista .

(PS: Espero que esta resposta seja útil - reconheço que é um pouco divergente da pergunta que você fez, então, deixe-me saber se estou muito fora da base e / ou repetindo algo que você já sabe.)

Rob Simmons
fonte

Obrigado pela ótima resposta. Isso seria definitivamente útil para o meu colega. No entanto, eu (independentemente do meu colega) estou mais interessado nas implicações teóricas na prova do problema de parada, que, se nos livramos do caso que mostrava a contradição, o que mais sabemos sobre a decidibilidade do problema de parada?

M. Alaggan