Mengapa kita menggunakan mesin Turing tape tunggal untuk kompleksitas waktu?

Seperti yang Anda tahu ada banyak anomali untuk mesin Turing tape tunggal ketika waktunya adalah : simulasi multi-tape TM, simulasi alfabet tape yang lebih besar hanya dengan , konstruktivitas waktu, non-sesak teorema hierarki waktu, ... $o(n^2)$ $\{0,1,b\}$

Juga hasil seperti , dan model lowerbounds waktu sangat spesifik untuk masalah sederhana (yang tidak diterjemahkan menjadi lowerbound superlinear pada dua pita TM). $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$ $O(n^2)$

Untuk kompleksitas ruang, kami menggunakan model di mana kami memiliki kaset input hanya baca terpisah, yang lebih alami dan kuat.

Model TM dengan banyak kaset (atau paling tidak 2 kaset yang berfungsi) akan jauh lebih kuat dan tidak akan menyebabkan anomali seperti yang saya sebutkan di atas. Saya pernah bertanya kepada seorang ahli teori kompleksitas terkemuka yang telah membuktikan hasil simulasi pada tahun-tahun awal teori kompleksitas jika dia tahu ada perbaikan pada salah satu dari hasil-hasil lama ini dan jawabannya adalah bahwa dia tidak berpikir bahwa "pertanyaan tentang model satu kaset adalah apakah penting".

Jika kita mengubah model standar untuk kompleksitas waktu menjadi TM dua tape, hasil yang masuk akal dalam teori kompleksitas tidak akan berubah dan kita menghindari anomali yang disebabkan oleh model tertentu. Jadi pertanyaan saya adalah:

apakah ada alasan mengapa kompleksitas waktu masih didefinisikan dalam hal TM tape tunggal? (selain alasan historis)

cc.complexity-theory turing-machines Kaveh
sumber

Saya belum pernah melihat kompleksitas waktu yang ditentukan oleh TM tape tunggal.

$\:$ Saya hanya melihat kelas kompleksitas waktu yang kuat yang ditentukan oleh TM tape tunggal.

$\;\;$

@ Ricky, maksud saya kompleksitas waktu dari suatu masalah didefinisikan dalam hal kompleksitas waktu dari single tape TM yang dapat menyelesaikannya.

Kaveh

dan maksud saya bahwa saya belum pernah melihat itu dilakukan.

$\:$ Saya selalu melihat, minimal, akses acak.

$\;\;$

tetapi apakah itu benar-benar definisi yang biasa? apa yang saya lihat di buku teks adalah: 1) mendefinisikan mesin single tape Turing (karena lebih sederhana); 2) menunjukkan cara memperluas ke varian lain, khususnya multi-tape dan akses acak; 3) menunjukkan bahwa semua ini dapat mensimulasikan satu sama lain dengan paling lambat polinomial; 4) segera melupakan model untuk sebagian besar, setidaknya sampai kita membutuhkan hal-hal yang lebih halus seperti mesin oracle dan pengurangan ruang log; jadi, seperti @RickyDemer, saya akan menantang klaim bahwa ini benar-benar definisi yang biasa.

Sasho Nikolov

Saya tidak punya jawaban untuk ini, tapi, saya hanya ingin menunjukkan pekerjaan ini kepada Anda oleh Yamakami ( springerlink.com/content/u844854721p83870 ). Makalah ini membahas tentang apa yang terjadi ketika Anda menambahkan saran ke mesin kecil (yaitu linear-time one-tape TM). Ini membuktikan beberapa pemisahan kelas, tetapi ia melakukannya menggunakan TMs satu-tape ini. Pemisahan ini tidak akan berfungsi jika Anda memiliki jenis TM lainnya. Saya pikir ini adalah contoh yang bagus di mana Anda dapat membuktikan hal-hal keren dengan satu-pita dan mungkin tidak bisa dengan model yang berbeda. Moralnya adalah "satu rekaman penting ketika Anda berurusan dengan hal-hal halus".

