Was ist der Unterschied zwischen RAM und TM?

Bei der Algorithmusanalyse nehmen wir eine generische Random Access Machine (RAM) mit einem Prozessor an. Soweit ich weiß, ist die RAM-Maschine nicht effizienter als die Turing-Maschine. Alle Algorithmen können in der Turingmaschine implementiert werden. Meine Fragen sind also:

Wenn die Turing-Maschine genauso effizient ist wie die RAM-Maschine, warum nehmen wir dann keine Turing-Maschine für die Algorithmusanalyse an?
Was ist der Unterschied zwischen RAM und TM?

turing-machines computation-models Tanmoy
quelle

Antworten:

Turingmaschinen sind nicht so effizient wie RAM-Maschinen. Eine RAM-Maschine kann auf eine beliebige Bandposition in zugreifen . Eine Turingmaschine kann nicht. Eine RAM-Maschine kann in rechnen (unter bestimmten Einschränkungen). Eine Turingmaschine kann nicht. $O(1)$ $O(1)$

$c$ $O(n^k)$ $O(n^{ck})$ $2$

Yuval Filmus
quelle

Danke Yuval. Jetzt verstehe ich, dass RAM schneller ist als Turing Maschine. Aber warum 2?

Tanmoy

2

$2$

Sie sollten sich Cooks zeitgebundene Direktzugriffsmaschinen ansehen, bei denen der Aufwand für die Simulation eines Modells mit einem anderen genau bewiesen ist.

Clément

Π

$\Pi$

Π

$\Pi$

Π

$\Pi$

Π

$\Pi$

@Azzo Sie haben Recht, ein Problem liegt in P vor, wenn es einen Polynomzeitalgorithmus im RAM-Modell gibt, wenn es einen Polynomzeitalgorithmus im Turing-Maschinenmodell hat.

Yuval Filmus