Alonzo Church: Arsitek Kecerdasan Komputer yang Terlupakan

• Alonzo Church tidak sepopuler Alan Turing di kalangan umum, tetapi ia adalah logikawan yang membangun fondasi logis komputasi melalui λ-calculus dan teori komputabilitas
• Church-Turing thesis pada 1936 menyediakan kerangka bahwa fungsi yang dapat dihitung secara efektif dapat dihitung oleh Turing machine atau sistem yang setara dengannya
• Terhadap Entscheidungsproblem dari Hilbert, ia memberikan jawaban bahwa tidak ada algoritme deterministik yang dapat memutuskan semua pernyataan matematika, sehingga memperjelas batas-batas komputasi
• Di Princeton, ia membimbing Stephen Kleene, J. Barkley Rosser, Alan Turing, dan lainnya; Turing menyelesaikan Ph.D. di bawah bimbingan Church
• Karya abstraknya tetap berada dalam silsilah komputasi yang berlanjut hingga compiler modern, interpreter, pemrograman fungsional, aplikasi smartphone, dan AI

---

Pengaruh Teoretis yang Lebih Besar daripada Ketenaran Publik

• Alan Turing lebih sering disebut dalam sejarah populer komputasi dan kecerdasan buatan melalui Turing Test, tetapi Church adalah sosok yang sangat memengaruhi pemikiran dan karya Turing
• Karya Church menjadi fondasi penting dalam memahami apa itu komputasi dan membentuk konsep untuk mengevaluasi AI
• Tanpa kontribusi Church, konsep kita saat ini tentang kecerdasan buatan dan cara mengevaluasinya mungkin akan sangat berbeda

Kehidupan dan Kecenderungan Akademik

• Church adalah logikawan pendiam dan tidak banyak bicara yang lahir pada 14 Juni 1903 di Washington, D.C.
• Ada catatan bahwa pada masa kecilnya ia kehilangan penglihatan atau sebagian penglihatan pada satu mata akibat kecelakaan senapan angin
• Setelah menyelesaikan preparatory school di Connecticut pada 1920, ia memulai pendidikan sarjana di Princeton pada tahun yang sama, lalu menyelesaikan program doktor pada 1927
• Setelah menghabiskan waktu sebagai National Research Fellow di Harvard, Göttingen, dan Amsterdam, ia kembali ke Princeton dan membangun sebagian besar pencapaian akademiknya di sana
• Ia dikenal karena tulisan papan tulisnya yang rapi dan sifatnya yang teliti, bahkan pernah melapisi makalah penting dengan Duco cement untuk mengawetkannya

λ-calculus dan Komputabilitas

• Kontribusi terdalam Church adalah λ-calculus, yang menjadi fondasi sebelum nama ilmu komputer muncul
• Pada 1936, Church memformalkan Church-Turing thesis, konsep inti dalam ilmu komputer teoretis
  • Isinya adalah bahwa fungsi yang dapat dihitung secara efektif dapat dihitung oleh Turing machine atau sistem yang setara dengannya
  • Ini menyediakan kerangka untuk memahami apa yang secara teoretis dapat dilakukan oleh mesin
  • Sekaligus memperlihatkan batas yang dapat dijangkau oleh prosedur algoritmik
• Proposisi ini merupakan konsep fundamental, tetapi masih menyisakan perdebatan dan batasan seputar penafsiran ‘effective computability’, komputasi fisik, dan hakikat kecerdasan manusia
• Jika Turing mengusulkan Turing machine yang menerjemahkan prosedur mekanis ke bentuk logis, Church menyediakan abstraksi murni yang menopang mesin semacam itu secara teoretis

Pemrograman Modern dan Cara Berpikir Fungsional

• Pengaruh λ-calculus juga terlihat dalam prinsip penulisan program saat ini, terkait dengan cara yang menekankan komposisi, higher-order function, dan imutabilitas
• Sistem formal ini memungkinkan masalah matematika abstrak dikodekan dan diselesaikan secara mekanis, serta menjadi fondasi arsitektur compiler dan interpreter modern
• Bagi programmer modern, λ-calculus dapat tampak seperti kumpulan fungsi bersarang yang terlihat dalam Lisp, Haskell, serta beberapa paradigma di Python atau JavaScript
• Abstraksi λ-calculus menjadi dasar pemrograman fungsional yang memperlakukan fungsi sebagai first-class citizen

Entscheidungsproblem dan Batas Komputasi

