Apakah ada hubungan antara Mesin Turing dan kalkulus Lambda - atau apakah mereka muncul secara bersamaan?
49
Apakah ada hubungan antara Mesin Turing dan kalkulus Lambda - atau apakah mereka muncul secara bersamaan?
Jawaban:
Kalkulus lambda lebih tua dari model mesin Turing, yang tampaknya berasal dari periode 1928-1929 (Seldin 2006), dan diciptakan untuk merangkum gagasan tentang fungsi skematis yang diperlukan Gereja untuk logika dasar yang ia buat. Itu tidak diciptakan untuk menangkap gagasan umum tentang fungsi yang dapat dihitung, dan memang versi yang diketik lebih lemah akan melayani tujuannya dengan lebih baik.
Tampaknya kebetulan untuk tujuan bahwa Gereja kalkulus diciptakan ternyata Turing lengkap, meskipun kemudian Gereja menggunakan kalkulus lambda sebagai fondasinya untuk apa yang ia sebut fungsi efektif dihitung (1936), yang menarik Turing dalam makalahnya .
Teori tipe sederhana Gereja (1940) memberikan teori fungsi yang lebih moderat dan diketik yang cukup untuk mengekspresikan sintaksis logika tingkat tinggi tetapi tidak mengekspresikan semua fungsi rekursif. Teori ini dapat dilihat sebagai lebih selaras dengan motivasi asli Gereja.
Referensi
Catatan Jawaban ini secara substansial direvisi karena keberatan oleh Kaveh dan Sasho. Saya merekomendasikan timeline Wikipedia yang disarankan Kaveh, tesis History of the Church-Turing , yang memiliki beberapa kutipan pilihan dari artikel mani.
sumber
Saya hanya ingin menunjukkan bahwa sementara kalkulus lambda dan mesin Turing keduanya menghitung kelas yang sama fungsi bilangan-teoretik, mereka tidak persis sama dalam segala hal yang dapat dibayangkan. Sebagai contoh, dalam teori realisasi ada pernyataan yang dapat direalisasikan oleh mesin Turing tetapi tidak oleh kalkulus lambda. Salah satu pernyataan tersebut adalah tesis resmi Gereja, yang menyatakan:
Di sini adalah predikat T Kleene . Realizer untuk pernyataan ini adalah program yang menerima (representasi) peta dan output (representasi) dengan properti yang diinginkan. Dalam model mesin Turing, peta diwakili oleh kode mesin Turing yang menghitung , sehingga program hanya (kode komputasi mesin Turing) fungsi identitas. Namun, jika kita menggunakan kalkulus lambda, maka seharusnya menghitung angka yang mewakili mesin Turing dari istilah lambda mewakili fungsiT c f e f f c c f . Ini tidak dapat dilakukan (saya dapat menjelaskan mengapa, jika Anda mengajukannya sebagai pertanyaan terpisah).
sumber
Mereka terkait baik secara matematis dan historis.
Kalkulus lambda dikembangkan pada tahun 1928 - 1929 oleh Gereja Alonzo (diterbitkan pada tahun 1932).
Mesin Turing dikembangkan pada tahun 1935 - 1937 oleh Alan Turing (diterbitkan pada tahun 1937).
Alan Turing adalah Ph.D. Gereja Alonzo pelajar di Princeton dari tahun 1936 - 1938.
Mesin Turing dan kalkulus lambda setara dalam kekuatan komputasi: masing-masing dapat secara efisien mensimulasikan yang lain.
sumber
Entscheidungsproblem adalah salah satu dari 23 masalah terkenal yang dikemukakan oleh ahli matematika David Hilbert.
Jadi kalkulus lambda dan mesin Turing tidak hanya terkait erat tetapi mereka adalah model komputasi yang setara .
Anda juga mungkin suka membaca The Annotated Turing: Tur Dipandu Melalui Kertas Bersejarah Alan Turing tentang Kompabilitas dan Mesin Turing oleh Charles Petzold . Buku ini menangkap beberapa informasi menarik tentang topik tersebut.
sumber
Mesin Turing dan Lambda Calculus adalah dua model yang menangkap gagasan algoritma (perhitungan mekanis). Kalkulus Lambda ditemukan oleh Gereja untuk melakukan perhitungan dengan fungsi. Ini adalah dasar dari bahasa pemrograman fungsional. Pada dasarnya, setiap masalah yang dapat dihitung (decidable) oleh mesin Turing juga dapat dihitung menggunakan Lambda calculus. Jadi, mereka adalah dua model komputasi yang setara (hingga faktor polinomial) dan keduanya mencoba menangkap kekuatan komputasi mekanis apa pun.
sumber