Cara memetakan kaset Turing Machine "k-tape" ke dalam satu tape Turing Machine "1-tape"

Saya membaca Sipser dan saya merasa sulit untuk memahami apa prosesnya sehingga jika Anda memberi saya mesin Turing dengan kaset k, saya dapat memuntahkan mesin Turing yang setara dengan hanya satu kaset. Sebuah contoh akan menyenangkan. Sebenarnya, contoh yang menunjukkan bagaimana untuk pergi dari TM yang memiliki kaset ke yang memiliki 1 kaset adalah apa yang saya benar-benar cari. Saya belum dapat menemukan satu sejauh ini. Saya juga tidak mencari bukti.$k$

Sebuah jawaban tanpa malu-malu disalin dari diri saya :

Mesin Turing multi-tape sebagian besar sama dengan mesin single-tape, kecuali kami memiliki fungsi transisi yang diperluas mana k adalah jumlah kaset. Jadi di setiap negara, fungsi transisi membaca isi dari setiap rekaman, pindah ke keadaan baru, (mungkin) menulis sesuatu di setiap pita dan menggerakkan setiap kepala - seperti TM biasa, kecuali sekarang kita memiliki lebih banyak hal untuk dibaca, tulis dan bergerak.$Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$$k$

Seperti pertanyaan Anda menyarankan, mesin seperti itu dapat disimulasikan oleh single-tape TM. Bahkan lebih baik, ini dapat dilakukan hanya dengan perlambatan kuadratik (jadi untuk kelas yang tertutup secara polinomi, itu sudah cukup untuk berbicara tentang mesin pita tunggal).

Buktinya, ini agak terlibat, dan mudah tersedia dengan pencarian web sederhana, jadi saya hanya akan membuat sketsa pemetaan kunci kaset ke satu kaset.$k$

Ide dasarnya sangat mudah; kami cukup menambahkan beberapa simbol baru dan melacak setiap rekaman dan kepala satu demi satu. Pada setiap langkah dalam perhitungan, kami hanya dapat mengunjungi sejumlah terbatas kaset mana pun, jadi kami hanya perlu menyimpan informasi sebanyak ini tentang setiap kaset. Jadi untuk setiap kami menambahkan simbol baru γ _ ke Γ yang akan menunjukkan di mana kepala (untuk setiap pita) berada pada setiap titik dalam perhitungan. Kami juga memperkenalkan karakter pemisah # ke Γ yang akan menunjukkan awal dan akhir dari kaset "virtual". Input yang diberikan ω = ω 1 ... ω $\gamma \in \Gamma$$\underline{\gamma}$$\Gamma$$\#$$\Gamma$$\omega = \omega_{1}\ldots\omega_{n}$(kita dapat berasumsi bahwa bahkan pada mesin multi-tape semua input ada pada tape pertama - membuktikan mengapa latihan yang baik) pada mesin multi-tape, mesin single-tape kami akan memiliki input

$$\underbrace{\#\underline{\omega_{1}}\ldots\omega_{n}\#\underline{\sqcup}\#\underline{\sqcup}\#\ldots\#\underline{\sqcup}\#}_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots$$

$k$

Contoh mudah-mudahan:

$\Sigma=\{0,1\}$$\Gamma=\{0,1,\sqcup\}$$\omega=10101$

$$\begin{array}{lc} \text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$ $\wedge$

Untuk membangun mesin single-tape gabungan, kita perlu menambahkan simbol baru ke alfabet tape:

1. Kami membutuhkan simbol yang akan menunjukkan awal dan akhir dari kaset yang disimulasikan
2. $\Gamma$

$\Gamma' =\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\#\}$

$$\#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$ $\wedge$) dan kepala simulasi dari 3 kaset simulasi (karakter yang digarisbawahi). Tentu saja rekaman itu meluas tak terbatas ke kanan seperti biasa. Saya juga curang secara ringan dengan menggerakkan kepala kaset ke karakter pertama pada string pertama; ketat itu harus dimulai pada sel paling kiri, tetapi ini adalah teknis yang sepele.

$\#$

$1$$1$$0$$1$

$1$

$$\begin{array}{lc} \text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$

$0$

$$\begin{array}{lc} \text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$

$\Gamma'$

$$\#1\underset{\wedge}{\underline{0}}101\#1\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$

Setelah langkah kedua:

$$\#10\underset{\wedge}{\underline{1}}01\#1\underline{\sqcup}\#1\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$

Tentu saja ini adalah pandangan tingkat tinggi dari proses - saya belum berusaha menjelaskan bagaimana membangun negara, atau bagaimana setiap kaset simulasi menjadi lebih lama (untuk ini, Anda perlu sedikit rutin yang memeriksa jika Anda telah mengalami akhir kaset simulasi, kemudian gerakkan semuanya ke kanan satu langkah dan peras dalam blank baru - yaitu hanya menambahkan sel-sel kaset simulasi ketika dibutuhkan).