Apa perbedaan antara RAM dan TM?

10

Dalam analisis algoritma, kami mengasumsikan satu prosesor generik Random Access Machine (RAM). Sejauh yang saya tahu, mesin RAM tidak lebih efisien daripada mesin Turing. Semua algoritma dapat diimplementasikan di mesin Turing. Jadi pertanyaan saya adalah:

  • Jika mesin Turing seefisien mesin RAM, lalu mengapa kita tidak mengasumsikan mesin Turing untuk analisis algoritma?

  • Apa perbedaan antara RAM dan TM?

turing-machines computation-models tanmoy
sumber

Jawaban:

13

Mesin Turing tidak seefisien mesin RAM. Mesin RAM dapat mengakses lokasi pita arbitrer diHAI(1). Mesin Turing tidak bisa. Mesin RAM dapat melakukan aritmatika diHAI(1)(di bawah batasan tertentu). Mesin Turing tidak bisa.

Mesin Turing mensimulasikan mesin RAM secara polis, yaitu, untuk beberapa konstan c, mesin RAM mana saja yang berjalan pada waktunya HAI(nk) dapat disimulasikan oleh mesin Turing yang berjalan tepat waktu HAI(nck). (Konstanta cukup masuk akal, tentang2, tergantung pada model mesin Turing.)

Yuval Filmus
sumber
1
Terima kasih Yuval. Sekarang saya mengerti bahwa RAM lebih cepat daripada mesin Turing. Tapi mengapa 2?
tanmoy
saya mendapat 2karena itulah (secara kasar) waktu yang dibutuhkan secara naif untuk mensimulasikan akses acak. Saya bisa salah di sini.
Yuval Filmus
2
Anda harus melihat di Cook's Time Bounded Random Access Machines , di mana overhead dalam mensimulasikan satu model dengan yang lain terbukti tepat.
Clément
Hanya pertanyaan singkat: Jika ada masalah Π memiliki algoritma waktu polinomial pada model RAM, dapatkah saya mengatakan itu Πmemiliki algoritma polinomial-waktu pada model TM? Atau sebagai alternatif, Jika ada masalahΠ memiliki algoritma waktu polinomial pada model RAM, dapatkah saya mengatakan itu Πada di P?
drzbir
1
@ Azzo Anda benar, masalahnya ada di P jika ia memiliki algoritma waktu polinomial dalam model RAM jika ia memiliki algoritma waktu polinomial dalam model mesin Turing.
Yuval Filmus