Mengapa pita itu bukan bagian dari definisi Mesin Turing?

Saya bertanya-tanya mengapa kaset itu bukan bagian dari definisi formal dari Mesin Turing. Pertimbangkan, misalnya, definisi formal mesin Turing di halaman Wikipedia . Definisi, mengikuti Hopcroft dan Ullman, meliputi: himpunan terbatas status , alfabet pita Γ , simbol kosong b ∈ Γ , keadaan awal q 0 ∈ Q , himpunan status akhir F ⊆ Q , dan transisi fungsi δ : ( Q ∖ F ) × Γ → Q × Γ $Q$ $\Gamma$$b \in \Gamma$$q_0\in Q$$F\subseteq Q$ . Tidak ada yang merupakan rekaman itu sendiri.$\delta:(Q\backslash F)\times \Gamma\rightarrow Q\times\Gamma\times\{L,R\}$

Mesin Turing selalu dianggap bekerja pada pita, dan fungsi transisi diartikan sebagai menggerakkan kepalanya, mengganti simbol dan mengubah keadaan. Jadi, mengapa rekaman itu ditinggalkan dari definisi matematika dari mesin Turing?

Dari apa yang saya lihat, definisi formal itu sendiri sepertinya tidak menyiratkan bahwa Mesin Turing beroperasi seperti yang sering dijelaskan secara informal (dengan kepala bergerak di sekitar pada kaset). Atau apakah itu?

Untuk secara formal mendefinisikan turunan dari mesin Turing (bukan konsep umum) Anda tidak perlu secara eksplisit menyebutkan kaset itu sendiri, atau isinya. Untuk menunjukkan konfigurasi mesin khusus ini, atau perhitungan yang dilakukan olehnya, saat itulah Anda memerlukan beberapa bentuk notasi untuk menggambarkan isi rekaman itu.

Ini agak abu-abu, tapi saya akan mengatakan definisi memisahkan model dari instance . Jika Anda ingin memiliki ide sederhana, pikirkan perangkat keras vs perangkat lunak.

The Model adalah hardware: adalah satu kepala. Ada satu kaset. Kaset itu tak terbatas di satu sisi dan berisi kosong (di samping input). Kepala bisa bergerak selangkah demi selangkah.

The contoh adalah perangkat lunak: diktat masukan apa rekaman itu memegang di awal, fungsi negara / transisi menceritakan bagaimana bergerak kepala dan bagaimana mesin "karya". Status akhir memberi arti keberhasilan / kegagalan.

Kedua parameter dapat dikonfigurasi --- keduanya dapat diubah. Model alternatif ada dengan dua kaset, dua kepala, kaset dua sisi, kaset non-kosong, dll. Tapi begitu Anda memperbaiki model, Anda perlu menyelesaikan parameter "yang dapat dikonfigurasi" lainnya, karena jumlah status yang mungkin, dan fungsi transisi .

$P$$M$$pattern$

Di sini sudah ada jawaban yang bagus, tetapi saya mencoba membuat jawaban yang ringkas.

Definisi tidak boleh berlebihan atau bertele-tele.

Memang, definisi mesin Turing mendefinisikan abstraksi tape juga. Q0 - adalah awal dari rekaman itu. Alfabet adalah isi dari rekaman itu. Dan δ: (Q ∖ F) × Γ → Q × Γ × {L, R} menyatakan bahwa kaset telah kiri dan kanan dan tak terhingga di kedua arah.

Jadi, tape, head, bergerak hanya representasi ramah-manusia dari model, mereka sudah dalam model matematika , tetapi mereka bukan model formal sendiri.

Les memberikan jawaban yang ringkas dan benar: definisi matematika setepat mungkin, dan secara eksplisit memasukkan rekaman tak terbatas ke dalam definisi mesin Turing akan membuat definisi itu jauh lebih singkat, jadi kami tidak.

Ini tidak menjawab pertanyaan: mengapa ? Bagaimana definisi mengecualikan rekaman tak terbatas ketika kita membutuhkannya?

Jawabannya: kita tidak. Dalam arti tertentu, mesin Turing sebenarnya tidak membutuhkan kaset tanpa batas, dan definisi mereka membuat ini menjadi jelas.

Menurut definisi, perpindahan mesin Turing membawa mesin dari satu konfigurasi ke konfigurasi lainnya; konfigurasi mencakup string hingga , yang kami anggap sebagai fragmen terbatas dari kaset tertulis. Setiap gerakan menggerakkan kepala kaset dengan satu posisi atau menimpa simbol di bawah kepala kaset. Namun - dan ini sangat penting untuk operasinya:

