Bagaimana kombinator Y mencontohkan "inkonsistensi Lambda calculus"?

Di halaman Wikipedia untuk Fixed Point Combinators tertulis teks yang agak misterius

Penggabung Y adalah contoh dari apa yang membuat kalkulus Lambda tidak konsisten. Jadi harus dianggap dengan kecurigaan. Namun aman untuk mempertimbangkan kombinator Y ketika didefinisikan dalam logika matematika saja.

Sudahkah saya memasuki semacam novel mata-mata? Apa di dunia yang dimaksud dengan pernyataan bahwa kalkulus adalah "tidak konsisten" dan bahwa itu harus "dianggap dengan kecurigaan" ?$\lambda$

Ini terinspirasi dari peristiwa nyata, tetapi cara itu dinyatakan hampir tidak dikenali dan "harus dianggap dengan kecurigaan" adalah omong kosong.

Konsistensi memiliki makna yang tepat dalam logika: teori yang konsisten adalah teori di mana tidak semua pernyataan dapat dibuktikan. Dalam logika klasik, ini setara dengan tidak adanya kontradiksi, teori yaitu tidak konsisten jika dan hanya jika ada pernyataan sehingga teori membuktikan kedua A dan negasinya ¬ A .$A$$A$$\neg A$

Jadi apa artinya ini tentang kalkulus lambda? Tidak ada. Kalkulus lambda adalah sistem penulisan ulang, bukan teori logis.

Dimungkinkan untuk melihat kalkulus lambda dalam kaitannya dengan logika. Menganggap variabel mewakili hipotesis dalam sebuah bukti, abstraksi lambda sebagai bukti di bawah hipotesis tertentu (diwakili oleh variabel), dan aplikasi sebagai menyusun bukti kondisional dan bukti hipotesis. Kemudian aturan beta terkait dengan penyederhanaan bukti dengan menerapkan modus ponens , prinsip dasar logika.

$n=3$$n=2$

The Curry-Howard korespondensi adalah paralel antara diketik bate dan sistem bukti.

• jenis sesuai dengan pernyataan logis;
• istilah sesuai dengan bukti;
• tipe yang dihuni (yaitu tipe sedemikian sehingga ada istilah jenis itu) sesuai dengan pernyataan benar (yaitu pernyataan sedemikian sehingga ada bukti pernyataan itu);
• evaluasi program (yaitu aturan seperti beta) sesuai dengan transformasi bukti (yang lebih baik mengubah bukti yang benar menjadi bukti yang benar).

$Y$$Y (\lambda x.x)$

Ini tidak berarti untuk kalkulus lambda murni, yaitu untuk kalkulus lambda tanpa jenis.

Di banyak kalki yang diketik, tidak mungkin untuk mendefinisikan kombinator titik tetap. Kalkuli yang diketik itu berguna sehubungan dengan interpretasi logis mereka, tetapi bukan sebagai dasar untuk bahasa pemrograman Turing-lengkap. Di beberapa kalki yang diketik, dimungkinkan untuk menentukan kombinator titik tetap. Kalkuli yang diketik tersebut berguna sebagai dasar untuk bahasa pemrograman Turing-lengkap, tetapi tidak sehubungan dengan interpretasi logis mereka.

Kesimpulannya:

• Kalkulus lambda tidak "tidak konsisten", konsep itu tidak berlaku.
• Sebuah diketik lambda kalkulus yang ditunjuk jenis untuk setiap jangka lambda tidak konsisten. Beberapa kalkulus lambda yang diketik adalah seperti itu, yang lain membuat beberapa istilah tidak dapat diketik dan konsisten.
• Kalkulus lambda yang diketik bukan satu-satunya raison d'etre untuk kalkulus lambda, dan kalkulus lambda yang diketik tidak konsisten adalah alat yang sangat berguna - hanya saja tidak untuk membuktikan sesuatu.

Saya ingin menambahkan satu ke apa yang dikatakan @Giles.

$\lambda$$\lambda$

$\lambda x.\lambda y.x$$a \to (b \to a)$$a \to b$$a$$b$$a \implies (b \implies a)$$\lambda x.\lambda y.xy$$(a \to b) \to (a \to b)$$(a \implies b) \implies (a \implies b)$

$\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$(a \to a) \to a$$(a \implies a) \implies a$

$(a \to a) \to a$

• $(a \to a) \to a$$\lambda$
• Hidup dengan sistem tipe yang tidak konsisten sebagai sistem deduksi logis.