Apa itu Turing Lengkap?

Apa arti ungkapan "Turing Lengkap"?

Bisakah Anda memberikan penjelasan sederhana, tanpa terlalu banyak detail teoretis?

Berikut penjelasan singkatnya:

Sistem Turing Lengkap berarti sistem di mana suatu program dapat ditulis yang akan menemukan jawaban (walaupun tanpa jaminan tentang runtime atau memori).

Jadi, jika seseorang mengatakan "hal baru saya adalah Turing Lengkap" yang berarti pada prinsipnya (meskipun sering tidak dalam praktik) itu dapat digunakan untuk menyelesaikan masalah perhitungan.

Suatu saat itu adalah lelucon ... seorang pria menulis simulator Turing Machine di vi, jadi mungkin untuk mengatakan bahwa vi adalah satu-satunya mesin komputasi yang pernah dibutuhkan di dunia.

Berikut ini penjelasan paling sederhana

Alan Turing menciptakan mesin yang dapat mengambil program, menjalankan program itu, dan menunjukkan beberapa hasil. Tetapi kemudian dia harus membuat mesin yang berbeda untuk program yang berbeda. Jadi dia menciptakan "Mesin Universal Turing" yang dapat mengambil program APA SAJA dan menjalankannya.

Bahasa pemrograman mirip dengan mesin tersebut (meskipun virtual). Mereka mengambil program dan menjalankannya. Sekarang, bahasa pemrograman disebut "Turing complete", jika itu dapat menjalankan program apa pun (terlepas dari bahasa) yang dijalankan oleh mesin Turing diberikan waktu dan memori yang cukup.

Sebagai contoh: Katakanlah ada program yang mengambil 10 angka dan menambahkannya. Mesin Turing dapat dengan mudah menjalankan program ini. Tetapi sekarang bayangkan bahwa karena suatu alasan bahasa pemrograman Anda tidak dapat melakukan penambahan yang sama. Ini akan membuatnya "Turing tidak lengkap" (bisa dikatakan). Di sisi lain, jika ia dapat menjalankan program apa pun yang dapat dijalankan mesin universal Turing, maka Turing itu lengkap.

Sebagian besar bahasa pemrograman modern (misalnya Java, JavaScript, Perl, dll.) Semua Turing lengkap karena mereka masing-masing mengimplementasikan semua fitur yang diperlukan untuk menjalankan program seperti penambahan, perkalian, kondisi if-else, pernyataan pengembalian, cara untuk menyimpan / mengambil / menghapus data dan sebagainya.

Pembaruan: Anda dapat mempelajari lebih lanjut di posting blog saya: "JavaScript Is Turing Complete" - Dijelaskan

Dari wikipedia :

Kelengkapan Turing, dinamai menurut Alan Turing, penting karena setiap desain yang masuk akal untuk perangkat komputasi sejauh ini dapat ditiru oleh mesin Turing universal - pengamatan yang telah dikenal sebagai tesis Church-Turing. Dengan demikian, mesin yang dapat bertindak sebagai mesin Turing universal dapat, pada prinsipnya, melakukan perhitungan apa pun yang dapat dilakukan oleh komputer lain yang dapat diprogram. Namun, ini tidak ada hubungannya dengan upaya yang diperlukan untuk menulis sebuah program untuk mesin, waktu yang diperlukan untuk mesin untuk melakukan perhitungan, atau kemampuan apa pun yang mungkin dimiliki mesin yang tidak terkait dengan perhitungan.

Sementara mesin Turing yang benar-benar lengkap sangat mungkin secara fisik tidak mungkin, karena mereka membutuhkan penyimpanan tanpa batas, kelengkapan Turing sering kali secara longgar dikaitkan dengan mesin fisik atau bahasa pemrograman yang akan universal jika mereka memiliki penyimpanan tanpa batas. Semua komputer modern Turing-lengkap dalam pengertian ini.

Saya tidak tahu bagaimana Anda bisa lebih non-teknis dari itu kecuali dengan mengatakan "turing yang lengkap berarti 'dapat menjawab masalah yang dapat dihitung dengan waktu dan ruang yang cukup'".

Definisi Informal