• Church juga memberi kontribusi penting pada bidang lain dalam logika dan filsafat, dengan contoh utama karyanya atas Entscheidungsproblem
• Entscheidungsproblem adalah masalah keputusan yang diajukan David Hilbert pada 1928, yang menanyakan apakah ada algoritme deterministik yang dapat memutuskan benar atau tidaknya pernyataan matematika apa pun
• Church memberikan jawaban negatif bahwa algoritme semacam itu tidak ada, dan hasil ini dikenal sebagai Church's Theorem
• Temuan ini sangat memengaruhi teori keputusan dan menekankan batas dari apa yang dapat dicapai hanya melalui komputasi

Pusat Intelektual Princeton dan Para Muridnya

• Church adalah mentor yang membimbing para logikawan dan ilmuwan komputer penting pada masanya
• Silsilah akademiknya mencakup Stephen Kleene, J. Barkley Rosser, dan Alan Turing
• Turing menyelesaikan Ph.D. di Princeton di bawah bimbingan Church
• David Kaplan dikisahkan menganjurkan mahasiswa pascasarjana baru untuk mengikuti kelas Church, dengan mengatakan bahwa meskipun itu bukan bidang minat mereka, pengalaman tersebut akan menjadi sesuatu yang kelak mereka ceritakan kepada cucu-cucu mereka
• Pada 1930-an, Princeton adalah pusat intelektual perkembangan logika modern, dengan hadirnya John von Neumann, Kurt Gödel, dan Church

Warisan yang Kurang Terlihat

• Church tidak memperoleh ketenaran publik pada tingkat yang sama dibanding Turing, von Neumann, Gödel, dan lainnya
• Warisannya tidak berbentuk kisah yang mudah menarik imajinasi publik, seperti kepahlawanan pemecahan sandi masa perang atau tragedi kematian dini
• Miliaran program yang berjalan di smartphone dapat ditelusuri logikanya hingga ke fungsi abstrak dalam λ-calculus
• Dari aplikasi sederhana hingga kecerdasan buatan, DNA komputasi yang tak terlihat mewarisi silsilah penting dari karya Church
• Kejeniusan Church tidak terletak pada spektakel, melainkan pada struktur yang ketat dan keanggunan sunyi yang mengubah dunia

[GN⁺]

Komentar Hacker News

