Qual é a diferença entre RAM e TM?

10

Na análise de algoritmos, assumimos uma máquina de acesso aleatório (RAM) de um processador genérico. Até onde eu sei, a máquina de RAM não é mais eficiente que a máquina de Turing. Todos os algoritmos podem ser implementados na máquina de Turing. Então, minhas perguntas são:

  • Se a máquina de Turing é tão eficiente quanto a máquina de RAM, por que não estamos assumindo a máquina de Turing para análise de algoritmos?

  • Qual é a diferença entre RAM e TM?

turing-machines computation-models tanmoy
fonte

Respostas:

13

Máquinas de Turing não são tão eficientes quanto as máquinas de RAM. Uma máquina de RAM pode acessar um local de fita arbitrário noO(1). Uma máquina de Turing não pode. Uma máquina de RAM pode fazer aritmética emO(1)(sob certas restrições). Uma máquina de Turing não pode.

Máquinas de Turing simulam polinomialmente máquinas de RAM, ou seja, por algumas constantes c, qualquer máquina de RAM em execução no tempo O(nk) pode ser simulado por uma máquina de Turing funcionando no tempo O(nck). (A constante é bastante razoável, sobre2, dependendo do modelo da máquina de Turing.)

Yuval Filmus
fonte
1
Agora eu entendo que a RAM é mais rápida que a máquina de Turing. Mas por que 2?
Tanmoy
eu recebo 2já que esse é (aproximadamente) o tempo que ingenuamente leva para simular o acesso aleatório. Eu poderia estar errado aqui.
Yuval Filmus
2
Você deve dar uma olhada nas Máquinas de acesso aleatório limitado por tempo da Cook , onde a sobrecarga na simulação de um modelo com outro é precisamente comprovada.
Clément
Apenas uma pergunta rápida: se houver um problema Π possui um algoritmo de tempo polinomial no modelo de RAM, posso dizer que Πpossui um algoritmo de tempo polinomial no modelo da MT? Ou, alternativamente, se um problemaΠ possui um algoritmo de tempo polinomial no modelo de RAM, posso dizer que Πestá em P?
drzbir
1
@ Azz Você está correto, existe um problema em P se ele tiver um algoritmo de tempo polinomial no modelo de RAM se ele tiver um algoritmo de tempo polinomial no modelo de máquina de Turing.
Yuval Filmus