Mengapa mesin Turing mengenali persis satu bahasa?

13

Saya mencoba memahami keberadaan bahasa yang tidak dikenali. Untuk mendapatkan ini, saya perlu tahu mengapa mesin Turing hanya mengenali satu bahasa, bukan beberapa. Kenapa ini?

turing-machines computation-models Anonim
sumber

12

Saya menduga Anda mungkin tidak memiliki gagasan yang jelas tentang apa yang kami maksud dengan "bahasa". Bisakah Anda mengatakan apa yang Anda yakini sebagai "bahasa"?

Eric Lippert

Mengapa Anda perlu tahu itu? Menurut Anda bagaimana hal itu dapat membuat perbedaan?

babou

29

Bahasa yang dikenali oleh mesin Turing, menurut definisi, adalah set string yang diterimanya. Ketika input diberikan ke mesin, itu diterima atau tidak. Setiap input tertentu ke mesin itu selalu diterima (dalam bahasa) atau selalu tidak diterima (tidak dalam bahasa). Jadi tidak ada mekanisme di mana mesin Turing tunggal bahkan dapat menerima lebih dari satu bahasa.

David Richerby
sumber

6

"Menurut definisi" adalah persis apa yang akan saya katakan.

Dave Clarke

1

@DaveClarke Tentu saja, menurut definisi. Tetapi bagi saya ini agak singkat, karena ia juga mengatakan bahwa kita dapat membuat definisi kita berbeda, sehingga TM akan menerima dua bahasa, atau angka apa pun. Saya sebenarnya tidak setuju dengan pernyataan David Richerby bahwa tidak ada mekanisme yang mana TM dapat menerima dua bahasa: itu hanya karena kita memilih untuk mengabaikannya, dan kita bisa melakukan sebaliknya. Karenanya pertanyaannya tidak sepenuhnya dijawab, imho, jika kita tidak menjelaskan apa yang dibenarkan melakukannya.

babou

2

Saya pikir masalahnya di sini adalah bahasa yang digunakan untuk menggambarkan "bahasa" itu sendiri. Mesin Turing menerima apa pun dalam bentuk string terlepas dari definisi bahasa kami. TM mendefinisikan bahasa berdasarkan apa yang diterimanya, ini tidak sama dengan pemahaman kita (manusia) terhadap bahasa. Inilah sebabnya mengapa jawaban ini baik dan "... dijawab sepenuhnya".

David Barker

2

Saya setuju dengan David, OP kemungkinan besar membaca di suatu tempat bahwa mesin Turing hanya mengakui satu bahasa, dan sedang mencoba memahami apa artinya itu. Mengingat bahwa ini mungkin berasal dari sumber normal, kita dapat mengasumsikan mereka menggunakan definisi normal "bahasa" seperti yang didefinisikan dalam teori komputasi, dan bukan definisi lain. Definisi tersebut mungkin arbitrer, tetapi definisi tersebut dipahami dengan baik dan disepakati atas definisi arbitrer.

Cort Ammon

3

Mesin Turing yang menerima dua bahasa adalah mesin Turing yang menerima bahasa yang merupakan gabungan dari dua bahasa.

Simon Richter

9

Pikirkan seperti ini: TM seperti komputer dengan perangkat lunak yang dimuat. Setiap perangkat lunak melakukan satu hal, bukan? Misalnya, pikirkan komputer Anda dan anggap ia hanya memiliki 1 program yang dimuat di dalamnya. Kemudian PC + "photoshop" hanya melakukan photoshop, sedangkan PC + "mine sweeper" hanya menyapu ranjau.

Jadi mesin Turing adalah makhluk yang sangat sederhana, yang pada setiap proses mendapatkan input dan output tunggal baik ya atau tidak . Di mana input itu mengatakan ya, dan yang mengatakan tidak - ini diatur oleh "program" TM sebagaimana ditentukan oleh negara dan fungsi transisi. Setelah ini diperbaiki, "program" diperbaiki, dan untuk setiap input yang diberikan hanya ada satu jawaban: Ya atau Tidak (terima / tolak). Ini mendefinisikan persis satu bahasa = semua input yang menghasilkan Ya ketika diberikan kepada TM.

Di sisi lain, set dari semua TM setara dengan seperangkat komputer + "software" dengan semua program yang mungkin. Sekarang lebih banyak bahasa dapat diputuskan - tetapi masih, masing-masing TM spesifik memutuskan (atau mengenali) hanya satu bahasa.