Bahasa lengkap Turing adalah bahasa yang dapat melakukan perhitungan apa pun. The Gereja-Turing Tesis menyatakan bahwa setiap perhitungan performable dapat dilakukan dengan mesin Turing. Sebuah mesin Turing adalah mesin dengan tak terbatas random access memory dan 'Program' terbatas yang mendikte ketika harus membaca, menulis, dan bergerak melintasi memori yang, ketika harus mengakhiri dengan hasil tertentu, dan apa yang harus dilakukan selanjutnya. Input ke mesin Turing dimasukkan ke dalam memorinya sebelum dimulai.

Hal-hal yang dapat membuat bahasa TIDAK Turing lengkap

Mesin A Turing dapat membuat keputusan berdasarkan apa yang dilihatnya dalam memori - The 'bahasa' yang hanya mendukung +, -, *, dan /pada bilangan bulat tidak Turing lengkap karena tidak dapat membuat pilihan berdasarkan masukan, tetapi mesin Turing bisa.

Mesin Turing dapat berjalan selamanya - Jika kami mengambil Java, Javascript, atau Python dan menghapus kemampuan untuk melakukan segala jenis loop, GOTO, atau panggilan fungsi, itu tidak akan Turing lengkap karena tidak dapat melakukan perhitungan sewenang-wenang yang tidak pernah selesai. Coq adalah pepatah teorema yang tidak bisa mengekspresikan program yang tidak berakhir, jadi Turing tidak lengkap.

Mesin Turing dapat menggunakan memori tak terbatas - Bahasa yang persis seperti Java tetapi akan berakhir setelah menggunakan lebih dari 4 Gigabytes memori tidak akan Turing lengkap, karena mesin Turing dapat menggunakan memori tak terbatas. Inilah sebabnya mengapa kita tidak bisa benar-benar membangun mesin Turing, tetapi Java masih merupakan bahasa lengkap Turing karena bahasa Java tidak memiliki batasan mencegahnya menggunakan memori tak terbatas. Ini adalah salah satu alasan ekspresi reguler Turing tidak lengkap.

Mesin Turing memiliki memori akses acak - Bahasa yang hanya memungkinkan Anda bekerja dengan memori pushdan popoperasi ke stack tidak akan selesai sepenuhnya. Jika saya memiliki 'bahasa' yang membaca string sekali dan hanya dapat menggunakan memori dengan mendorong dan muncul dari tumpukan, itu dapat memberitahu saya apakah setiap (string memiliki )nanti sendiri dengan mendorong ketika melihat (dan muncul ketika melihatnya ). Namun, tidak dapat memberi tahu saya jika setiap (memiliki )nanti sendiri dan setiap nanti nanti [sendiri ](catatan yang ([)]memenuhi kriteria ini tetapi ([]]tidak). Mesin Turing dapat menggunakan memori akses acaknya untuk melacak ()dan[]terpisah, tetapi bahasa ini hanya dengan tumpukan tidak bisa.

Mesin Turing dapat mensimulasikan mesin Turing lainnya - Mesin Turing, ketika diberi 'program' yang sesuai, dapat mengambil 'program' mesin Turing lainnya dan mensimulasikannya pada input sewenang-wenang. Jika Anda memiliki bahasa yang dilarang menerapkan interpreter Python, itu tidak akan Turing lengkap.

Contoh dari Turing bahasa lengkap

Jika bahasa Anda memiliki memori akses acak tak terbatas, eksekusi bersyarat, dan beberapa bentuk eksekusi berulang, itu mungkin Turing lengkap. Ada sistem yang lebih eksotis yang masih dapat mencapai semua yang dapat dilakukan mesin Turing, yang membuat mereka juga menyelesaikan Turing:

• Kalkulus lambda yang tidak diketik
• Permainan hidup Conway
• Template C ++
• Prolog

Pada dasarnya, kelengkapan Turing adalah salah satu syarat singkat, rekursi tak terbatas.

Bahkan tidak dibatasi oleh ingatan.

Saya memikirkan ini secara mandiri, tetapi sini ada beberapa diskusi tentang pernyataan tersebut. Definisi saya tentang LSP menyediakan lebih banyak konteks.

Jawaban lain di sini tidak secara langsung mendefinisikan esensi mendasar dari kelengkapan Turing.

Turing Complete berarti setidaknya sekuat Mesin Turing . Ini berarti apa pun yang dapat dihitung dengan Mesin Turing dapat dihitung dengan sistem Turing Lengkap.

Belum ada yang menemukan sistem yang lebih kuat daripada Mesin Turing. Jadi, untuk saat ini, mengatakan sistem Turing Lengkap sama dengan mengatakan sistem sama kuatnya dengan sistem komputasi yang dikenal (lihat Tesis Gereja-Turing ).

Dalam istilah yang paling sederhana, sistem Turing-complete dapat menyelesaikan masalah komputasi yang mungkin terjadi.

Salah satu persyaratan utama adalah ukuran scratchpad tidak terikat dan memungkinkan untuk mundur untuk mengakses tulisan sebelumnya ke scratchpad.

Jadi dalam praktiknya tidak ada sistem yang Turing-lengkap.

Alih-alih beberapa sistem mendekati Turing-kelengkapan dengan memodelkan memori tidak terbatas dan melakukan perhitungan apa pun yang mungkin sesuai dengan memori sistem.

Saya pikir pentingnya konsep "Turing Lengkap" adalah dalam kemampuan untuk mengidentifikasi mesin komputasi (belum tentu mekanikal / listrik "komputer") yang dapat prosesnya didekonstruksi menjadi instruksi "sederhana", terdiri dari lebih sederhana dan lebih sederhana instruksi, bahwa mesin Universal dapat menafsirkan dan kemudian mengeksekusi.

Saya sangat merekomendasikan The Annotated Turing

@Mark, saya pikir apa yang Anda jelaskan adalah campuran antara deskripsi Mesin Universal Turing dan Turing Lengkap.

Sesuatu yang Turing Lengkap, dalam arti praktis, akan menjadi mesin / proses / komputasi yang dapat ditulis dan diwakili sebagai program, yang akan dijalankan oleh Universal Machine (komputer desktop). Meskipun tidak mempertimbangkan waktu atau penyimpanan, seperti yang disebutkan oleh orang lain.

Apa yang saya pahami dengan kata-kata sederhana:

Turing Complete: Bahasa pemrograman / program yang dapat melakukan komputasi, adalah Turing complete.

Sebagai contoh :

1. Bisakah Anda menambahkan dua angka menggunakan Just HTML . (Ans adalah ' Tidak ', Anda harus menggunakan javascript untuk melakukan penambahan.), Karenanya HTML tidak Turing Lengkap.

2. Bahasa-bahasa seperti Java, C ++, Python, Javascript, Solidity untuk Ethereum dll. Turing Lengkap karena Anda dapat melakukan perhitungan seperti menambahkan dua angka menggunakan bahasa ini.

Semoga ini membantu.

Lengkap jika dapat menguji dan bercabang (memiliki 'jika')

Mesin Turing mengharuskan setiap program dapat melakukan pengujian kondisi. Itu fundamental.

Pertimbangkan pemain piano roll. Pemain piano dapat memainkan musik yang sangat rumit, tetapi tidak pernah ada logika kondisional dalam musik. Itu Turing Lengkap.

Logika bersyarat adalah kekuatan dan bahaya dari mesin yang Turing Lengkap.

Roll piano dijamin berhenti setiap saat. Tidak ada jaminan untuk TM. Ini disebut "masalah terputus-putus."

Seperti yang dikatakan Waylon Flinn :

Turing Complete berarti setidaknya sekuat Mesin Turing.

Saya percaya ini salah, sistem Turing lengkap jika sama kuatnya dengan Mesin Turing, yaitu setiap perhitungan yang dilakukan oleh mesin dapat dilakukan oleh sistem, tetapi juga setiap perhitungan yang dilakukan oleh sistem dapat dilakukan oleh mesin Turing .

Dalam istilah-istilah bahasa praktis yang umum bagi kebanyakan programmer, cara yang biasa untuk mendeteksi kelengkapan Turing adalah jika bahasa tersebut memungkinkan atau memungkinkan simulasi pernyataan sementara yang tidak dibatasi sementara (sebagai lawan dari gaya Pascal untuk pernyataan, dengan batas atas tetap).

Dapatkah sebuah basis data relasional memasukkan garis lintang dan bujur tempat dan jalan, dan menghitung jalur terpendek di antara mereka - tidak. Ini adalah salah satu masalah yang menunjukkan SQL belum selesai Turing.

Tetapi C ++ dapat melakukannya, dan dapat melakukan masalah apa pun. Begitulah.