Was ist der Unterschied zwischen RAM und TM?

10

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?

Tanmoy
quelle

Antworten:

13

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 O ( 1 ) rechnen (unter bestimmten Einschränkungen). Eine Turingmaschine kann nicht.O(1)O(1)

cO(nk)O(nck)2

Yuval Filmus
quelle
1
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
ΠΠΠΠ
1
@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