Menghitung panjang input pada mesin Turing satu-pita

Sehubungan dengan pertanyaan ini, terpikir oleh saya untuk bertanya-tanya: apa kompleksitas waktu untuk satu mesin single-head Turing untuk menghitung panjang inputnya? Untuk lebih spesifik, misalkan alfabet tape adalah , inputnya adalah string dalam dikelilingi oleh blank, mesin dimulai pada simbol input paling kiri, dan itu harus berakhir pada simbol paling kiri dari string di $\{0,1,b\}$ $(0+1)^*$ $(0+1)^*$ (lagi-lagi dikelilingi oleh blank) yang memberikan representasi biner dari panjang input. Ini juga dapat dianggap sebagai masalah mengubah nomor dari unary ke binary.

Sangat mudah untuk menyelesaikan ini pada mesin dua-pita atau mesin dua-kepala dalam waktu linier (cukup pindai input dengan satu kepala saat menggunakan kepala lainnya untuk berulang kali menambah penghitung; peningkatan adalah operasi waktu diamortisasi konstan). Tetapi solusi single-head yang bisa saya buat hanyalah (misalnya berulang kali menambah penghitung dan kemudian menggesernya dengan satu posisi di sepanjang pita). Apakah ada batas bawah yang cocok? $O(n\log n)$

Saya mencoba beberapa pencarian tetapi frasa seperti "satu kepala" dan "panjang input" sangat umum sehingga menyulitkan untuk mencari literatur untuk hasil yang diketahui tentang masalah ini.

turing-machines David Eppstein
sumber

Menarik .. Ini kurang jelas dari yang seharusnya. Saya ingin tahu apakah ada hubungan antara batas bawah untuk ini dan batas bawah untuk simulasi TM yang tidak disadari. (Setiap TM yang memecahkan masalah ini akan, secara definisi, tidak menyadari (atau memiliki kode yang tidak perlu).)

Daniel Apon

Jawaban:

Ini tidak dapat dihitung dalam waktu . $o(n\lg n)$

Biarkan menjadi mesin yang diberi string input berhenti dengan ukuran ditulis dalam biner pada kaset. $M$ $x$ $x$

Kita dapat menambahkan DFA sederhana (zero-space linear-time) ke untuk memeriksa apakah ukuran input adalah kekuatan dua: cukup periksa bahwa bit pertama adalah 1 dan sisanya nol. $M$

Mari kita asumsikan bahwa menjalankan waktu . Kemudian kita dapat memutuskan dalam waktu bahwa ukuran input adalah kekuatan dua. Dengan kata lain, bahasa berikut dapat dipilih dalam . Ini mengikuti dari $M$ $o(n \lg n)$ $o(n \lg n)$ $\mathsf{DTime}(n \lg n)$

L = {0^{i} ∣ \exists k i = 2^{k}}

$L = \{ 0^i \mid \exists k \ i = 2^k\}$

bahwa

harus teratur. Tetapi mudah untuk memeriksa bahwa bahasanya tidak teratur. Jadi

tidak dapat berjalan dalam waktu

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$

L

$L$

M

$M$

o (n \lg n)

$o(n \lg n)$

Kaveh
sumber

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n\lg n))=\mathsf{Reg}$

D T i m e (n \lg n) = R e g

$\mathsf{DTime}(n \lg n) = \mathsf{Reg}$

Terima kasih untuk petunjuknya, saya telah melihat dalam "Teori Rekursi Klasik" vol. II Karena fakta bahwa itu telah berubah, tidak begitu jelas bagi saya. Sebagai contoh, buku Sipser menggunakan single-tape TM untuk mendefinisikan kelas kompleksitas waktu, tetapi buku Hopcroft-Ullman dan Arora-Barak dan Goldreich yang terbaru menggunakan multitape TM.

Bruno

@ Bruno, saya pikir apa definisi DTime yang lebih umum lebih rumit. Misalnya klaim yang umum dinyatakan bahwa "teorema hierarki waktu tidak dikenal ketat" hanya berlaku untuk mesin pita tunggal, karena mesin dua pita itu dikenal ketat sejak 1982.

Kaveh

D T i m e

$\mathsf{DTime}$