É decidível se uma TM atinge alguma posição na fita?

14

Eu tenho essas perguntas de um exame antigo que estou tentando resolver. Para cada um dos problemas, a entrada é uma codificação de uma máquina de Turing .M

Para um número inteiro e os três problemas a seguir:c>1

  1. É verdade que, para cada entrada , M não passa na posição ao executar ?| x | + c xx|x|+cx

  2. É verdade que, para cada entrada , M não passa na posição ao executar x ?max { | x | - c , 1 } xxmax{|x|c,1}x

  3. É verdade que, para cada entrada x , M não passa na posição (|x|+1)/c ao executar em x ?

Quantos problemas são decidíveis?

O número do problema (1), na minha opinião, está em coRER se entendi correto, pois posso executar todas as entradas em paralelo e parar se alguma entrada chegou a essa posição e por mostrar que não é em R eu posso reduzir o complemento de Atm . Construo uma máquina de Turing M seguinte maneira: para uma entrada y , verifico se y é um histórico de computação, se for, então M funcionando corretamente e não para, se não for, para.

Para (3), acredito que seja decidível, pois para c2 são todas as máquinas de Turing que sempre ficam na primeira célula da faixa, pois para uma sequência de um caractere pode passar pela primeira célula, então eu preciso simular todas as cadeias de comprimento 1 para as etapas |Q|+1 (isso está correto?) e ver se estou usando apenas a primeira célula em todas elas.

Eu realmente não sei o que fazer com (2).

Jozef
fonte
1) Você assume uma fita infinita unilateral? 2) O que é ATM?
Raphael
1) Sim, 2) O problema de aceitação.
Jozef

Respostas:

9

Qualquer situação que indique se uma Máquina de Turing está confinada a uma seção finita da fita (digamos, do comprimento ) em uma determinada entrada é decidível.n

O argumento funciona da seguinte maneira. Considere a máquina de Turing, a fita e a posição da máquina de Turing na fita. Juntos, eles têm um número finito de configurações. Para ser específico, existem apenasconfigurações possíveis. é o conjunto de símbolos da fita e é o conjunto de estados. Continuarei a usar a palavra "configuração" para descrever o estado da Máquina de Turing combinado com o estado da fita e sua posição na fita pelo restante desta resposta, mas esse não é o vocabulário padrão.Γ Qt=n|Γ|n|Q|ΓQ

Execute a máquina, acompanhando todas as suas configurações anteriores. Se alguma vez ultrapassar o ponto , retorne "sim, passa à posição ". Caso contrário, a máquina está em algum lugar entre 0 e . Se a máquina repetir uma configuração - seu estado, os símbolos na fita e sua posição na fita são idênticos aos que eram antes - retornam "não, nunca passa na posição ".M n n M nnMnnMn

Pelo princípio pidgeonhole, isso deve acontecer em não mais que etapas. Portanto, tudo o que foi dito acima é decidível; depois de no máximo etapas simuladas, você obtém uma resposta.t + 1t+1t+1

Uma observação rápida sobre por que isso funciona: quando a máquina, a fita e sua posição na fita se repetem, deve ter havido uma sequência de configurações entre essas repetições. Essa sequência acontecerá novamente, levando à mesma configuração mais uma vez - a máquina está em um loop infinito. Isso ocorre porque estamos acompanhando todos os aspectos da máquina de Turing; nada fora da configuração pode ter impacto no que aconteceu. Portanto, quando uma configuração se repete, ela se repete novamente, com uma série idêntica de configurações no meio.

Portanto, é possível limitar a fita a uma parte finita da corda. Portanto, iterando sobre todas as sequências de entrada possíveis, o problema está em para as três perguntas. Você já deve ter percebido isso (entre suas idéias para 1 e 3 e a resposta de Ran G para 2 parece resolvida completamente de qualquer maneira), mas achei que talvez valesse a pena postar.testemunho

SamM
fonte
"Se a máquina repetir uma configuração, [...] retorne 'não'" - isso está errado. Uma máquina não determinística pode executar um loop algumas vezes e depois seguir em frente.
Raphael
1
Estamos falando de máquinas de turing aqui, que não são consideradas não-determinísticas. Se não fosse determinístico, simule a versão determinística.
SamM 12/08/12
Boa explicação. Veja também a primeira versão da minha resposta (que eu rever uma vez que eu percebi que o OP não chegou a pedi-lo ..)
Ran G.
@ Sam: Funciona ao contrário: a menos que seja assumido de outra forma, uma máquina de Turing pode não ser determinística. O que é uma "versão determinística"? Se você quer dizer um desdobramento completo de opções, uma configuração repetida perde o significado, pois pode ocorrer em diferentes ramificações.
Raphael
2
@ Raphael, a maneira padrão de fazer isso é um gráfico de configuração: os vértices são as mesmas configurações definidas por Sam e existe uma borda direcionada da configuração A para B se o NTM puder passar de A para B em uma única etapa. O gráfico é finito ee se a máquina pára é uma questão simples de acessibilidade do gráfico. Isto também mostra que é um subconjunto de D T I M E ( 2 O ( s ) )NSPUMACE(s)DTEuME(2O(s))
Sasho Nikolov
4

(2) é muito semelhante a (3) e o mesmo raciocínio que você tinha para (3) também se aplica aqui: observe que as máquinas que em têm uma propriedade estranha - elas não leem toda a entrada (elas nunca atingem sua últimos c bits.) E isso é verdade para todas as entradas.eu2c

Ok, agora vamos considerar apenas entradas até o comprimento . Para cada uma delas, existem apenas duas opções: a máquina faz um loop / pára sem mover a cabeça ou move a cabeça. Se mover a cabeça em algum x (com | x |c ), essa máquina não está em L 2 devido a essa entrada x . Caso contrário, afirmo que a máquina está em L 2 . Como ele nunca move a cabeça - não tem idéia de qual é o tamanho da entrada! isso significa que se comporta da mesma forma para todas as entradas de comprimento | x | > C . Portanto, L 2 é decidível.cx|x|ceu2xeu2|x|>ceu2

Tocou.
fonte
Como você considera máquinas não determinísticas?
Raphael
Não considerei MNTs, mas deve ser a mesma coisa. Para todas as palavras de comprimento até o número de configurações em que o NTM pode estar sem mover a cabeça é finito. c
Ran G.
Sim, mas seu argumento é interrompido. Você não pode determinar em tempo finito (por simulação simples) se um NTM sai de uma determinada posição.
Raphael
|x|exp(|x|)
|x||Q|M