• Saya menyukai asal-usul nama lambda yang dijelaskan dalam Paradigms of Artificial Intelligence Programming (PDF/EPUB: https://github.com/norvig/paip-lisp)
  Ceritanya, Alonzo Church mencoba mengubah tanda caret yang dipakai di atas variabel terikat dalam notasi Principia Mathematica karya Russell dan Whitehead, x̂(x + x), menjadi string satu dimensi dengan memindahkannya ke depan seperti ^x(x + x). Karena caret kosong itu terasa janggal, ia menggantinya dengan lambda kapital Λx(x + x), lalu untuk menghindari kebingungan akhirnya menjadi huruf kecil λx(x + x)
  Disebutkan juga bahwa John McCarthy adalah murid Church di Princeton, dan ketika ia membuat Lisp pada 1958, keypunch saat itu tidak memiliki huruf Yunani, sehingga ia memakai (lambda (x) (+ x x)), yang bertahan sampai sekarang
  Jadi, seperti tema tulisan ini, Church sering muncul dalam retrospektif tentang Lisp, dan mungkin hanya bisa disebut “terlupakan” bagi orang-orang yang hampir tidak berminat pada sejarah komputasi

  • Saya berharap asal-usul itu punya makna lebih dari sekadar simbol yang sulit dipahami, tetapi tampaknya tidak demikian
    Menurut Dana Scott, Church sendiri menyebut pilihan itu sebagai pilihan acak ala “eeny, meeny, miny, moe”, dan penjelasan ala Barendregt juga konon dibantah dalam kuliah terbaru di University of Birmingham
    Di dunia berbahasa Prancis, “personne lambda” berarti orang biasa/orang anonim, sehingga tampak cocok dengan fungsi anonim, dan adjektiva lambda juga berarti “umum/biasa”; jadi memang ada kesan bahwa huruf yang kira-kira berada di tengah alfabet Yunani melambangkan sesuatu yang rata-rata
    https://math.stackexchange.com/questions/64468/why-is-lambda...
  • Katanya “Lisp biasanya menyukai nama yang ekspresif”, tetapi selain lambda, car/cdr juga, meski bukan huruf Yunani, sama sekali bukan nama yang transparan
  • PAIP memang topik kecerdasan buatannya sendiri sudah cukup termakan zaman, tetapi secara keseluruhan tetap buku yang sangat bagus
    Buku itu membahas banyak topik pemrograman, dan bagi orang yang belum banyak terpapar pemrograman fungsional, ia juga membuka paradigma yang bisa terasa asing
  • Tidak jelas apakah kisah yang terus diulang tentang asal-usul notasi lambda Alonzo Church ini benar
    Contoh lain yang mengisyaratkan bahwa Church memilihnya lebih sebagai pilihan acak di antara huruf-huruf Yunani, bukan karena makna tertentu, ada di https://en.wikipedia.org/wiki/Lambda_calculus#Origin_of_the_...
  • Saya penasaran siapa yang pertama kali mencetuskan istilah lambda calculus
    Saya juga penasaran apakah itu sebelum atau sesudah McCarthy memulai Lisp

• “Kalkulus lambda Church dan mesin Turing memiliki kemampuan komputasi yang setara, tetapi mesin Turing berbeda karena memakai state yang dapat berubah. Hingga hari ini pun, adanya jurang antara bahasa fungsional dan bahasa imperatif disebabkan oleh pemisahan Church dan state”
  Saya sudah lama mengetahui kutipan ini, tetapi tidak bisa menemukan sumber aslinya
  Edit: Mungkin asalnya dari ucapan Guy Steele: “Ada orang-orang yang tidak ingin mencampur bagian bahasa yang fungsional/berbasis kalkulus lambda dengan bagian yang menimbulkan efek samping. Tampaknya mereka percaya pada pemisahan Church dan state”

  • Kutipan Guy itu berasal dari mailing list MIT yang berlanjut dari Lightweight Languages Workshop 2001
    Arsip aslinya ada di sini: https://people.csail.mit.edu/gregs/ll1-discuss-archive-html/...
  • Saya juga teringat lelucon nama Niklaus Wirth
    Leluconnya, orang Eropa umumnya mengucapkan namanya dengan benar sebagai “Nick-louse Veert”, tetapi orang Amerika merusaknya menjadi “Nickel's Worth”
    Artinya, orang Eropa memanggilnya dengan nama, sedangkan orang Amerika memanggilnya dengan nilai
    https://en.m.wikiquote.org/wiki/Niklaus_Wirth
  • Sepertinya berasal dari Peter Norvig. Lihat komentar saudara

• Jika ingin membaca tulisan yang benar-benar menakjubkan tentang Church, saya merekomendasikan memoar Rota
  Bagian pertamanya di https://www34.homepage.villanova.edu/robert.jantzen/princeto...
  Tautan terkait: Alonzo Church, 92, Theorist of the Limits of Mathematics (1995) - https://news.ycombinator.com/item?id=12240815 - Agustus 2016, Gian-Carlo Rota on Alonzo Church (2008) - https://news.ycombinator.com/item?id=9073466 - Februari 2015

  • Memoar Rota bukan hanya bagian tentang Church; seluruh halaman webnya, yaitu “Fine Hall in its golden age: Remembrances of Princeton in the early fifties”, adalah satu bab dari bukunya Indiscrete Thoughts
    Seluruh bukunya layak dibaca

• Bahasa pemrograman Alonzo yang dinamai menurut dirinya hampir terlupakan
  https://dl.acm.org/doi/pdf/10.1145/68127.68139

• Secara khusus, filsafat logika yang melanjutkan karya Frege dan Russell serta teori makna/rujukan sebagian besar telah terlupakan
  Church menerbitkan banyak makalah tentang topik ini, tetapi di tempat seperti Wikipedia hal itu hampir tidak dibahas
  Meski begitu, entri Stanford Encyclopedia of Philosophy sedikit lebih baik: https://plato.stanford.edu/entries/church/
  Namun saya dengar itu pun melewatkan sebagian karya utamanya, dan sepertinya terlalu filosofis bagi matematikawan serta terlalu teknis bagi filsuf

  • Terkait hal ini, E.J. Lemmon, saat menyebut buku-buku logika penting dalam Beginning Logic, menulis bahwa Bab 0 dari Introduction to Mathematical Logic karya Church layak dibaca berkali-kali oleh semua filsuf

• Ini bukan poin utama, tetapi saya berharap orang agak menahan diri dalam memakai ilustrasi buatan AI di tulisan blog
  Foto asli Church juga ada di domain publik, sementara ilustrasi ini tidak terlalu mirip dengannya dan, seiring tulisan itu menjadi populer, sudah muncul di hasil pencarian gambar
  Kalau ilustrasinya bahkan tidak layak dibuat lebih dari 5 menit, bukankah lebih baik dihilangkan saja?
  Meski begitu, jika memang harus memakai gambar buatan “AI”, setidaknya harus diberi keterangan demikian

  • Terima kasih atas koreksinya, dan maaf
    Saya enggan mengambil foto dari internet, dan gambar ini adalah hasil ke-7 yang saya buat agar tidak menjadi sosok mirip yang ‘palsu’; saya merasa kemiripannya cukup ada
    Gambar JvN cukup berhasil dibuat, tetapi ke depan tampaknya lebih tepat memakai gambar simbolis alih-alih sosok mirip palsu yang terlihat seperti manusia

• Ungkapan “arsitek kecerdasan komputer” rasanya berlebihan
  Memang benar Church adalah logikawan yang hebat, tetapi jika kecerdasan komputer di sini berarti AI/ML, kontribusinya praktis tidak ada
  Secara terpisah, saya juga tidak begitu yakin lambda calculus benar-benar matematika; tampaknya lebih dekat ke notasi yang cerdik
  Keunggulan notasi bersifat subjektif, dan menarik juga bahwa Church tidak terlalu peduli bahwa idenya menginspirasi desain bahasa pemrograman tertentu

  • “Lambda calculus” kadang berarti simply typed lambda calculus, yang terutama merujuk pada simple type theory (STT), yaitu “teori tipe Church”
    STT juga sering disamakan dengan logika orde-tinggi, karena hanya dengan dua tipe primitif—“objek” dasar dan nilai kebenaran T/F—serta tipe fungsi (a --> b), ia dapat mengekspresikan objek logis apa pun
    STT jelas merupakan penemuan Church, sangat memengaruhi teori tipe modern, dan juga memengaruhi bahasa pemrograman dengan sistem tipe kompleks seperti Haskell

• Saya tidak bisa membuktikannya sepenuhnya, tetapi secara intuitif Turing dan hal-hal yang ia wakili pada akhirnya sangat dihargai di ranah AI, sementara Church tampak sebaliknya
  Yang pertama berangkat dari kemurnian, kondisi minimum yang mungkin, dan komputasi abstrak yang “murni”, sedangkan yang kedua tampaknya lebih tertarik pada bagaimana kita benar-benar dapat berpikir, serta lebih memperhatikan ekspresi dan perluasan abstraksi daripada implementasi

  • Dari satu sudut pandang, Turing membuat komputer praktis selama perang, tetapi kemudian dicegah oleh pemerintahnya sendiri untuk terus membuat komputer sehingga harus mundur ke teori
    Church tidak punya pengalaman praktik komputer dan lebih condong memperluas teori matematika itu sendiri
    Kolaborasi dan komunikasi mereka melintasi Atlantik memadukan praktik dan teori, lalu mengokohkan teori-teori inti seperti dualitas imperatif/fungsional, teorema Church-Turing, serta hubungan antara masalah penghentian dan teorema Church
    Melihatnya sebagai persaingan itu keliru, dan ungkapan bahwa ilmu komputer memiliki “dua bapak” tepat karena berbagai alasan
    Terlebih lagi jika mengingat kematian Turing
    Juga, tidak boleh dilupakan bahwa Turing bukannya tidak tertarik pada implementasi; ia ingin kembali ke implementasi nyata, tetapi tidak diizinkan
    Ada tragedi dan pertanyaan besar tentang apa yang akan berubah seandainya klasifikasi rahasia pemerintah Inggris berbeda, tetapi jika begitu, mungkin kita juga akan kehilangan kolaborasinya dengan Church yang dalam lini masa kita berhasil memantapkan teori dengan begitu baik

• Saya beruntung bisa bertemu Alonzo Church dan Haskell Curry di ACM Symposium on LISP and Functional Programming yang diadakan di CMU pada Agustus 1982
  Curry jelas sedang kurang sehat dan meninggal sekitar dua minggu setelah konferensi, tetapi Church tampak sehat dan hidup sekitar 13 tahun lagi setelah itu
  Di resepsi, Gerry Sussman tampak sangat bersemangat saat berkeliling ruangan memperkenalkan keduanya, dan bagi kami pun bertemu mereka adalah pengalaman yang sangat mengharukan

• Salah satu kontribusi besar Church adalah para muridnya
  Dari satu tempat itu lahir sederet pemikir luar biasa