Alfabet dari mesin Turing single-tape

Dapatkah setiap fungsi yang dapat dihitung dalam waktu pada mesin Turing pita tunggal menggunakan alfabet ukuran dapat dihitung dalam waktu pada mesin Turing single-tape menggunakan alfabet ukuran (katakanlah, dan kosong)? $f : \{0,1\}^* \to \{0,1\}$ $t$ $k = O(1)$ $O(t)$ $3$ $0,1,$

(Dari komentar di bawah oleh OP). Perhatikan input ditulis menggunakan , tetapi mesin Turing menggunakan alfabet ukuran dapat menimpa simbol input dengan simbol dari alfabet yang lebih besar. Saya tidak melihat cara menyandikan simbol dalam alfabet yang lebih besar dalam alfabet yang lebih kecil tanpa harus menggeser input yang membutuhkan waktu . $0,1$ $k$ $n^2$

computability turing-machines Manu
sumber

Perhatikan input ditulis menggunakan , tetapi mesin Turing menggunakan alfabet ukuran dapat menimpa simbol input dengan simbol dari alfabet yang lebih besar. Saya tidak melihat cara menyandikan simbol dalam alfabet yang lebih besar dalam alfabet yang lebih kecil tanpa harus menggeser input yang membutuhkan waktu .

0, 1

$0,1$

k

$k$

n^{2}

$n^2$

Manu

@ Emanuele: Anda harus mengedit pertanyaan dan menekankan aspek ini; selain itu kedengarannya persis seperti latihan buku teks standar ...

Jukka Suomela

@ Tsuyoshi, saya pikir Anda salah paham pertanyaannya.

Suresh Venkat

@Jukka: Pada mesin Turing satu-pita, semua yang dapat dihitung dalam waktu sebenarnya adalah bahasa biasa.

o (n \log n)

$o(n \log n)$

Kristoffer Arnsfelt Hansen

@ Bel: Hasil yang Anda kutip dari Arora dan Barak mengatasi masalah utama di sini karena dalam model mereka (yang cukup standar untuk TM multi-tape), mereka memiliki tape input terpisah, hanya baca.

Joshua Grochow

Jawaban:

Sebagian jawaban jika TM berjalan di $o( |x| \log |x|)$

Jika TM4 adalah TM 4-simbol (dengan alfabet ) yang menghitung , yaitu memutuskan bahasa in $\Sigma_4 = \{\epsilon,0,1,2 \}$ $f:\{0,1\}^* \to \{0,1\}$ $L = \{ x | f(x) = 1 \}$ $(o( |x| \log |x|))$

Satu kompleksitas deterministik linear-waktu adalah $1DLIN = 1DTime(O(n))$

Hennie membuktikan (1) bahwa $REG = 1DLIN$
Kobayashi membuktikan (2) bahwa $REG = 1DTime(o(n \log n))$

Jadi adalah teratur, dan jelas masih teratur lebih dari alfabet $L$ $\Sigma_3 = \{\epsilon,0,1\}$

Jadi ada DFA yang memutuskan L dan hanya menggunakan simbol di . TM3 3-simbol satu-pita dapat dibangun langsung dari DFA dan memutuskan L menggunakan input murni yang sama dari TM4 asli . $\Sigma_3$

... Anda tidak dapat membangunnya langsung dari TM4, tetapi TM3 ada.

Jika TM4 berjalan di maka Anda dapat menggeser input dan melakukan konversi langsung dari TM4 ke TM3. $\Omega(n^2)$

Seperti disebutkan dalam komentar, kasus yang sulit adalah ketika TM4 berjalan di . $\Omega(n\log n) \cap o(n^2)$

(1) Perhitungan mesin Turing Hennie, One-tape, off-line (1965)

(2) Kobayashi, Pada struktur hierarki waktu mesin Turing satu-pita nondeterministic (1985)

Marzio De Biasi
sumber

Poin tentang sudah dicatat oleh Kristoffer Arnsfelt Hansen dalam komentar di bawah pertanyaan. Kasus yang sangat menarik adalah .

o (n \log n)

$o(n\log n)$

Ω (n \log n) \cap o (n^{2})

$\Omega(n\log n) \cap o(n^2)$

Kaveh

Anda benar, saya tidak memperhatikan komentar Kristoffer. Saya dengan buruk mengungkapkan kasus yang menarik (saya tidak tahu bagaimana membuktikannya), jadi saya memperbarui jawabannya.

Marzio De Biasi

@ Kaveh: Bagaimana dengan - mesin waktu untuk masalah janji? Apakah kita sudah tahu cara mengonversi, misalnya, mesin apa pun yang memecahkan masalah janji dalam waktu ? Saya tidak tahu bagaimana melakukannya, dan koneksi ke bahasa biasa tidak lagi berlaku (kecuali saya salah besar).

