Simulação universal de máquinas de Turing

16

Seja uma função construtiva de tempo fixa.f

O resultado clássico da simulação universal para as TMs (Hennie e Stearns, 1966) afirma que existe uma TM duas fitas que, dada aU

  • a descrição de uma TM , eM
  • uma sequência de entrada ,x

corre para as etapas e retorna a resposta de em . E podem ser considerados como qualquer função no .g(|x|)x g ω ( f ( n ) lg f ( n ) )Mxgω(f(n)lgf(n))

Minhas perguntas são:

  1. Qual é o resultado de simulação mais conhecido em uma única fita TM? O resultado acima também se mantém?

  2. Existe alguma melhoria no [HS66]? Podemos simular TMs em uma TM de duas fitas para etapas de maneira mais rápida? Podemos tomar g ( n ) para estar em ω ( f ( n ) ) no lugar de ω ( f ( n ) lg f ( n ) ) ?f(n)g(n)ω(f(n))ω(f(n)lgf(n))

Kaveh
fonte
O número de fitas deve ser igual ou limitado de alguma forma?
Raphael
E várias fitas podem ser simuladas em tempo quadrático em uma fita; portanto, se esse tipo de simulação é justo, por que você espera uma diferença? Ou o tempo da simulação linear é justo por outras razões?
Raphael
"Estou perguntando se a simulação pode ser feita com sobrecarga linear" - não posso combinar isso com a pergunta. Você quis dizer ? o(f(n))
Raphael
1
@ Rafael, eu verifiquei novamente e atualizei a pergunta. O está correto, observe que g é umωg função arbitrária em . (no teorema, precisamos de algo que cresça mais rápido que f ( n ) lg f ( n ) porque o alfabeto e o número de estados da máquina simulada não são fixos; portanto, há uma constante dependendo da máquina. ω é usado por causa de -los).ω(f(n))f(n)lgf(n)ω
Kaveh

Respostas:

7

Qual é o resultado de simulação mais conhecido em uma única fita TM? O resultado acima também se mantém?

Podemos simular uma TM múltipla fita em uma única fita com aumento quadrático no tempo. O tempo de simulação é . O aumento quadrático é necessário, pois existem idiomas (por exemplo, palíndromos) que requerem tempo Ω ( n 2 ) em um DTM de fita única, mas podem ser resolvidos no tempo O ( n ) em um DTM de duas fitas.O(n2)Ω(n2)O(n)

Em resumo, o resultado acima não funciona quando o simulador é uma TM de fita única.

Para a simulação de TMs de fita única em uma TM de fita única (com alfabeto finito arbitrário), o resultado é válido, ou seja, a simulação pode ser feita com o aumento do fator no tempo. Veja (2) e (3). A referência parece ser (6).lg

Existe alguma melhoria no [HS66]? Podemos simular TMs em uma TM de duas fitas para etapas de maneira mais rápida? Podemos pegar g (f(n) para estar em ω ( f ( n ) ) no lugar de ω ( f ( n ) lg f ( n ) ) ?g(n)ω(f(n))ω(f(n)lgf(n))

Parece que não houve nenhuma melhoria, pois isso implicaria um teorema da hierarquia de tempo melhor do que o atualmente conhecido.

Correção: Os teoremas habituais da hierarquia são baseados em classes de complexidade de tempo definidas usando TMs de fita única. Para TMs tape, um resultado apertado semelhante ao teorema da hierarquia espacial é comprovado por Furer em 1982 (5). O fator lg não é necessário. Veja também (4).nlg

Referências:

  1. Peter van Emde Boas, "Modelos de Máquinas e Simulação", no Manual de Ciência da Computação Teórica, 1990
    (em particular, pp. 18-21)

  2. Michael Sipser, "Introdução à Teoria da Computação", 2006
    (as classes de complexidade de tempo são definidas usando TMs com fita simples infinita em ambas as direções e alfabeto finito arbitrário, consulte as páginas 140 e 341)

  3. Odifreddi, "Teoria Clássica da Recursão", vol. I e II, 1989 e 1999
    (as definições são semelhantes às de Sipser, consulte Def. I.4.1 no vol. I página 48, Def. VII.4.1 no vol. II página 67 e Thm. VII.4.15 na vol. II página (83)

  4. Piergiorgio Odifreddi, "Teoria Clássica da Recursão", vol. II, 1999
    (página 84)

  5. Martin Fürer, " A estreita hierarquia determinística do tempo ", 1982

  6. Juris Hartmanis, " Complexidade Computacional de Computações com Máquina de Turing com Uma Fita ", 1968

  7. FC Hennie e RE Stearns, " Simulação em Duas Fitas de Máquinas de Turing Multitape ", 1966

  8. Outras questões relacionadas:

    1. Limites inferiores e separação de classes ,
    2. lgf
    3. Alfabeto da máquina de Turing de fita única ,
    4. Para o teorema da hierarquia de tempo, como a entrada é traduzida eficientemente? ,
    5. um comentário de Luca Trevisan.
Kaveh
fonte
Ainda existem algumas coisas que ainda não estão completamente claras para mim, particularmente sobre a versão 8.3 e a simulação de fita única de máquinas de fita única, atualizarei a resposta, se necessário.
Kaveh
Harmanis'68, Thm. 7 usa a simulação, mas é apenas para . Para t menor ( n )n2t(n)t(n) menor, Harmanis fornece uma prova direta do teorema da hierarquia de tempo.
Kaveh