Maieutik lambda-calculus

Adakah anda fikir manusia menemui atau mencipta pengkomputeran?

Saya cenderung kepada penemuan, kerana Mesin Turing dan Lambda-Calculus Gereja telah diformalkan secara berasingan antara satu sama lain pada tahun 1936, namun kedua-duanya juga ekspresif secara universal (membolehkan anda mengira segala-galanya). Sangat berbeza, tetapi 100% setara.

Saya tidak bercakap tentang ciptaan komputer perkakasan, yang boleh mengambil semua bentuk dan secara amnya melaksanakan konsep ini terima kasih kepada litar elektronik dan transistornya. Saya bercakap di sini tentang logik pengiraan dan pemikiran pengiraan yang berkaitan dengannya: logik itu terapung di udara menunggu untuk ditangkap dan dikurung.

Seperti di sekolah menengah

Mari kita ingat pelajaran matematik kita, khususnya fungsi:
Biarkan f(x) = 2*x, fungsi yang mendarab dengan 2 nilai yang dihantar kepadanya. Mari namakannya Double.

Jadi Ganda(3) = 2*3 = 6
Dan Ganda(4) = 2*4 = 8.
Mudah.

Sama untuk f(x) = x 1, atau Penambahan.

Tambahan(3) = 3 1 = 4
Kenaikan(4) = 4 1 = 5
Sangat mudah.

Pengiraan lambda

Pengiraan lambda boleh ditulis dengan cara yang sama:
f(x) = x ialah sebagai contoh fungsi yang mengembalikan nilai yang dihantar kepadanya.
Fungsi ini dipanggil I, atau Idiot atau Identiti, dan merupakan salah satu asas kalkulus lambda.

Jadi Identiti(3) = 3
Dan Identiti(4) = 4.
Terlalu mudah.

Ada yang lain, kurang jelas, tetapi utiliti lambda-calculus telah ditemui:
f(x, y) = x ialah K, Kestrel atau Pemalar: fungsi yang mengembalikan hujah pertamanya.

Malar(3, foo) = 3
Malar(foo, 5) = foo

Ini satu lagi:
f(x) = x(x) ialah M, Mockingbird atau Memohon Sendiri.

Tetapi ia terlalu berpintal untuk menggunakannya dengan nombor:
f(3) = 3(3) = 3 tidak masuk akal, hujah 3 harus menjadi fungsi untuk digunakan secara bergilir-gilir dengan hujah.

g(x) = foo di sini ialah fungsi yang mengembalikan foo setiap kali! Hebat, kita panggil dia Dummy.

Jadi, jika Memohon Sendiri ialah f(x) = x(x)
Dan Dummy ialah g(x) = foo

So Self-Apply(Dummy) = Dummy(Dummy) = foo
Ya, Dummy terpakai pada dirinya sendiri, dan kerana Dummy sentiasa kembali foo, kami memperoleh foo dengan baik.

Keajaiban bermula

Sifat gabungan pengiraan lambda menjadikannya sangat mudah untuk difahami dan dimanipulasi, tetapi juga untuk ditemui semula.
Cuma uji semua perkaitan dan gabungan yang mungkin, dengan bilangan istilah tertentu, untuk mencari semua fungsi yang benar-benar berbeza dan berguna.

Sebagai contoh, kami mendapati bahawa f(x, y, z) = x(y(z)) ialah fungsi yang sangat berguna, dan kami memanggilnya B, Bluebird atau Karang.
Apa yang anda perlu lakukan ialah lulus 2 fungsi dan nilai untuk mendapatkan hasil daripada rantaian operasi yang dijalankan pada hujah ke-3 ini.

Karang(Kenaikan, Kenaikan, 3) = Kenaikan(Kenaikan(3)) = Kenaikan(4) = 5
Kompaun(Berganda, Berganda, 10) = Berganda(Berganda(10)) = Berganda(20) = 40
Kompaun(Karang(Kenaikan, Kenaikan), Berganda, 10) = (Karang(Kenaikan, Kenaikan))(Kembar(10)) = Kenaikan(Kenaikan(20)) = Kenaikan(21) = 22

Projek yang agak gila

Saya sedang memulakan projek menemui semula semua fungsi berguna lambda-calculus dan melaksanakannya dalam JavaScript.
Saya akan mendapatkan bantuan daripada rakan, Claude, untuk bergerak ke hadapan dengan lebih pantas dengan menjana semua kombinasi yang mungkin dan mengujinya.

Adakah dia akan berjaya? Dan kita, adakah kita akan menghayati dan merasai apa yang dilalui oleh Gereja Alonzo pada tahun 1936?

Harapan yang lebih gila: bolehkah kita menemui perkara baharu dengan mencari kesempurnaan gabungan ini?

Atas ialah kandungan terperinci Maieutik lambda-calculus. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!