Marcos Villagra

Jawaban:

Jawaban lain terlihat sangat bagus. Saya ingin membagikan komentar yang dibuat Russell Impagliazzo bertahun-tahun yang lalu dalam sebuah kuliah, yang terus melekat pada saya sejak saat itu.

Saya pikir Turing mungkin lebih suka satu kaset TM karena masuk akal secara fisik.

Saya menunjuk Russell ke utas ini beberapa hari yang lalu tetapi, karena dia tidak ada di sini, saya ingin komentarnya diketahui, dan akan melakukan yang terbaik untuk menafsirkannya.

Untuk satu pita TM, seandainya pita panjang tak terbatas (tolong tetap dengan saya), Anda dapat membangun TM yang hanya membutuhkan jumlah energi terbatas per iterasi. Bayangkan rekaman itu sebagai batang panjang, dan kepala, yang berisi semua logika TM, cukup bergerak di sepanjang batang ini. (Saya menganggapnya sebagai alat kecil yang diarahkan, menggunakan teknologi yang sangat primitif. Batang dapat memiliki takik untuk membantunya, dan isi sel pita hanya dapat menjadi blok yang meluncur secara ortogonal ke poros batang.)

$k$ $k$ dari alat-alat di atas, mereka harus mengkomunikasikan status baca mereka ke kepala lain yang berpotensi sangat jauh, yang mengambil jumlah energi yang tidak terbatas (misalnya Anda menggunakan kabel, yang tentu saja membocorkan panas), dan terlebih lagi tidak instan, sehingga menyulitkan mekanisme. Jika sebaliknya Anda menyatukan kepala dan memindahkan kaset di bawahnya, Anda akan menggunakan energi yang cukup untuk memindahkan kaset dengan panjang tak terbatas .. Saya tidak melihat bagaimana mendapatkan energi yang terikat dalam kedua kasus. Trik seperti penambahan pita yang menyusut (untuk mendapatkan panjang yang terbatas) mengandaikan alam semesta yang dapat dibagi secara tak terhingga, dan melanggar hal-hal seperti konstanta Planck dan prinsip holografik. Bahkan mengabaikan ini, mekanisme di kepala harus tepat sewenang-wenang, yang lagi-lagi menyebabkan masalah energi, dan sangat rumit.

$k$

matus
sumber

Saya berpikir bahwa Turing mencoba untuk mengabstraksi konsep "komputasi" dan tidak mengabstraksi model untuk perangkat fisik. dalam kasus itu, mesin Turing satu-pita menangkap dengan bersih intuisi filosofis bahwa perhitungan melibatkan akses lokal ke memori (tak terbatas) yang besar

Sasho Nikolov

Saya mengharapkan alasan teoritis (bukan realisasi model) tetapi saya menemukan jawaban ini sangat menarik, jadi saya menerimanya. Terima kasih lagi.

Kaveh

Menjaga pita tetap di tempatnya sepertinya kita dapat membuat loglinear energi total atau mudah-mudahan tidak lebih buruk daripada quasilinear pada waktunya dengan merekayasa bentuk konstruksi Hennie-Stearns. Saya membayangkan kaset digulung menjadi loop yang semakin besar saat mereka memanjang ke arah mana pun ... Atau lebih imajinatif, pada gulungan kaset, 100 kaset menjadi gulungan, 100 gulungan ke rak, 100 rak ke gudang, dan seterusnya dan di. Tentu saja untuk energi yang dibatasi per iterasi kita membutuhkan energi total linear dalam waktu. Tapi quasilinear lebih baik daripada kuadrat naif jadi saya pikir saya akan menyebutkannya.

Dan Brumleve

$f(n)$

Ada alasan pedagogis yang jernih mengapa Sipser melakukan ini, yaitu jalur yang secara alami mengalir seperti itu karena:

Anda harus memperkenalkan mesin tape tunggal sebelum mesin multi-tape, jika tidak curam kurva belajar.
$\cdot$ $\cdot$
Anda sebaiknya membandingkan mesin multi-tape dengan mesin single tape saat Anda memperkenalkan mesin multi-tape, jika tidak, ketidaktahuan yang berkepanjangan akan menyebabkan kebingungan tambahan.
Anda bisa menghilangkan pengenalan kelas TIME analog untuk mesin multi-tape, sehingga menyederhanakan notasi secara keseluruhan.

Tidak ada alasan untuk berdebat tentang kebersihan konseptual ketika pedagogi dengan jelas menentukan jalur termudah, dan setiap mahasiswa ilmu komputer harus mengambil kursus dasar ini, termasuk semua yang masih tidak mengerti bukti.

Jeff Burdges
sumber

Tidak, IIRC, pertemuan pertama saya dengan TM adalah Hopcroft dan edisi pertama Ullman. Tapi alasan saya mengajukan pertanyaan ini sebenarnya terkait dengan buku bagus Sipser, saya mengajar teori kompleksitas berdasarkan Sipser dan saya merasa itu akan lebih sederhana dan lebih bersih (tanpa bahan penting yang hilang) untuk saya dan siswa jika didasarkan pada multi -tape TMs. Semua detail teknis kecil tentang akses terbatas TM pita tunggal ini akan dihindari dan saya dapat membahas materi yang lebih menarik dalam waktu terbatas yang saya miliki. Sipser santai tentang menggunakan tesis Church-Turing,

Kaveh

jadi saya pikir santai tentang bagian ini juga bisa baik-baik saja. Pada bagian teorema hierarki waktu, ia menyebutkan bahwa faktor log tambahan tidak diperlukan jika kami memiliki beberapa kaset dan itu akan cukup ketat. Hal ini menyebabkan saya bertanya untuk melihat apakah ada alasan non-historis untuk menggunakan single-tape TM untuk kompleksitas waktu. Ini tidak lebih buruk daripada menggunakan kaset read-only terpisah untuk kompleksitas ruang (dan sekali lagi itu terutama karena satu pita TM tidak menangkap intuisi tentang kelas kompleksitas ruang kecil dengan baik).

Kaveh

Saya tidak melihat bagaimana seseorang akan memahami batas ruang sub-linear tanpa pita input terpisah.

$\;$

Ya, saya anggap SPACE dilakukan secara berbeda, sebagian karena Anda akan melakukan batasan sublinear, yang mungkin tidak akan Anda lakukan untuk WAKTU. Saya berdebat untuk berlangganan WAKTU atau melakukan apa pun yang dilakukan Sipser untuk SPACE jika Anda ingin melakukannya dengan cara ini, tentu saya ingin berbicara tentang WAKTU atau WAKTU_1 atau apa pun sebelum mesin multi-tape.

Jeff Burdges

Menariknya, Sipser mengatakan hanya "Mesin Turing" ketika mendefinisikan SPACE (f (n)) tetapi kemudian mengubah definisi ketika membahas fungsi sublinear f, memberikan latihan pada kesetaraan untuk superliner f. Saya sudah mengajarkan materi ini dari Sipser sebelumnya. Saya belum terlalu memikirkannya saat itu, tetapi saya senang sekarang.

Jeff Burdges

Mesin Turing asli diuraikan menggunakan satu pita:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

Jadi ketika Anda menyatakan dalam pertanyaan Anda, ini terutama karena alasan historis. Selain itu, selalu ada kecenderungan untuk bertanya apa model paling sederhana yang dapat melakukan sesuatu ...

Juga, karena topik ini biasanya diajarkan secara sangat formal, secara teknis lebih mudah untuk menggambarkan mesin pita tunggal daripada mesin dua pita.

Lihat juga:

http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html

Sariel Har-Peled
sumber