Saya melihat bahwa sebagian besar definisi Turing-complete adalah tautologis. Misalnya jika Anda Google "apa artinya menjadi Turing lengkap", Anda mendapatkan:

Komputer Turing lengkap jika dapat menyelesaikan masalah apa pun yang dapat dilakukan mesin Turing ...

Sementara itu didefinisikan dengan sangat baik apakah sistem yang berbeda Turing lengkap atau tidak, saya belum melihat penjelasan tentang apa implikasi / konsekuensi menjadi Turing lengkap.

Apa yang bisa dilakukan mesin Turing di mana tidak ada mesin non-Turing yang dapat melakukan tugas yang sama? Misalnya komputer dapat melakukan perhitungan sederhana seperti (1+5)/3=?, tetapi kalkulator biasa juga dapat melakukannya, yang non-Turing lengkap jika saya benar.

Apakah ada cara untuk mendefinisikan kemampuan Turing Machine tanpa hanya mengatakan "mampu mensimulasikan Mesin Turing lain"?

Saya merenung sebentar apakah akan menambahkan jawaban lain. Jawaban yang lain fokus di tengah pertanyaannya (tentang "turing lengkap", "tautologi" dan sebagainya). Biarkan saya ambil bagian pertama dan terakhir, dan dengan demikian gambaran yang lebih besar dan sedikit filosofis:

Tapi apa artinya itu?

Apa artinya menjadi Turing lengkap?

Apakah ada cara untuk mendefinisikan kemampuan Turing Machine tanpa hanya mengatakan "mampu mensimulasikan Mesin Turing lain"?

Berbicara secara informal, menjadi Turing lengkap berarti mekanisme Anda dapat menjalankan algoritma apa pun yang dapat Anda pikirkan, tidak peduli seberapa kompleks, dalam, rekursif, rumit, panjang (dalam hal kode), dan tidak peduli berapa banyak penyimpanan atau waktu yang akan diperlukan untuk mengevaluasinya. Tak perlu dikatakan bahwa itu hanya berhasil jika masalah dapat dihitung, tetapi jika itu dapat dihitung, itu akan berhasil (berhenti).

(NB: untuk mencari tahu mengapa ini "informal", lihat tesis Gereja-Turing yang sejalan, dengan kata-kata yang lebih rumit; menjadi tesis, itu bisa atau tidak bisa benar. Terima kasih kepada @DavidRicherby untuk menunjukkan kelalaian kecil ini dalam komentar.)

"Algoritma" berarti apa yang biasanya kita pahami sebagai algoritma komputer saat ini; yaitu, serangkaian langkah-langkah terpisah memanipulasi penyimpanan, dengan beberapa logika kontrol bercampur. Namun, ini tidak seperti mesin Oracle, yaitu, ia tidak dapat "menebak".

Contoh untuk bahasa non-tc yang praktis

Jika Anda telah memprogram diri sendiri, Anda mungkin tahu ekspresi reguler, yang digunakan untuk mencocokkan string dengan beberapa pola.

Ini adalah salah satu contoh konstruksi yang tidak Turing Lengkap. Anda dapat dengan mudah menemukan latihan di mana tidak mungkin membuat ekspresi reguler yang cocok dengan frasa tertentu.

Sebagai contoh (dan ini pasti telah menyebalkan banyak programmer dalam aplikasi nyata yang sebenarnya), secara teoritis dan praktis tidak mungkin untuk membuat ekspresi reguler yang cocok dengan bahasa pemrograman atau dokumen XML: tidak mungkin bagi regexp untuk menemukan struktur blok ( do ... endatau { ... }dalam bahasa; membuka dan menutup tag dalam dokumen XML) jika diizinkan secara mendalam. Jika ada batasan di sana, misalnya Anda hanya dapat memiliki 3 level "rekursi", maka Anda dapat menemukan ekspresi reguler; tetapi jika tidak terbatas, maka itu tidak boleh.

Karena sangat mungkin untuk membuat program dalam bahasa Turing-complete (seperti C) untuk mengurai kode sumber (kompiler mana pun yang melakukannya), ekspresi reguler tidak akan pernah dapat mensimulasikan program tersebut, maka mereka secara definisi bukan Turing-complete

Motivasi

Gagasan mesin turing itu sendiri tidak praktis; misalnya, Turing tentu tidak menciptakannya untuk membuat komputer nyata atau sesuatu seperti itu, berlawanan dengan Charles Babbage atau von Neumann, misalnya. Inti dari konsep Mesin Turing adalah sangat sederhana. Ini terdiri dari hampir tidak ada. Ini mengurangi kemungkinan (dan aktual) komputer ke minimum paling sederhana yang bisa dibayangkan.

Inti dari penyederhanaan ini, pada gilirannya, adalah bahwa hal ini memudahkan (ish) untuk merenungkan pertanyaan-pertanyaan teoretis (seperti menghentikan masalah, kelas-kelas kompleksitas dan apa pun ilmu komputer teoretis yang mengganggu). Salah satu fitur khususnya adalah biasanya sangat mudah untuk memverifikasi apakah bahasa yang diberikan atau komputer dapat mensimulasikan Mesin Turing hanya dengan pemrograman kata Mesin Turing (yang sangat mudah!) Dalam bahasa itu.

Hingga tak terbatas

Perhatikan bahwa Anda tidak pernah membutuhkan waktu atau penyimpanan tanpa batas ; tetapi waktu dan penyimpanan tidak terbatas. Mereka akan memiliki nilai maksimal untuk setiap proses yang dapat dikomputasi, tetapi tidak ada batasan seberapa besar nilai tersebut dapat terjadi. Kenyataan bahwa komputer yang nyata pada akhirnya akan kehabisan RAM telah dipoles di sini; ini tentu saja merupakan batasan untuk komputer fisik apa pun, tetapi juga jelas dan tidak menarik bagi "kekuatan komputasi" teoretis mesin. Kami juga tidak tertarik tentang berapa lama waktu yang dibutuhkan. Jadi mesin kecil kami dapat menggunakan jumlah waktu dan ruang yang sewenang-wenang, yang membuatnya sangat tidak praktis.

... dan seterusnya

Satu mencengangkan titik terakhir, kemudian, adalah bahwa sederhana seperti itu, hal yang sederhana dapat melakukan segala sesuatu setiap komputer nyata dibayangkan bisa pernah , di seluruh alam semesta, mencapai (hanya sangat jauh lebih lambat) - setidaknya sejauh yang kita kenal sekarang.

Sama sekali tidak tautologis.

Model perhitungan adalah Turing-complete jika dapat mensimulasikan semua mesin Turing, yaitu, setidaknya sekuat mesin Turing.

Satu hal yang dapat dilakukan mesin Turing adalah mensimulasikan mesin Turing lainnya (melalui mesin Turing universal). Itu berarti bahwa, jika model komputasi Anda tidak dapat mensimulasikan mesin Turing, itu tidak dapat melakukan setidaknya satu hal yang dapat dilakukan mesin Turing, sehingga tidak memenuhi definisi, sehingga Turing tidak lengkap. Tidak ada sirkularitas karena kami tidak mendefinisikan kelengkapan Turing dalam hal itu sendiri: kami mengatakan bahwa kelengkapan Turing adalah properti untuk dapat melakukan segala sesuatu yang dapat dilakukan mesin Turing.

$a$$b$

Apakah ada cara untuk mendefinisikan kemampuan Turing Machine tanpa hanya mengatakan "mampu mensimulasikan Mesin Turing lain"?

Saya tidak yakin apa yang Anda maksud dengan "mendefinisikan kemampuan mesin Turing". Kemampuan didefinisikan dalam hal otomat keadaan terbatas yang beroperasi pada pita tak terbatas. (Saya tidak akan mengulangi definisi lengkap tetapi Anda dapat menemukannya, misalnya, di Wikipedia .)

Model perhitungan Turing hanyalah salah satu dari banyak model komputasi yang setara. Ini memiliki kekuatan yang sama dengan fungsi rekursif Gödel dan kalkulus lambda Gereja, yang diusulkan sekitar waktu yang sama, serta model-model lain seperti mesin penunjuk. Karena itu Anda dapat menyatakan itu

Komputer Turing-selesai jika dapat memecahkan masalah yang Excel bisa.

Ini berfungsi karena Excel juga Turing-complete. Saya merekomendasikan untuk melihat halaman Wikipedia tentang tesis Gereja-Turing , dan pada kertas survei Blass dan Gurevich, Algoritma: A Quest for Absolute Definition .

Mengenai pertanyaan Anda, apa yang bisa dilakukan mesin Turing yang tidak bisa dilakukan mesin Turing, secara umum jawabannya sayangnya tergantung pada mesin non-Turing.

Namun demikian, dimungkinkan untuk mendefinisikan gagasan non-sepele tentang masalah tuntas Turing, misalnya:

$L$$A$$f$$a \in A$$f(a) \in L$

Di bawah definisi ini, penyandian yang cocok untuk masalah penghentian adalah Turing-complete, dan untuk kelas mesin yang masuk akal (tergantung pada definisi "computable yang efisien"), mesin tersebut Turing-complete jika dapat mewujudkan beberapa (setara, semua ) Bahasa Turing-lengkap.

Ada banyak masalah lain yang menyelesaikan Turing yang ditangkap oleh formalisme ini, tergantung pada definisi "yang dapat dihitung secara efisien", seperti masalah korespondensi Turing, dan masalah mengenai ubin Wang dan Game of Life. Masalah-masalah ini dapat berfungsi sebagai tolok ukur alih-alih masalah penghentian.

Pertama-tama saya ingin menunjukkan bahwa definisi kelengkapan Turing sama sekali tidak tautologis. Tidak hanya membuktikan model komputasional, Turing-complete adalah hasil yang menarik dalam dirinya sendiri, tetapi juga memungkinkan Anda untuk segera memperluas semua hasil dari teori komputabilitas ke model komputasi lain ini; misalnya: mesin 2-counter adalah Turing-complete, mesin Turing tidak dapat menyelesaikan masalah penghentian, oleh karena itu tidak ada mesin 2-counter yang bisa.

$\mu$

Kelas semacam itu menggabungkan fungsi-fungsi yang "secara intuitif dapat dihitung", yaitu perhitungan mana yang dapat dilakukan oleh manusia mengikuti algoritme yang tepat dengan pensil dan kertas.

Jelas bahwa "secara intuitif dapat dihitung" sebenarnya bukan definisi formal, identifikasi "secara intuitif dapat dihitung" dengan "Turing yang dapat dihitung" dikenal sebagai tesis Church-Turing. Karena banyak upaya formal untuk mengkarakterisasi kemampuan komputasi pada akhirnya menyatu dengan model komputasi yang Turing-complete, meskipun tidak akan pernah ada bukti formal dari pernyataan seperti itu dalam pengertian matematika, ada alasan kuat untuk memercayainya.

Mesin Turing memiliki kaleng yang menghitung fungsi yang sama dengan komputer kuantum universal, yang dapat mensimulasikan sistem fisik apa pun:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

Dengan demikian, mesin Turing mampu melakukan pemrosesan informasi apa pun yang diizinkan oleh hukum fisika, meskipun ia tidak akan selalu melakukan pemrosesan tersebut seefisien mungkin.