Mesin Turing - pita tak terbatas dalam satu atau dua arah

Saya telah melihat mesin turing beeing diwakili dengan kaset tak terbatas dalam satu, dan dalam dua arah. Apakah ada perbedaan dalam kekuatan mesin turing tersebut, atau apakah pada dasarnya setara? Di kepala saya, saya pikir mereka setara, karena saya kira harus ada beberapa cara untuk mewakili pita tak terbatas dua arah sebagai pita tak terbatas satu arah, tetapi saya tidak bisa menemukan bukti atau contoh.

Mereka setara dalam kekuatan komputasi. Apa pun yang dapat dihitung oleh salah satu dari dua jenis mesin Turing ini, dapat dihitung oleh jenis lainnya. Mari kita lihat bagaimana mensimulasikan mesin Turing dengan pita tak terbatas ganda, pada mesin Turing dengan pita tak terbatas tunggal.

Idenya adalah untuk memotong pita tak terbatas dua kali lipat Anda menjadi dua, sehingga Anda memiliki dua kaset tunggal tak terbatas, yang satu kiri dan yang kanan, yang akhirnya akan Anda gabungkan. Anda dapat menandai ujungnya dengan lokasi pita yang berisi simbol EOF khusus. Anda juga menduplikasi kontrol hingga Anda, sehingga Anda memiliki dua kontrol negara hingga identik. Anda berasumsi bahwa Anda memiliki perangkat kontrol lewat (lihat di bawah), sehingga, ketika mesin kiri mencoba melampaui ujung kanan rekamannya, ia melewati kontrol ke mesin kanan, pada posisi rekaman paling kiri (tepat sebelum ujung kiri pita kanan). Dan sebaliknya, ketika mencoba untuk melewati ujung kiri pita kanan.

Sekarang, untuk membedakan mesin kiri dan kanan, kami mengubah nama negara dan simbol rekaman, dengan mengindeksnya dengan$R$$L$

Sekarang kita siap untuk menggabungkan dua kaset setengah, misalnya dengan melipat yang kanan ke yang kiri. Untuk itu Anda membalik setengah pita kanan, dan Anda berhati-hati untuk memodifikasi sesuai transisi, bertukar kanan ke kiri dan kiri ke kanan. Kemudian Anda menggabungkan kedua kaset menjadi satu kaset yang berisi pasangan simbol, yang kiri dan yang kanan, masing-masing komponen mungkin kosong.

Anda memodifikasi lagi transisi dari kedua mesin, sehingga transisi kiri (resp. Kanan) menggunakan dan memodifikasi hanya bagian kiri (resp. Kanan) dari pasangan pada pita. Kemudian Anda menggabungkan kontrol dari dua mesin dengan serikat set sederhana masing-masing untuk negara, dan untuk transisi.

Anda menambahkan satu set transisi untuk setiap negara yang ada, sehingga ketika simbol rekaman adalah EOF, itu kembali ke lokasi rekaman sebelumnya (lokasi non-EOF pertama) dan negara berubah ke pasangan kiral: jika itu adalah kiri (resp. kanan) menyatakan, itu berubah ke kanan (resp. kiri) rekannya. Itu adalah perangkat kontrol lewat.

Saya mungkin lupa detail, tetapi ini adalah ide umum dari konstruksi. Buktinya dibiarkan sebagai eksekusi.

Tentu saja, rekaman awal (input) harus dimodifikasi. Tapi itu bisa dibuat sederhana dengan menempatkan input (jika terbatas) sepenuhnya di sisi kiri (yang tidak terbalik) dari potongan pita.

Kemudian Anda menyingkirkan driver sekrup karena mungkin berbahaya bagi anak-anak.

PS Saya hanya menunjukkan bahwa rekaman tak terbatas ganda dapat disimulasikan dengan pita tak terbatas tunggal. Kebalikannya tampak terlalu jelas.