Ran G.
sumber

Poin kecil: Saya tidak akan mengatakan bahwa TM menghasilkan "baik ya atau tidak", karena ini mengabaikan nonterminasi. Penyederhanaan ini dapat menyebabkan masalah lebih lanjut di kemudian hari.

chi

4

Mesin Turing berfungsi seperti yang mereka lakukan karena kami memilih untuk mendefinisikannya juga. Kita dapat memiliki definisi yang lebih canggih, tetapi pertanyaannya adalah apakah itu akan memenuhi tujuan, apakah itu akan memungkinkan kita melakukan lebih banyak hal. Dan, sejauh yang kita tahu, jawabannya adalah tidak.

Sangat mudah untuk membuat model Turing Machines yang mengenali dua bahasa. Bahasa yang diberikan dan , kita dapat mendefinisikan TM dengan 2 jenis status penerimaan: satu untuk dan satu untuk . Seorang TM akan dikatakan menerima $L_1$ $L_2$ $L_1$ $L_2$ $L_i$ jika ia memasuki suatu kondisi tertentu sebagai negara penerima. Tetapi itu akan melanjutkan perhitungan untuk melihat apakah ia juga bisa memasuki jenis lain dari negara penerima. Dan kita bisa meminta agar nanti berhenti, atau mungkin tidak. Anda kemudian dapat membangun seluruh teori pada mesin seperti itu. Itu akan berhasil dan jauh lebih rumit dari apa yang biasanya kita lakukan.

Untuk menjawab pernyataan David Richerby bahwa " tidak ada mekanisme di mana satu mesin Turing bahkan dapat menerima lebih dari satu bahasa ", itu hanya karena kami memilih untuk tidak mempertimbangkan mekanisme tersebut. Bahkan jika Anda membatasi TM ke model yang sangat standar, Anda bisa mengatakan bahwa input diakui dalam bahasa ketika TM berhenti dalam keadaan menerima dengan jumlah langkah ganjil, dan itu ada di $L_1$ $L_2$ ketika TM menerima dengan sejumlah langkah. Berkat non-determinisme, ini tidak akan mencegah TM dari mengenali kedua bahasa yang berpotongan.

Intinya adalah bahwa semua jenis varian dapat digunakan untuk melakukan teori. Juga pendekatan yang sangat berbeda telah dicoba untuk memodelkan apa itu komputasi, seperti lambda-calculus, compinatory logic, teori fungsi rekursif, dan banyak lagi.

Selalu ditunjukkan bahwa tidak ada dari mereka yang melakukan sesuatu yang tidak dapat dilakukan oleh model sederhana kami di mana TM hanya mengenali satu bahasa. Sedemikian rupa sehingga diduga bahwa ia melakukan apa pun yang bisa dilakukan. Itu disebut tesis Gereja-Turing . Ini adalah landasan teori komputasi, yang, sejauh yang kita tahu, menentukan bahasa apa yang dapat dikenali, atau tidak.

Jadi kita sebaiknya menggunakan model sederhana, karena model yang kompleks akan membuat hidup kita lebih sulit, tanpa manfaat nyata.

Tentu saja, kami terkadang menggunakan model lain karena mereka memungkinkan kami untuk lebih memahami beberapa masalah.

babou
sumber

Saya percaya paragraf pertama agak menyesatkan. Saya berani bertaruh bahwa OP tidak bertanya tentang mengapa kita mendefinisikan hal-hal seperti ini, tetapi mereka bahkan tidak tahu itu masalahnya. "Kita bisa memiliki definisi yang lebih canggih, tetapi pertanyaannya adalah apakah itu akan memiliki tujuan" membuatnya tampak seperti Anda perlu tahu tujuan dari suatu konsep sebelum Anda dapat memberikannya nama - menurut saya, itu buruk cara belajar.

interestinglythere

OP mengatakan dia ingin tahu mengapa TM hanya mengenali satu bahasa untuk memahami sesuatu yang lain. Saya menjawabnya, mereka melakukannya karena kita mendefinisikannya seperti itu. Saya menambahkan, yang benar, bahwa kita dapat menggunakan definisi yang berbeda, tetapi itu tidak akan mengubah teorinya. Itu adalah cara untuk memberitahunya bahwa apa pun yang ia kejar, pilihan definisi tidak material, dan dapat dikenali dapat didefinisikan untuk mencakup set yang persis sama. Alasan untuk memilih definisi adalah kenyamanan dan kesuburan, dan itulah sebabnya mereka berevolusi dengan waktu, serta cara konsep diberi nama atau dicatat.

