O conjunto de máquinas de Turing que para em no máximo 50 etapas em todas as entradas é decidível?

19

Deixe . Preciso decidir se F é decidível ou recursivamente enumerável. Eu acho que é decidível, mas não sei como provar.F={M:M é uma TM que para para cada entrada em no máximo 50 etapas}

Meus pensamentos

Esta parte dos "50 passos" imediatamente transforma o sinal R para mim. Se fosse para informações específicas, seria decidível. No entanto, aqui está para cada entrada. Verificá-lo para infinitas entradas me faz pensar que o problema é co-RE , ou seja , seu complemento é aceitável.

Talvez eu possa verificar as configurações e ver que todas as configurações após 50 etapas não levam ao estado de aceitação - como faço isso?

Jozef
fonte

Respostas:

21

NN1

Como swegi observa em uma resposta anterior, se a máquina parar após no máximo etapas, somente as células na fita são significativas. Basta simular a máquina em todas as seqüências de entrada do formato , das quais existe um número finito.N0 0,1,...,N-1MxΣN

  • Se alguma dessas simulações falhar em entrar em um estado de parada pelotransição, isso indica que qualquer sequência de entrada começando com é aquela para a qual a máquina não para nas primeiras etapas.NºxN
  • Se todas essas simulações forem interrompidas pelotransição, então pára dentro de etapas em todas as entradas de qualquer comprimento (das quais a subcadeia de comprimento é tudo em que atua).NºN NMNN
Niel de Beaudrap
fonte
E- Suponho que tal forma que seu comprimento seja maior que N seja automaticamente rejeitado? xN
Jozef
Por que ele não pode ir além da célula N dentro das N etapas da computação?
Jozef
@Jozef: as simulações apenas percorrer todos cadeias de entrada possíveis de comprimento N . Você pode percorrer mais strings, mas não aprenderá mais nada, porque apenas os primeiros N símbolos são importantes. A razão pela qual ela não pode ir além das N células é porque as máquinas de Turing (ou a definição padrão delas de qualquer maneira) movem apenas uma célula por etapa.
Niel de Beaudrap 9/08/12
Certo, entendi. assim, você se importa apenas com os primeiros N símbolos de cada palavra e, assim, verifica todas as combinações delas. por que você excluiu a descrição das configurações?
Jozef
Ainda está visível se você olhar as edições anteriores. I revisto para isso porque, enquanto a outra resposta foi talvez interessante, muito do que fez "interessante" só serviu para obscurecer o fato de que o procedimento de decisão não é mais nem menos do que simula em todas as entradas possíveis de comprimento N . Achei melhor revisar a resposta para algo muito mais direto e que basicamente chegou à raiz do que torna o problema decidível. MN
Niel de Beaudrap 9/08/12
4

Se parar em não mais que 50 passos, as posições que M pode alcançar na fita normalmente infinita são limitadas. Assim, a fita infinita pode ser simulada por uma fita finita. Isso significa que a fita pode ser simulada por um autômato finito. Daqui resulta que uma máquina de turing M que para em não mais do que 50 etapas é bimimilar de algum autômato finito M ' .MMMM

Seja o conjunto de estados de M , F Q o conjunto de estados aceitantes e Γ seja o alfabeto. Em seguida, vamos construir o conjunto de estados Q ' de M ' da seguinte forma: Q ' = { n , q , s , p , um QMFQΓQM onde p é a posição da cabeça de leitura / gravação acima da fita. Podemos restringir a posição para { - 50 , . . . , 50 } porque o número de etapas de computação permitidas limita o número de posições alcançáveis.Q={n,q,s,p,a|n{0,...,50}qQ,sΓ,p{50,...,50},aqF}p{50,...,50}

Tendo um estado do autómato finito M ' , em seguida, significa que estamos em estado Q do autómato original, com s sobre a fita na posição p , onde também a cabeça de leitura / gravação está posicionado , após a n- ésima etapa da computação. O estado é um um aceitar se um t r u e .n,q,s,p,aMqspnatrue

Transformar a relação de transição de uma máquina de turing de concreto é um pouco mais trabalhoso, mas não é necessário para a pergunta original, pois basta mostrar que o espaço de estados é finito (e, portanto, podemos apenas testar cada entrada com um comprimento máximo de 50 símbolos em cada um desses autômatos). A ideia é a construção de uma nova relação de transição que vai de um estado para um estado n + 1 , Q ' , s ' , p ' , um ' no nn,q,s,p,an+1,q,s,p,an-ésima etapa sse a transição de computação estava na relação de transição inicial.q,s,pq,s,p

swegi
fonte
Como você simula o armazenamento na fita, ou seja , a capacidade de revisitar símbolos que você já leu, em um autômato finito?
Niel de Beaudrap
@NieldeBeaudrap: Você enumera todo o espaço de estados, ou seja, faz a verificação do modelo da fita finita e do autômato de controle da máquina de turing.
swegi
1
Dado que o OP está fazendo perguntas básicas de computabilidade para as Máquinas de Turing, convém descompactar esse esboço em algo mais completo. (Eu mesmo nunca ouvi a frase "verificação de modelo" em um contexto computacional antes.) No contexto, eu normalmente assumia por 'autômato finito' que você significaria um DFA ou similar, a menos que especificasse o contrário, e não está claro para mim o que corresponderia à contribuição do DFA nessa construção. Se você apenas quer dizer um gráfico representando possíveis trajetórias da MT, eu concordo.
Niel de Beaudrap 9/08/12
Com o modelo verificando a parte finita da fita, quero dizer basicamente o que você escreveu em sua resposta: basta testar cada entrada de tamanho no máximo 50 e verificar se é atingido um estado de aceitação.
swegi
1
Eu gostaria que as pessoas parassem de propagar o mito de que uma fita de máquina de Turing precisa ser infinita. Não - pode ser finito desde que seja estendido conforme necessário.
Reinierpost