• $b$
• kita bisa sering melakukannya tanpa batas .

$n$$n$

Salah satu cara pengulangan kata ini adalah dengan mengatakan: mesin beroperasi pada pita tanpa batas, seluruhnya diisi dengan kertas kosong, kecuali untuk fragmen terbatas tempat kepala kasetnya berada. Inilah yang dikatakan sebagian besar penjelasan.

Cara lain untuk mengulangi ini adalah dengan mengatakan: mesin beroperasi pada pita terbatas, diperpanjang dengan kosong setiap kali kepalanya bergerak dari pita di kedua ujungnya.

Ini adalah kedua cara yang valid untuk membuat konsep bagaimana mesin beroperasi: dalam kedua kasus, jika Anda benar-benar memiliki mesin yang beroperasi seperti itu, itu akan benar menerapkan mesin Turing.

Jika yang Anda minati adalah mengajarkan siswa bagaimana mesin Turing bekerja, mungkin tidak masalah konseptualisasi mana yang Anda pilih.

Namun, saya pikir konseptualisasi pertama adalah kesalahan, karena dua alasan:

• Itu tidak realistis . Kita sebenarnya tidak bisa membangun mesin dengan pita tak terbatas. Kita dapat membangun mesin dengan pita terbatas yang diperpanjang berdasarkan permintaan.
• Ini berlawanan dengan intuisi. Kami tidak menganggap mesin yang melakukan tugas secara sewenang-wenang sering kali mengandung sumber daya yang tak terbatas. Misalnya, kami tidak menganggap mesin fotokopi berisi kertas fotokopi dalam jumlah tak terbatas. Mesin Turing memodelkan aktivitas komputasi. Mereka memodelkan apa yang akan terjadi jika kami mengganti komputer (yang, pada saat penemuannya, adalah seorang wanita yang melakukan perhitungan di atas kertas) dengan mesin yang mampu melakukan perhitungan yang dapat diprogram secara sewenang-wenang. Kami tidak menganggap wanita itu mengandung kertas yang tak terbatas. Alih-alih, kami menganggap ia akan diberi kertas dalam jumlah berapa pun yang ia butuhkan, dan kami menganggap kegagalan untuk melakukannya sebagai kegagalan lingkungan, daripada mengatakan wanita seperti itu tidak mungkin ada. Mengapa tidak melakukan hal yang sama untuk mesin?
• Itu mengundang kesimpulan yang menyesatkan. Saya sudah sering melihat ini. Misalnya:
  • Orang mengatakan mesin Turing sebenarnya tidak bisa dibangun, sementara mesin negara hingga bisa. Yah, kita tidak bisa membangun mesin negara berhingga besar yang sewenang-wenang seperti kita tidak bisa menyediakan jumlah rekaman sewenang-wenang ke mesin Turing.
  • Orang mengatakan mesin Turing tidak memodelkan komputer dengan benar, sedangkan mesin negara terbatas melakukannya. Ini berfungsi untuk membuat poin penting: jika semua yang kita tertarik menggunakan mesin untuk memutuskan bahasa input, maka komputer yang hanya beroperasi pada penyimpanan internal (tetap) dapat sepenuhnya mengimplementasikan mesin keadaan terbatas apa pun hingga ukuran tertentu, sementara itu tidak dapat sepenuhnya menerapkan sebagian besar mesin Turing, karena akan kehabisan penyimpanan internal bagi banyak dari mereka. Namun, ini sering digeneralisasi dengan mengatakan: komputer adalah mesin negara yang terbatas, yang menyesatkan:
    • Itu tidak melukiskan gambaran realistis dari kebanyakan pemrograman komputer. Memang, pemrograman dataflow sebenarnya didasarkan pada mesin negara yang terbatas, tetapi pemrograman imperatif tradisional tidak; menggunakan program yang lebih dekat dengan mesin contoh Turing.
    • Dalam praktiknya, komputer juga berinteraksi dengan sumber input, output, dan penyimpanan eksternal yang ukurannya tidak tetap.
    • Mesin Turing tidak seharusnya memodelkan komputer sejak awal; mereka memodelkan komputasi sewenang-wenang.

Singkatnya: gagasan mesin Turing menggunakan atau mengandung pita tak terbatas berfungsi untuk menekankan titik teknis yang penting, tetapi itu tidak selalu merupakan cara paling intuitif untuk berpikir tentang mesin Turing, dan itu mengundang kesimpulan yang salah. Gunakan dengan hati-hati.