o (n \log n)

$o(n \log n)$

O (n)

$O(n)$

Jukka Suomela

@ Kaveh: Tidak bisakah Anda mengambil masalah yang bukan bahasa biasa tetapi dapat diselesaikan dengan mesin Turing dalam, misalnya, putaran , dan mendefinisikan masalah janji sebagai berikut: yes-instance terdiri dari string diikuti oleh bit padding; no-instance terdiri dari string diikuti oleh bit padding. Masalah janji dapat dipecahkan dalam waktu , dan tidak dapat dipecahkan dengan menggunakan mesin keadaan terbatas.

L

$L$

O (n^{2})

$O(n^2)$

x \in L

$x \in L$

| x |^{2}

$|x|^2$

x \notin L

$x \notin L$

| x |^{2}

$|x|^2$

O (n)

$O(n)$

Jukka Suomela

@ Kaveh: Saya kira argumen intuitif gagal karena alasan berikut: Ya, ada masalah tidak dijanjikan yang diselesaikan oleh mesin yang sama. Namun, waktu menjalankan mesin mungkin setinggi untuk input tertentu. (Secara intuitif, mesin tidak dapat memverifikasi bahwa ada padding yang cukup, dan karenanya "untuk bermain aman" itu harus mengasumsikan bahwa ada padding yang cukup setelah awalan . Kemudian ia membuang waktu untuk menentukan apakah , dan ini terlalu banyak jika, misalnya, kami hanya memiliki bit padding.)

Θ (n^{2})

$\Theta(n^2)$

x

$x$

Θ (| x |^{2})

$\Theta(|x|^2)$

x \in L

$x \in L$

Θ (| x |)

$\Theta(|x|)$

Jukka Suomela

-4

~~Untuk semua ukuran alfabet lebih besar dari , runtimes hanya berubah oleh faktor konstan karena untuk semua . $1$ $\log_k(x) \in \Theta(\log_l(x))$ $k, l > 1$~~

~~Elaborasi:~~ Dalam timesteps, diasumsikan mesin Turing dapat memproses paling posisi / bit. Bit diambil dari alfabet -nary, wlog . Buat mesin Turing baru dengan mengganti setiap transisi dengan transisi; setiap bit lama dikodekan oleh bit di (kosong disediakan untuk menandai sel yang tidak digunakan). Perhatikan ini pada dasarnya adalah angka kode biner. $t$ $t$ $k$ $\{0,1,\dots,k-1\}$ $\lceil \log_2(k) \rceil$ $\lceil \log_2(k) \rceil$ $\{0,1\}$

Jelas, mesin Turing yang dihasilkan mengeksekusi paling banyak langkah . $\lceil \log_2(k) \rceil \cdot t \in \mathcal{O}(t)$

Tambahan: Argumentasi di atas terputus karena operasi yang menimpa simbol input dengan sedikit tidak dalam tidak dapat diterjemahkan secara langsung; input harus digeser. Ini dapat diubah dengan menerjemahkan input asli sebelum memulai perhitungan (pada dasarnya padding); ini dapat dilakukan dalam waktu , menghasilkan runtime total dari . $\{0,1\}$ $\mathcal{O}(n^2)$ $\mathcal{O}(n^2) + \lceil \log_2(k) \rceil \cdot t$

Akibatnya, hanya menggunakan dua simbol untuk pengkodean hasil antara tidak berdampak asimptotik jika , tetapi preprocessing mendominasi algoritma yang lebih cepat. Karena sebagian besar fungsi yang menarik ada di (misalnya menambahkan dua angka), orang mungkin menganggap masalahnya dapat diabaikan. $t(n) \in \Omega(n^2)$ $\Omega(n^2)$

Raphael
sumber

Sampai Anda meyakinkan saya mengapa ini seharusnya terjadi, saya akan menyimpannya.

Andrej Bauer

Saya ingin mendengar beberapa bukti untuk klaim Anda. Semua itu, hanya satu klaim.

Andrej Bauer

Oh, saya mengerti apa yang Anda maksud. Ok maaf Namun, pertanyaannya bukan tentang itu . Ini sedikit variasi.

Andrej Bauer

Saya pikir case dengan t = Ω (n ^ 2) adalah case yang mudah karena Anda dapat memberikan waktu untuk menggeser string input. Kasus esensial adalah ketika t = o (n ^ 2). Saya tidak tahu betapa pentingnya untuk mempertimbangkan single-tape TM dengan waktu (n ^ 2), tetapi pertanyaannya adalah tentang itu.

Tsuyoshi Ito

Pertanyaan asli sudah menyiratkan bahwa case mudah; karenanya saya tidak benar-benar melihat bagaimana jawaban ini menambahkan sesuatu yang baru ...

Ω (n^{2})

$\Omega(n^2)$

Jukka Suomela