Model Komputasi
Banyak kerangka formal mendefinisikan apa artinya menghitung, mulai dari penulisan ulang fungsi kalkulus lambda hingga sirkuit Boolean dan sistem kuantum, dan membandingkan kekuatannya mengungkapkan model mana yang setara dan mana yang benar-benar berbeda.
Definition
Model komputasi adalah kerangka abstrak yang tepat yang menentukan operasi apa yang diizinkan dan bagaimana komputasi berlangsung; model yang berbeda dapat menghitung kelas fungsi yang sama namun berbeda dalam keringkasan, paralelisme, atau sumber daya yang mereka eksplisitkan.
Scope
Area ini mencakup kalkulus lambda dan model fungsional, fungsi rekursif dan mesin register, sirkuit Boolean dan kompleksitas sirkuit, serta komputasi kuantum, menguji bagaimana setiap model mengekspresikan algoritma, bagaimana kekuatan komputabilitasnya berhubungan melalui tesis Church–Turing, dan bagaimana efisiensinya dapat menyimpang.
Sub-topics
Core questions
- Apa saja cara berbeda untuk memformalkan gagasan komputasi?
- Model mana yang setara dalam fungsi yang dapat mereka hitung, dan mengapa?
- Bagaimana model berbeda setelah efisiensi, paralelisme, atau realisasi fisik menjadi penting?
- Dapatkah model yang termotivasi secara fisik seperti komputasi kuantum melampaui efisiensi klasik?
Key theories
- Kesetaraan di bawah tesis Church–Turing
- Kalkulus lambda, fungsi rekursif, mesin register, dan mesin Turing semuanya menghitung kelas fungsi yang sama persis, konvergensi yang mendasari identifikasi komputasi dengan komputabilitas Turing.
- Perbedaan dalam efisiensi
- Model yang setuju pada komputabilitas dapat sangat berbeda dalam sumber daya: sirkuit mengekspos komputasi paralel dan non-seragam, dan model kuantum tampaknya menawarkan percepatan, sehingga pilihan model sangat penting untuk kompleksitas bahkan ketika tidak untuk komputabilitas.
Clinical relevance
Model yang berbeda menerangi aspek-aspek yang berbeda dari komputasi nyata: kalkulus lambda adalah dasar teoretis dari bahasa pemrograman fungsional, sirkuit memodelkan perangkat keras dan komputasi paralel, mesin register mencerminkan prosesor konvensional, dan model kuantum memandu desain perangkat keras dan algoritma kuantum yang muncul.
History
Pada tahun 1930-an, kalkulus lambda Church, fungsi rekursif Gödel dan Kleene, serta mesin Turing masing-masing diusulkan dan kemudian ditunjukkan setara. Model-model selanjutnya menambahkan dimensi baru: kompleksitas sirkuit memformalkan komputasi paralel dan perangkat keras, dan proposal Feynman tahun 1982 tentang simulasi kuantum menabur model komputasi kuantum.
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- Mengapa mempelajari banyak model jika mereka menghitung fungsi yang sama?
- Kesetaraan hanya berlaku untuk apa yang dapat dihitung secara prinsip. Model yang berbeda membuat hal-hal yang berbeda mudah diekspresikan atau dianalisis: kalkulus lambda memperjelas pemrograman fungsional, sirkuit mengungkapkan paralelisme dan biaya perangkat keras, dan model kuantum menangkap fenomena fisik, sehingga masing-masing adalah lensa yang tepat untuk pertanyaan yang berbeda.
- Apakah semua model komputasi setara?
- Semua model klasik yang masuk akal menghitung kelas fungsi yang sama, mendukung tesis Church–Turing. Tetapi mereka dapat sangat berbeda dalam efisiensi, dan model yang memanfaatkan sumber daya yang berbeda, seperti superposisi kuantum, dapat memecahkan masalah tertentu lebih cepat meskipun menghitung fungsi yang sama.