¿Cuál es la diferencia entre RAM y TM?

10

En el análisis de algoritmos, asumimos una máquina de acceso aleatorio (RAM) genérica de un procesador. Hasta donde yo sé, la máquina RAM no es más eficiente que la máquina Turing. Todos los algoritmos se pueden implementar en la máquina Turing. Entonces mis preguntas son:

  • Si la máquina de Turing es tan eficiente como la máquina de RAM, entonces ¿por qué no estamos asumiendo la máquina de Turing para el análisis de algoritmos?

  • ¿Cuál es la diferencia entre RAM y TM?

turing-machines computation-models tanmoy
fuente

Respuestas:

13

Las máquinas de Turing no son tan eficientes como las máquinas de RAM. Una máquina RAM puede acceder a una ubicación de cinta arbitraria en . Una máquina de Turing no puede. Una máquina RAM puede hacer aritmética en (bajo ciertas restricciones). Una máquina de Turing no puede.O(1)O(1)

Las máquinas de Turing simulan polinómicamente máquinas RAM, es decir, para alguna constante , cualquier máquina RAM que se ejecute en el tiempocO(nortek) puede ser simulada por una máquina Turing que se ejecute en el tiempo . (La constante es bastante razonable, aproximadamente , dependiendo del modelo de máquina de Turing).O(norteCk)2

Yuval Filmus
fuente
1
Gracias Yuval. Ahora entiendo que la RAM es más rápida que la máquina Turing. ¿Pero por qué 2?
tanmoy
Obtengo ya que ese es (aproximadamente) el tiempo que ingenuamente lleva simular el acceso aleatorio. Podría estar equivocado aquí. 2
Yuval Filmus
2
Debe echar un vistazo a las máquinas de acceso aleatorio limitado por tiempo de Cook , donde se demuestra con precisión la sobrecarga al simular un modelo con otro.
Clément
Solo una pregunta rápida: si hay un problema Π tiene un algoritmo de tiempo polinómico en el modelo RAM, ¿puedo decir que Πtiene un algoritmo de tiempo polinómico en el modelo TM? O alternativamente, si hay un problemaΠ tiene un algoritmo de tiempo polinómico en el modelo RAM, ¿puedo decir que Πestá en P?
drzbir
1
@Azzo Tiene razón, un problema está en P si tiene un algoritmo de tiempo polinomial en el modelo RAM si tiene un algoritmo de tiempo polinomial en el modelo de máquina Turing.
Yuval Filmus