Quelle est la différence entre RAM et TM?

Les machines de Turing ne sont pas aussi efficaces que les machines RAM. Une machine RAM peut accéder à un emplacement de bande arbitraire dans $O(1)$ . Une machine de Turing ne peut pas. Une machine RAM peut faire de l'arithmétique dans $O(1)$ (sous certaines restrictions). Une machine de Turing ne peut pas.

Les machines de Turing simulent polynomiquement des machines RAM, c'est-à-dire pour $c$ , toute machine RAM fonctionnant à temps $O(n^k)$ peut être simulé par une machine de Turing fonctionnant dans le temps $O(n^{ck})$ . (La constante est assez raisonnable, environ $2$ , selon le modèle de la machine Turing.)

Yuval Filmus
la source

Merci Yuval. Maintenant je comprends que la RAM est plus rapide que la machine Turing, mais pourquoi 2?

tanmoy

Je reçois

2

$2$ car c'est (à peu près) le temps naïvement nécessaire pour simuler un accès aléatoire. Je peux me tromper ici.

Yuval Filmus

Vous devriez jeter un œil à Time Bounded Random Access Machines de Cook , où la surcharge de simulation d'un modèle avec un autre est prouvée avec précision.

Clément

Juste une petite question: en cas de problème

Π

$\Pi$ a un algorithme polynomial sur le modèle RAM, puis-je dire que

Π

$\Pi$ a un algorithme polynomial sur le modèle TM? Ou bien, si un problème

Π

$\Pi$ a un algorithme polynomial sur le modèle RAM, puis-je dire que

Π

$\Pi$ est en P?

drzbir

@Azzo Vous avez raison, un problème est dans P ssi il a un algorithme de temps polynomial dans le modèle RAM ssi il a un algorithme de temps polynomial dans le modèle de machine de Turing.

Yuval Filmus

Quelle est la différence entre RAM et TM?

Réponses: