Simulasi universal mesin Turing

Biarkan menjadi fungsi tetap yang dapat dibangun-waktu.$f$

Hasil simulasi universal klasik untuk TMs (Hennie dan Stearns, 1966) menyatakan bahwa ada dua-tape TM sedemikian rupa sehingga diberikan$U$

• deskripsi dari TM , dan$\langle M \rangle$
• string input ,$x$

dijalankan untuk langkah dan mengembalikan jawaban M pada x . Dan g dapat dianggap sebagai fungsi apa pun dalam ω ( f ( n ) lg f ( n ) ) .$g(|x|)$$M$$x$$g$$\omega(f(n)\lg f(n))$

Pertanyaan saya adalah:

1. Apa hasil simulasi paling dikenal pada single tape TM? Apakah hasil di atas juga masih bertahan?

2. Apakah ada peningkatan pada [HS66]? Bisakah kita mensimulasikan TM pada TM dua-tape untuk langkah-langkah dengan lebih cepat? Bisakah kita menganggap g ( n ) berada di ω ( f ( n ) ) menggantikan ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Apa hasil simulasi paling dikenal pada single tape TM? Apakah hasil di atas juga masih bertahan?

Kita dapat mensimulasikan multi-tape TM pada single-tape TM dengan peningkatan kuadrat waktu. Waktu simulasi adalah . Peningkatan kuadrat diperlukan karena ada bahasa (misalnya palindrom) yang membutuhkan waktu Ω ( n 2 ) pada DTM tape tunggal tetapi dapat diselesaikan dalam waktu O ( n ) pada DTM dua tape.$O(n^2)$$\Omega(n^2)$$O(n)$

Singkatnya, hasil di atas tidak berfungsi ketika simulator adalah single-tape TM.

Untuk simulasi single-tape TM pada single-tape TM (dengan alfabet hingga sewenang-wenang), hasilnya berlaku, yaitu simulasi dapat dilakukan dengan peningkatan faktor dalam waktu. Lihat (2) dan (3). Rujukannya tampaknya (6).$\lg$

Apakah ada peningkatan pada [HS66]? Bisakah kita mensimulasikan TM pada TM dua-tape untuk langkah-langkah dengan lebih cepat? Bisakah kita menganggap g ( n ) berada di ω ( f ( n ) ) menggantikan ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Tampaknya belum ada perbaikan sejak itu akan menyiratkan teorema hierarki waktu yang lebih baik daripada yang diketahui saat ini.

Koreksi: Teorema hierarki biasa didasarkan pada kelas kompleksitas waktu yang didefinisikan menggunakan TM tape tunggal. Untuk -tape TM, hasil yang mirip dengan teorema hierarki ruang dibuktikan oleh Furer pada tahun 1982 (5). The lg faktor tidak diperlukan. Lihat juga (4).$n$$\lg$

Referensi:

1. Peter van Emde Boas, "Model Mesin dan Simulasi", dalam Handbook of Theoretical Computer Science, 1990
   (khususnya, hlm. 18-21)

2. Michael Sipser, "Pengantar Teori Komputasi", 2006
   (kelas kompleksitas waktu didefinisikan menggunakan TM dengan pita tunggal tak terbatas di kedua arah dan alfabet terbatas sewenang-wenang, lihat halaman 140 dan 341)

3. Odifreddi, "Teori Rekursi Klasik", vol. I & II, 1989 & 1999
   (definisi mirip dengan Sipser, lihat Def. I.4.1 di vol. I halaman 48, Def. VII.4.1 di vol. II halaman 67, dan Thm. VII.4.15 di vol. Halaman II 83)

4. Piergiorgio Odifreddi, "Teori Rekursi Klasik", vol. II, 1999
   (halaman 84)

5. Martin Fürer, " Hierarki Waktu Deterministik Ketat ", 1982

6. Juris Hartmanis, " Kompleksitas Komputasi dari Komputasi Mesin Turing Satu Pita ", 1968

7. FC Hennie dan RE Stearns, " Simulasi Dua Pita Mesin Turing Multitape ", 1966

8. Pertanyaan terkait lainnya:

   1. Batas bawah dan pemisahan kelas ,
   2. $\lg f$
   3. Alfabet dari mesin Turing single-tape ,
   4. Untuk teorema hierarki waktu, bagaimana input diterjemahkan secara efisien? ,
   5. komentar oleh Luca Trevisan.