Perbedaan antara mesin turing dan mesin keadaan terbatas?

27

Saya sedang melakukan presentasi tentang mesin Turing dan saya ingin memberikan latar belakang tentang FSM sebelum memperkenalkan Mesin Turing. Masalahnya adalah, saya benar-benar tidak tahu apa yang SANGAT berbeda satu sama lain.

Inilah yang saya tahu berbeda:

FSM memiliki status berurutan tergantung pada kondisi terkait yang dipenuhi sementara mesin Turing beroperasi pada "Pita" tanpa batas dengan kepala yang membaca dan menulis.

Ada lebih banyak ruang untuk kesalahan dalam FSM karena kita dapat dengan mudah jatuh pada keadaan tanpa akhir, sementara itu tidak begitu banyak untuk mesin Turing karena kita dapat kembali dan mengubah banyak hal.

Tapi selain itu, saya tidak tahu banyak perbedaan yang membuat mesin Turing lebih baik daripada FSM.

Bisakah kamu menolongku?

terminology turing-machines finite-automata machine-models Julio Garcia
sumber
2
Tidak sulit untuk google untuk "FSM vs. Turing Machine"! Itulah bagian yang menyenangkan dari melakukan riset Anda sendiri. Perbedaan utama adalah bahwa mesin Turing memiliki "memori" yang tak terbatas, tetapi FSM tidak.
Dai
Ok, saya sedikit curang di sana>.> ;; Gotcha! Terima kasih!
Julio Garcia
3
argumen tentang "kesalahan" tidak benar. Coba wikipedia dan buku pelajaran. Lihat apa perbedaan mendasar mereka, tujuan penggunaan masing-masing (misalnya ketika kita tidak dapat memilih FSM daripada TM?) Dan hubungannya.
Parham
@ MahmoudAlimohamadi yang saya maksud adalah ada peluang yang lebih besar bagi seorang fsm untuk mendarat dalam keadaan tanpa akhir.
Julio Garcia
@Dai: Lebih tepat mengatakan bahwa Mesin Turing dapat menggunakan memori dalam jumlah besar secara sewenang - wenang . Jumlah yang digunakan tidak pernah terbatas.
reinierpost

Jawaban:

24

Perbedaan utama antara bagaimana DFA (Deterministic Finite Automaton) dan TM bekerja dalam hal bagaimana mereka menggunakan memori.

Secara intuitif, DFA sama sekali tidak memiliki memori "goresan"; konfigurasi DFA sepenuhnya diperhitungkan oleh negara di mana ia saat ini menemukan dirinya, dan kemajuannya saat ini dalam membaca input.

Secara intuitif, TM memiliki memori "gores" dalam bentuk pita; konfigurasi TM terdiri dari kondisi saat ini dan konten rekaman saat ini, yang dapat diubah oleh TM saat dijalankan.

DFA dapat dianggap sebagai TM yang tidak mengubah simbol pita atau menggerakkan kepala ke kiri. Pembatasan ini membuat tidak mungkin untuk mengenali bahasa tertentu yang dapat diterima oleh TM.

Perhatikan bahwa saya menggunakan istilah "DFA" daripada "FSM", karena, secara teknis, saya akan menganggap TM sebagai mesin negara-terbatas, karena TM secara definisi memiliki sejumlah negara terbatas. Perbedaan antara DFA dan TM adalah dalam jumlah konfigurasi, yang sama dengan jumlah negara untuk DFA, tetapi sangat bagus untuk TM.

Patrick87
sumber
Ah, mengerti. Satu pertanyaan mengenai bagian "tidak ada ingatan": Saya melihat contoh mesin penjual otomatis yang menambahkan koin yang dikeluarkan. Bagaimana mereka tahu berapa banyak uang yang ada jika tidak memiliki memori?
Julio Garcia
@JulioGarcia Sulit dikatakan tanpa tahu persis apa yang Anda lihat. Ada mesin Moore dan Mealy yang dapat menampilkan simbol pada transisi. Aktivitas mesin penjual otomatis mungkin dimodelkan dengan lebih baik oleh salah satu mekanisme itu. Sebuah vanilla DFA hanya menerima dan menolak string ... mesin penjual otomatis harus "menerima" setiap "string" mata uang. Bergantung pada bagaimana Anda memodelkan efek samping tambahan dari memberikan perubahan, jenis memori awal yang dibutuhkan mungkin tidak ada atau akses acak tanpa batas.
Patrick87
Tanpa melihat teladan Anda, saya tidak dapat sepenuhnya yakin, tetapi saya memiliki dua tebakan. Salah satunya adalah tidak tahu berapa banyak uang yang ada: hanya mengasumsikan ada cukup. Anda tidak ingin membuat mesin penjual otomatis seperti itu, tetapi itu masih merupakan contoh konsep yang berguna. Kemungkinan lain adalah bahwa itu bukan FSA "murni": itu terhubung ke sensor yang bisa mendapatkan data ini dari "luar" mesin entah bagaimana. Mesin tidak tahu atau tidak peduli dari mana data berasal, dan tidak bisa menyimpan apa pun di sensor (jadi itu bukan "memori"), tetapi masih bisa bertindak berdasarkan apa yang dilihatnya di sana.
The Spooniest
16

Turing Machines menggambarkan kelas bahasa yang jauh lebih besar, kelas bahasa yang berulang secara berulang. Mesin negara yang terbatas menjelaskan kelas bahasa biasa.

Mesin negara yang terbatas tidak memiliki "memori", itu dibatasi oleh negara.

Mesin keadaan terbatas adalah mesin Turing terbatas di mana kepala hanya dapat melakukan operasi "baca", dan selalu bergerak dari kiri ke kanan.

Ambil bahasa ini sebagai contoh:

L={aibi| i>=0}

Karena mesin status terbatas terbatas dalam arti bahwa mereka tidak memiliki memori, FSM yang menerima L tidak dapat dibangun.

Untuk meringkas:

Mesin negara terbatas menjelaskan kelas kecil bahasa di mana tidak ada memori yang diperlukan.

Turing Machines adalah deskripsi matematis dari sebuah komputer dan menerima kelas bahasa yang jauh lebih besar daripada FSM.

Mesin Turing memiliki daya komputasi lebih dari FSM. Ada tugas-tugas yang tidak dapat dilakukan FSM, tetapi Turing Machines dapat melakukannya.

mrjasmin
sumber
3

Saya memiliki keraguan yang sama dan saya melihat dua video yang sangat mencerahkan dan satu penjelasan tentang Quora sebagai berikut:

Mesin keadaan terbatas hanyalah seperangkat keadaan dan transisi. Satu-satunya memori yang dimilikinya adalah statusnya. Dengan demikian, jumlah status memori adalah ... terbatas.

Mesin Turing adalah mesin keadaan terbatas ditambah memori tape. Setiap transisi dapat disertai dengan operasi pada pita (pindahkan, baca, tulis).

Saya telah mengerti dari itu bahwa mesin turing menggunakan / memiliki mesin negara yang terbatas sebagai bagian dari prosedur operasinya, ditambah menambahkan beberapa memori yang dapat diedit ke dalamnya.

Silakan tonton juga dua video itu, semuanya mencerahkan!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

pengguna5193682
sumber
2

Sejauh yang saya mengerti perbedaan antara (model standar) Turing dan (model standar) Mesin Mealy:

  • Mesin Turing membaca dan menulis pada kaset yang sama vs. Mesin Mealy membaca pada satu tape input dan menulis pada tape output yang lain
  • Mesin Turing dapat mengubah "arah kaset" (lanjutkan ke kiri atau ke kanan [atau berhenti]) vs Mesin Mealy hanya dapat melanjutkan ke kanan (itulah sebabnya tidak ada arah yang ditetapkan {L, R, H} dalam fungsi transisi dari Mesin Mealy [ini secara implisit {R}, yang berarti tidak ada pilihan sama sekali])
  • Mesin Turing dapat berhenti pada sel rekaman apa pun vs. Mesin Mealy membaca input lengkap dan kemudian berhenti menerima atau menolaknya
Michael Klaube
sumber
-3

Mesin Turing dapat menyimpan, sebagai bagian dari kaset, hal-hal yang ingin diingatnya.

richard mullins
sumber
5
Tidak jelas apa yang Anda maksud dengan "itu" tetapi mesin Turing dan FSM dapat melakukan ini sehingga tidak ada perbedaan.
David Richerby
@DavidRicherby Tapi FSM hanya dapat menyimpan jumlah yang telah ditentukan, sedangkan mesin Turing dapat menyimpan sebanyak yang mereka inginkan. Itu adalah perbedaan mendasar.
Gilles 'SANGAT berhenti menjadi jahat'
1
@Gilles Setuju tapi bukan itu yang dikatakan jawabannya.
David Richerby