Restrições da máquina de Turing que tornam a parada decidível

33

Se alguém restringir as máquinas de Turing a uma fita finita (ou seja, para usar o espaço limitado ), o problema de parada será decidido, essencialmente porque após várias etapas (que podem ser calculadas a partir do número de estados , e , e o tamanho do alfabeto), uma configuração deve ser repetida.Q SSQS

Existem outras restrições naturais da Máquina de Turing que tornam a parada decidível?

Certamente, se o gráfico de transição de estado não tiver ciclos ou ciclos, a interrupção é decidível. Alguma outra?

Joseph O'Rourke
fonte
1
Você também pode considerar TM que pode ser provado ser total digamos PA, ZFC, ...
Kaveh
@ Kaveh: Isso poderia ser formulado como uma restrição ao comportamento da MT, em algum sentido quase físico?
Joseph O'Rourke
Não, eu não penso assim.
Kaveh
1
O problema de decisão em uma máquina de registro único (com instruções de incremento-e-salto incondicional, se-zero-então-salto-mais-decremento-e-salto e parada) é decidível.
Wchargin
AFAIK O problema da parada para máquinas de Turing com um espaço limitado S, não é determinável por máquinas de Turing que são delimitadas para o espaço S.
Taemyr

Respostas:

30

Uma variação bastante natural e estudada é a máquina de Turing com inversão de fita (o número de inversões de fita é limitado); veja por exemplo:

Juris Hartmanis: Computações de máquinas de Turing vinculadas com inversão de fita. J. Comput. Syst. Sci. 2 (2): 117-135 (1968)


Editar : [essa variação é mais artificial] o problema de parada é decidível para uma máquina de Turing que não apaga e que possui no máximo duas instruções restantes no alfabeto ; veja Maurice Margenstern: Máquinas de Turing não-telescópicas: uma fronteira entre um problema de parada decente e a universalidade. Theor. Comput. Sci. 129 (2): 419-424 (1994){0 0,1}

Marzio De Biasi
fonte
O limite de inversão de fita é realmente bastante natural. Obrigado!
Joseph O'Rourke
18

Considerando-se como a passagem de parâmetros para as sub-rotinas e uma grande parte do gerenciamento de memória nas principais linguagens de computador é baseada em pilha, uma variação óbvia e natural é restringir a memória ilimitada de uma máquina de Turing a uma pilha.

Esse modelo possui boas propriedades , além de deixar de ser decidível (conhecido por PDAs ):

A noção de um PDA pode ser generalizada para um auxiliar pushdown autómato ( S ( n ) -AuxPDA)S(n)S(n) . Isso consiste de

  1. uma fita de entrada somente leitura, cercada por marcadores finais,
  2. um controle de estado finito,
  3. S(n)n
  4. uma pilha

Em "Hopcroft / Ullman (1979) Introdução à Teoria dos Autômatos, Idiomas e Computação (1ª ed.) , Encontramos:

S(n)registron

  1. euS(n)
  2. euS(n)
  3. euDTIME(cS(n))c

com o surpreendente:

euPeuregistron

Thomas Klimpel
fonte
Obrigado, Thomas, esta também é uma restrição natural.
Joseph O'Rourke
3

a formulação desta questão é um pouco problemática, porque uma máquina de Turing com uma fita finita não tem muito a ver com uma máquina de Turing e está mais próxima / essencialmente de uma máquina de estados finitos. Da mesma forma que todas as outras "restrições" nas máquinas de Turing, quase todas as restrições parecem ser um fenômeno totalmente diferente (isto é, exceto a integridade de Turing com propriedades completamente diferentes). de fato, alguns trabalhos agora chamam / estudam esse limite em detalhes e pode ter alguma similaridade aproximada com outro famoso limite de computação, ou seja, transições de fase completa de NP.

e é um tanto contra-intuitivo que a teoria FSM "computacionalmente mais simples / totalmente decidível" tenha surgido muito tempo após a invenção da máquina de Turing, presumivelmente um pouco vagamente inspirada por ela. portanto, talvez uma maneira de reformular isso seja solicitar os "modelos decidíveis mais sofisticados" da computação ou "o estudo da fronteira entre modelos de computação indecidíveis e decidíveis".

de qualquer maneira, então ligeiramente reformulada dessa maneira, uma resposta razoável / teoria / programa de pesquisa ainda não listada é a agora significativamente desenvolvida e ativamente pesquisada / teoria dos autômatos temporizados, que acabou de ganhar um prêmio da Igreja por Alur / Dill. Aqui está um exemplo de um artigo sobre autômatos cronometrados e o estudo do limite da (des) decidibilidade do modelo de computação e existem muitos outros nesse sentido.

vzn
fonte
coincidentemente, a pergunta parece conceitualmente semelhante à que foi feita recentemente em Ciência da Computação : Quais são as linguagens terminativas mais expressivas?
vzn
1
Obrigado pelos links para autômatos cronometrados , cujo conceito eu desconhecia.
Joseph O'Rourke 15/05
btw, reflexão tardia / adendo: um aspecto da teoria conhecida que tende / parece pressionar contra qualquer "relaxamento natural decidível" de uma MT existente, Rices thm . no entanto, outro ponto de vista / idéia natural evocado de alguma forma em outras respostas é que toda a hierarquia de tempo / espaço e as classes de complexidade são todas as versões decidíveis "naturais" das TMs.
vzn
Uma máquina de estado finito pode estar muito longe de uma máquina de Turing para falar de uma restrição, mas uma máquina restrita de Turing que poderia computar todas as funções recursivas primitivas estaria suficientemente próxima para que se possa razoavelmente dizer que é um modelo restrito de uma máquina de Turing.
Thomas Klimpel