babou

Oke, itu masuk akal. Saya pikir saya sebagian besar keberatan dengan penggunaan "canggih" - itu menyiratkan bahwa definisi yang kurang sederhana diinginkan.

Menariknya

3

Saya ingin memperluas pada satu titik dalam jawaban Richerby:

Ketika input diberikan ke mesin, itu diterima atau tidak.

Alasan untuk ini adalah bahwa mesin Turing bersifat deterministik: diberi input dan kondisi awal yang sama, mesin Turing akan selalu melakukan hal yang sama setiap kali Anda menjalankannya (baik berakhir dalam kondisi terima yang sama atau dalam kondisi tolak yang sama, atau lewati selamanya ).

Selain itu, kami dapat dengan mudah membuktikan bahwa setiap mesin Turing mengenali persis satu bahasa:

Anggaplah, dengan kontradiksi, bahwa mesin Turing M mengenali dua bahasa berbeda L1 dan L2. Karena L1 dan L2 berbeda, harus ada string S yang ada di L1 tetapi tidak di L2 (tanpa kehilangan generalitas - bisa jadi sebaliknya tetapi buktinya akan berjalan dengan cara yang sama dari sini dengan L1 dan L2 dipertukarkan ). Sekarang jalankan M pada S. Jika diterima, maka kontradiksi tercapai karena S akan berada di L2. Jika tidak menerima (menolak atau loop), maka kontradiksi tercapai karena S tidak akan berada di L1.

Atsby
sumber

2

Mesin Turing mengenali satu bahasa karena itulah definisi dari kata mengenali : Bahasa yang dikenali mesin Turing adalah kumpulan semua string / input yang diterima mesin Turing.

ada yang menarik
sumber

2

Selamat Datang di Ilmu Komputer ! Jawaban Anda adalah (IMO) yang benar tetapi saya tidak berpikir itu menambah jawaban yang sudah ada sebelumnya. Kami memiliki banyak pertanyaan yang belum terjawab dan akan jauh lebih menarik dan produktif untuk menjawab salah satu dari mereka daripada mengulangi jawaban yang ada.

David Richerby

1

Terima kasih! Saya sebenarnya tidak melihat jawaban yang saat ini diterima pada awalnya (yang saya pikir bagus) karena sangat singkat, dan saya merasa seperti jawaban lain tidak menjawab pertanyaan dengan cara yang langsung.

Menariknya

1

Jawabannya tergantung pada apa yang sebenarnya Anda pahami ketika Anda maksudkan "mesin Turing". Ada tiga komponen untuk setiap model komputasi (membatasi untuk penentu / akseptor di sini):

sintaksis,
semantik,
kriteria penerimaan.

Untuk mesin Turing, sintaksis akan menjadi tuple set keadaan, huruf, fungsi transisi, dan sebagainya. The semantik akan definisi dari perhitungan , yaitu untuk menggambarkan bagaimana menerapkan fungsi transisi dalam rangka untuk memperoleh isi rekaman setelah beberapa langkah. The kriteria penerimaan adalah untuk mengatakan, "ketika hal ini terjadi, kita berhenti dan hasilnya adalah bahwa".

Sekarang, apakah mesin Turing hanya sintaks dan semantik untuk Anda, atau apakah Anda memasukkan kriteria penerimaan juga? Jika Anda melakukan yang pertama, TM mana pun dapat menerima banyak bahasa dengan menggunakan kriteria penerimaan yang berbeda; Anda bahkan dapat membayangkan kriteria penerimaan yang memungkinkan untuk beberapa bahasa yang diterima (pikirkan tentang TM dua parameter, misalnya). Namun, jika Anda melakukan yang terakhir, tidak ada ruang gerak dan kriteria penerimaan yang biasa memang memungkinkan tepat satu bahasa per TM (dari jenis ini).

The biasa definisi dan penggunaan istilah dalam TCS mencakup semua tiga komponen. Itu masuk akal karena, khususnya, mengubah kriteria penerimaan dapat mengubah kelas objek yang diwakili oleh robot secara drastis , jadi kita perlu memperbaiki kriteria untuk mengetahui apa yang kita bicarakan.

Sebagai contoh, bandingkan automata terbatas dan Büchi automata . Sintaks dan semantiknya persis sama, tetapi yang satu menerima kata-kata yang terbatas sementara yang lain menerima kata-kata yang tak terbatas!
Coba cari tahu apa yang terjadi jika Anda memasukkan kriteria penerimaan Büchi automata ke definisi TM.

