Apakah bahasa ini dikenali oleh 3 simbol TM di O (n log n)?

Saya bermain dengan pertanyaan yang sangat menarik dan masih terbuka " Alfabet mesin Turing single-tape " (oleh Emanuele Viola) dan muncul dengan bahasa berikut:

$L = \{ x \in \{0,1\}^n \text{ s.t. } |x| = n = 2^m \text{ and } count1(x) = k * m; \; n,m,k \geq 1 \}$

di mana adalah jumlah s dalam string x. $count1(x)$ $1$

Misalnya, jika x = 01101111 maka n = 8, m = 3, k = 2; jadi $x \in L$

Bisakah L dikenali oleh Mesin Turing dengan satu pita dan 3 simbol alfabet dalam langkah ? $\{ \epsilon, 0, 1 \}$ $O(n \log{n})$

Jika kita menggunakan 4 simbol jawabannya adalah ya:

periksa apakah mengganti s dengan dan s dengan dan sekaligus simpan s di sebelah kanan; $|x|=2^m$ $0$ $\epsilon$ $1$ $2$ $m$ $1$
kemudian menghitung jumlah s modulo di . $2$ $m$ $O(n \log{n})$

Sebagai contoh:

....01101111....... input x  (|x| = 8 = 2^3)
000.021.1212.0001.. div 2, first sweep (000. can safely be used as a delimiter)
000.022.1222.00011. div 2, second sweep
000.022.2222.000111 div 2, third sweep --> m = 3 (= log(n) )
000..22.2222....111 cleanup (original 1s are preserved as 2)
000..22.2221102.... start modulo m=3 calculation
000..22.2210022.... mod 3 = 2
000..22.2000222.... mod 3 = 0
000..22.0012222.... mod 3 = 1
000..20112.2222.... mod 3 = 2
000..11122.2222.... ACCEPT

cc.complexity-theory turing-machines time-complexity Marzio De Biasi
sumber

Jika adalah bilangan alami yang diwakili oleh daripada selalu sama dengan dan ?

| x | = n = 2^{m}

$\vert x \vert = n = 2^m$

x

$x$

c o u n t 1 (x)

$count1(x)$

1

$1$

L = {10}

$L = \lbrace 10 \rbrace$

Marc Bury

Maaf | x | berarti panjang string x. Contoh: x = 01101111, n = 8, m = 3, k = 2, dan dengan demikian

x \in L

$x \in L$

Marzio De Biasi

Ngomong-ngomong, ini adalah kandidat yang sangat baik untuk pertanyaan Emanuele, karena itu ada di : ini tidak biasa oleh lemma pemompaan, jadi tidak mungkin , tetapi itu adalah .

Θ (n \log n)

$\Theta(n \log n)$

o (n \log n)

$o(n \log n)$

O (n \log n)

$O(n \log n)$

Joshua Grochow

Tidak bisakah Anda menggunakan ide yang sama dengan yang Anda miliki untuk case 4 simbol , dengan modifikasi berikut:

Selalu proseskan sepasang simbol secara bersamaan.
Dalam sapuan "div 2" Anda, tandai blok dua simbol sebagai "diproses" dengan memetakan . Anda masih memiliki tersedia sebagai "pemisah" yang dapat Anda gunakan di kedua ujungnya, dan Anda dapat memulihkan data asli dengan mudah. $(00, 01, 10, 11) \mapsto (\epsilon0, \epsilon1, 0\epsilon, 1\epsilon)$ $\epsilon\epsilon$
Gunakan trik serupa untuk langkah "mod 2".

Secara umum, Anda dapat memeras informasi pembukuan dalam jumlah besar secara sewenang-wenang dengan bantuan simbol ketiga dengan memroses simbol sekaligus. $O(1)$

Jukka Suomela
sumber

Kamu benar! ... sekarang saya curiga bahwa jawaban untuk pertanyaan Emanuele adalah ya ... tetapi masih terbuka sehingga mungkin tidak terlalu mudah untuk membuktikannya secara resmi :-( Terima kasih!

Marzio De Biasi

Apakah bahasa ini dikenali oleh 3 simbol TM di O (n log n)?

Jawaban: