Parar problema para máquinas de turing com uma entrada

Question

A minha pergunta é:

Há uma construção simples semelhante ao de Turing é 'mentiroso' programa que mostra que máquinas de Turing, além de um deter a oracle não é possível decidir se uma determinada máquina de Turing pára em todas as entradas.

Quando eu falar sobre o mentiroso programa que eu estou me referindo ao padrão a prova de que uma máquina de Turing não pode determinar a suspensão de todas as outras máquinas de Turing, uma vez que a análise de cada caso a seguir, leva a contradições

def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

Eu posso ver que ter um Interrompendo a oracle iria me permitir determinar se uma máquina de Turing pára em qualquer conjunto finito de entradas (que seria apenas executar tudo em ordem).

Se chamamos regular máquinas de Turing nível 0, podemos chamar de máquinas de Turing plus a suspensão oracle nível 1.Eu tenho visto que a prova usando o Mentiroso programa funciona mesmo para mostrar que o nível 1 máquinas têm as suas próprias Parar problema que é indecidíveis para eles.

Answer 1

O que você chama de "mentiroso" o programa é normalmente chamado de um diagonalization argumento, pois, de alguma forma, se assemelha Cantor do diagonalization argumento.

Normalmente o que nós queremos dizer é que, se tentarmos enumerar todos os elementos com uma determinada propriedade, então podemos apontar, por construção, um elemento que é, necessariamente, "incorreto", e podemos fazê-lo, mostrando que ele não satisfaz a propriedade com relação a si mesmo (isto é completamente mão-ondulado, mas se você viu o argumento, você vai espero que entenda o que quero dizer).

Agora, o que você está perguntando é se podemos fazer o mesmo para mostrar que ALL_TM (TM universalidade) não é decidível por uma TM com a oracle para HALT_TM.

Bem, não realmente.Pelo menos não de uma forma natural:o argumento teria que partem do pressuposto de que existe um oracle máquina M que decide ALL_TM e, em seguida, construir a partir de M alguma outra máquina N (o que você chama de "mentiroso" máquina), o que geraria uma contradição quando corremos N em N.No entanto, a máquina N teria que ser um oracle máquina, não há um padrão TM (ou seria, essencialmente, perder o poder da oracle em M).Mas desde que a oracle no N tem como entrada padrão TMs, em seguida, a operação interna de N, de alguma forma, precisamos criar um padrão TM de alimentação para o oráculo.Este não parece ser uma construção natural, e ele certamente não seria simples.

Agora, talvez, há alguns complicada forma de dar um direto diagonalization argumento para esta afirmação, mas não é bem motivado, dado que comprovem a reclamação diretamente (ou seja, que ALL_TM não é decidível por uma TM com a oracle para DETER) não é difícil usando ferramentas padrão, tais como reduções.