Kompleksitas Waktu dari Simulasi Mesin Turing Universal dan Teorema Hierarki Waktu

Saya punya sedikit masalah untuk memahami bukti Teorema Time Hierarchy (Hennie and Stearns, 1966) yang memastikan keberadaan bahasa yang dapat diterima dalam tetapi tidak dapat diterima dalam untuk fungsi apa pun , sehingga dapat dikonstruksi waktu dan$U(n)$$T(n)$$T(n),U(n)$$U(n)$

Bukti ini didasarkan pada keberadaan mesin Universal Turing yang mensimulasikan setiap mesin Turing dengan kompleksitas waktu dalam waktu .$T(n)$$T(n) \log T(n)$

Saya mengerti (dan percaya) bukti bahwa setiap mesin -tape Turing dapat disimulasikan oleh mesin Turing dua-pita dengan overhead logaritmik. Namun, saya mengerti konstruksi ini hanya jika mesin Turing yang disimulasikan diperbaiki, tidak dalam kasus simulasi Universal TM.$k$

Saya melihat satu "masalah" dalam alasan yang diberikan dalam makalah yang dikutip (dan juga di beberapa buku standar tentang kompleksitas komputasi) terkait dengan konstruksi mesin Universal. "Masalah" ini adalah bahwa dalam simulasi mesin Universal, satu langkah komputasi dari mesin yang disimulasikan seharusnya dijalankan dalam waktu yang konstan oleh mesin Universal. Dengan kata lain, panjang deskripsi mesin yang disimulasikan seharusnya konstan.

Tetapi apakah ini OK? Karena dalam bukti Teorema Hierarki Waktu, input yang diberikan ke mesin Turing yang disimulasikan adalah persis deskripsi ini, dan dengan demikian, deskripsi tersebut entah bagaimana bergantung pada . Saya sadar bahwa deskripsi dapat diperpanjang dengan urutan bit terkemuka, tetapi ini tampaknya tidak menyelesaikan masalah ini.$n$

Artinya, saya tidak tahu mengapa langkah perhitungan dari mesin yang disimulasikan dapat dieksekusi dalam waktu yang konstan oleh mesin Universal. Makalah Hennie dan Stearns tidak terlalu memperhatikan hal ini, ia hanya menyatakan bahwa saat ini adalah sesuatu yang secara implisit dianggap konstan. Demikian pula dalam buku teks yang saya baca tentang topik tersebut.

Saya tidak tahu mengapa kompleksitas waktu dari simulasi adalah , dan bukan .$T(n)\log T(n)$$n T(n) \log T(n)$

Saya hampir yakin bahwa saya kehilangan sesuatu. Namun, saya mencoba untuk memahami ini untuk waktu yang relatif lama dan entah bagaimana saya tidak bisa mengetahuinya.

Di sini saya merujuk pada bukti teorema hierarki yang saya kenal, di mana saya tidak melihat masalah yang Anda sebutkan.

Kami mendefinisikan bahasa tidak menerima dalam (di mana adalah fungsi waktu yang sedang kita kerjakan).$L=\{(M,w): M$$(M,w)$$\le \frac{t(n)}{|M|^3+|M|\log t(n)}, n=|(M,w)|\}$$t$

Kami menunjukkan bahwa dapat dipilih dalam menggunakan mesin universal, dan dalam mesin universal setiap langkah memang tergantung pada ukuran mesin, itulah sebabnya kami memiliki dalam penyebut ( 3 hanyalah beberapa batas atas pada perhitungan yang diperlukan untuk mensimulasikan langkah).$L$$O(t(n))$$|M|^3$

Untuk kelengkapan jawabannya: ketika kita mencoba untuk mencapai suatu kontradiksi, maka kita asumsikan bahwa ada sebuah mesin yang memutuskan . Setelah asumsi ini, pengkodean adalah tetap, dan kemudian simulasi satu langkah benar-benar mengambil waktu yang konstan, dan kita dapat mencapai kontradiksi dengan mengambil cukup lama untuk meningkatkan panjang input tanpa mengubah .$T$$L$$T$$w$$T$