Sekarang, mengapa kriteria penerimaan yang biasa menjadi kriteria? Selama Anda membatasi diri pada bahasa string terbatas, tidak banyak yang akan berubah dengan memiliki beberapa bahasa per TM, pada tingkat konseptual: kami masih akan dapat menerima serangkaian bahasa yang sama. Jadi kami tetap berpegang pada model yang lebih sederhana. Itu tidak berarti, bagaimanapun, bahwa model yang lebih terlibat tidak dapat berguna untuk pemodelan dalam aplikasi - tapi itu di luar ruang lingkup TCS (yang memegang otoritas definitorial).

Raphael
sumber

0

$M_{1}$ $L_{1}$ $L_{2}$ $L_{1} \neq L_{2}$ $s_{1}$ $s_{1} \in L_{1}$ $s_{1} \notin L_{2}$ $M_{1}$ $s_{1}$ $s_{1} \notin L_{2}$ $M_{1}$ $s_{1}$ $s \in L_{2}$ $s \notin L_{1}$

$M$ $L$ $s \in L$ $M$ $s$ $s$ $M$ $s \in L$

$s \in L \iff M$ $s$

$A_{TM}$

pengguna3730788
sumber

Tidak perlu membuktikan bahwa TM hanya mengenali satu bahasa: itu langsung dari definisi "kenali". Mengingat definisi itu, bahkan tidak jelas apa artinya bagi seorang TM untuk menerima lebih dari satu bahasa (seperti yang Anda duga dalam kalimat pertama Anda) atau apakah potongan dari asumsi seperti itu (seperti dalam kalimat ketiga Anda) valid. Bukti berdasarkan kontradiksi hanya berfungsi jika deduksi kedap air: di sini, kesalahannya bisa dalam asumsi tentang bagaimana TM yang mengenali TM berperilaku, daripada dalam asumsi bahwa mesin seperti itu ada.

David Richerby

-2

Bahasa adalah seperangkat string. Bukankah penyatuan dua bahasa L1, dan L2 satu set string (sebut saja L3), dan begitu juga dengan bahasa lain? Kemudian, jika mesin Turing mengenali kedua bahasa, ia mengenali L3, satu bahasa.

Joe Cash
sumber

2

Tetapi mesin Turing tidak mengenali kedua bahasa kecuali mereka sebenarnya sama. Mengenali L1 berarti tidak menerima string apa pun di luar L1; mengenali L2 berarti tidak menerima apa pun di luar L2. Jika L1 dan L2 berbeda, ia tidak dapat mengenali keduanya.

David Richerby

-3

tidak ada jawaban lain yang menunjukkan keberadaan Mesin Universal Turing (s) seperti yang pertama kali dijelaskan / ditemukan oleh Turing dalam bukti berhenti. ya TM menerima satu bahasa enumerasi rekursif tunggal, tetapi UTM dapat mengenali bahasa enumerasi rekursif apa pun jika dikodekan pada input bersama dengan string input. jadi pertanyaannya memiliki kualitas mirip zen. TM hanya menerima satu bahasa dan semua bahasa yang memungkinkan untuk dikodekan.

vzn
sumber

4

Tidak. Mesin Turing universal menerima satu bahasa

{⟨ M, x ⟩ ∣ M accepts x}

$\{\langle M,x\rangle\mid M\text{ accepts }x\}$ untuk beberapa pengkodean

⟨ - ⟩

$\langle-\rangle$ mesin dan input Turing.

David Richerby

& apa bedanya dengan yang tertulis?

vzn

2

Mengenali kode bahasa tidak sama dengan mengenali bahasa.

David Richerby

ya persis seperti yang dinyatakan

vzn

1

@ DavidRicherby Saya pikir ini adalah masalah perspektif. Orang tentu dapat melihat TM universal sebagai menerima banyak bahasa; tulis saja sebagai

{(m, x) ∣ m = ⟨ M ⟩, \dots}

$\{ (m, x) \mid m = \langle M \rangle, \dots \}$ dan lihat bahasa

x

$x$ untuk setiap nomor tetap

m

$m$ (kari / smn). Membatasi TM untuk satu parameter bersifat universal, tetapi tidak perlu.

Raphael

Mengapa mesin Turing mengenali persis satu bahasa?

Jawaban: