Pentingnya praktis mesin Turing?

Saya seorang insinyur listrik, dan hanya memiliki satu kursus CS di perguruan tinggi 26 tahun yang lalu. Namun, saya juga pengguna setia Mathematica.

Saya merasa bahwa Mesin Turing sangat penting dalam ilmu komputer. Apakah kepentingannya hanya dalam teori ilmu komputer? Jika ada implikasi / aplikasi praktis, apa sajakah dari mereka?

Pentingnya mesin Turing ada dua. Pertama, mesin Turing adalah salah satu model teoritis pertama (jika bukan yang pertama) untuk komputer, yang berasal dari tahun 1936. Kedua, banyak ilmu komputer teoritis telah dikembangkan dengan mempertimbangkan mesin Turing, dan banyak hasil dasarnya adalah dalam bahasa mesin Turing. Salah satu alasan untuk ini adalah bahwa mesin Turing sederhana, dan sangat memungkinkan untuk dianalisis.

Yang mengatakan, mesin Turing bukan model praktis untuk komputasi. Sebagai seorang insinyur dan pengguna Mathematica, mereka seharusnya tidak membuat Anda khawatir sama sekali. Bahkan dalam komunitas ilmu komputer teoretis, mesin RAM yang lebih realistis digunakan di bidang algoritma dan struktur data.

Bahkan, dari sudut pandang teori kompleksitas, mesin Turing secara polinomi setara dengan banyak model mesin lainnya, sehingga kelas kompleksitas seperti P dan NP dapat secara setara didefinisikan dalam hal model ini. (Kelas kompleksitas lainnya lebih halus.)

Mesin Turing adalah salah satu model awal untuk komputasi, yaitu mereka dikembangkan ketika komputasi itu sendiri tidak dipahami dengan baik (sekitar 1940). Saya ingin fokus pada dua aspek yang (bisa dibilang) menyebabkan mereka menjadi model yang disukai saat itu, yang menyebabkan menjadi model yang paling mapan dan akhirnya menjadi model standar.

1. Kesederhanaan bukti
   Sebagai model teoretis, mesin Turing memiliki daya tarik "sederhana" dalam arti bahwa kondisi mesin saat ini hanya memiliki ukuran konstan. Semua informasi yang Anda butuhkan untuk menentukan status mesin berikutnya adalah satu simbol dan satu (status kontrol). Perubahan ke kondisi mesin sama kecilnya, hanya menambahkan pergerakan kepala mesin. Itu menyederhanakan bukti (formal), terutama jumlah kasus yang harus dibedakan.

   Bandingkan aspek ini dengan model RAM (bila tidak digunakan dalam bentuk minimalis): operasi berikutnya mungkin saja dari beberapa operasi, yang dapat mengakses setiap (dua) register. Ada juga beberapa struktur kontrol.

2. 
   $\lambda$$\mu$

   Untuk mesin Turing, bagaimanapun, kedua gagasan itu mudah didefinisikan (dan berada di kertas pertama Turing pada modelnya, jika saya ingat dengan benar). Karena pertimbangan efisiensi segera sangat penting untuk benar-benar melakukan hal-hal, ini merupakan keuntungan pasti dari mesin Turing.

Dengan demikian, mesin Turing telah ditetapkan sebagai satu model komputasi, yang dapat dilihat sebagai kombinasi dari sejarah "kecelakaan" dan beberapa sifat kunci. Namun demikian, banyak model telah ditentukan sejak dan digunakan dengan rajin, khususnya untuk mengatasi kekurangan mesin Turing; misalnya, mereka membosankan untuk "program" (yaitu mendefinisikan).

Saya tidak mengetahui adanya aplikasi langsung dalam praktiknya. Secara khusus, praktik komputasi berevolusi paralel dengan (dan, pada awalnya, sebagian besar terlepas dari) teori komputasi. Bahasa pemrograman yang dikembangkan tanpa model mesin formal. Namun, jelas (di belakang) bahwa banyak kemajuan dalam praktik komputasi dimungkinkan oleh teori.

Selain itu, perlu diingat bahwa nilai yang dimiliki konsep teoretis untuk praktik harus diukur dengan mempertimbangkan semua keturunan, yaitu kerja lanjutan, hasil, dan gagasan baru yang dimungkinkan oleh konsep itu. Dan dalam hal itu, saya pikir adil untuk mengatakan bahwa konsep mesin Turing (antara lain) telah merevolusi dunia.

Satu-satunya aplikasi yang cukup praktis yang dapat saya pikirkan (dalam arti bahwa Anda mungkin benar-benar mengimplementasikan mesin Turing) adalah untuk membuktikan bahwa bahasa semacam itu memiliki kekuatan yang cukup.

Jika Anda merancang semacam bahasa pemrograman (atau apa pun yang dimaksudkan untuk menghitung hal-hal), maka Anda mungkin ingin memastikan bahwa itu adalah Turing-complete (mis. Mampu menghitung apa pun yang dapat dihitung) dengan menerapkan mesin Turing di dalamnya.

Tentu saja, Anda juga bisa menerapkan hal lain yang lengkap-Turing (seperti C atau logika kombinasional), tetapi kadang-kadang mesin Turing adalah pilihan yang paling mudah.

Mesin Turing adalah model perhitungan matematis. Manfaatnya adalah: -

1. Periksa Decidability Jika TM tidak dapat menyelesaikan masalah dalam waktu yang dapat dihitung maka tidak ada algoritma yang dapat memecahkan masalah tersebut (Itulah masalahnya adalah tidak dapat ditentukan).

Untuk masalah keputusan jika TM-nya berhenti dalam waktu yang dapat dihitung untuk semua input panjang yang terbatas maka kita dapat mengatakan bahwa masalah tersebut dapat diselesaikan dengan suatu algoritma dalam waktu yang dapat dihitung.

2. Klasifikasi Masalah TM membantu untuk mengklasifikasikan masalah yang dapat diputuskan ke dalam kelas Hirarki Polinomial.

Misalkan kita menemukan bahwa masalahnya dapat ditentukan. Kemudian target menjadi seberapa efisien kita bisa menyelesaikannya. Efisiensi dihitung dalam beberapa langkah, ruang ekstra yang digunakan, panjang kode / ukuran FSM.

3. Desain dan Implementasi Algoritma untuk Mesin Praktis TM membantu untuk menyebarkan ide algoritma di mesin praktis lainnya. Setelah pemeriksaan 1,2 kriteria berhasil kita dapat menggunakan perangkat / komputer praktis kita untuk merancang dan mengimplementasikan algoritma.

Mesin Turing adalah latihan pikiran yang baik dengan sedikit penggunaan praktis. Tidak ada salahnya tidak memilikinya. Semua aplikasi mesin Turing bersifat intuitif atau masalah agama karena tidak dapat dibuktikan atau disangkal.