alonso church
tarafından ortaya atılmıştır.
lambda calculus ile ilgili en kaydadeğer*
nokta şudur:alan turing
, bir makine ve bir teyp (ikisinin toplamı: turing machine
)'i kullanarak neyin hesaplanabilir *
olup neyin hesaplanamaz olduğunu açıklayan ilk adamdır.
o zamana kadar, bu turing makinesinin öncesinde, turing makinesi
kadar esnekliği/hesaplama kabiliyeti olmayan türde automaton'lar üzerine de çalışılmıştır.
örneğin deterministic finite automaton'lar vardır, a^(n).b^(n) şeklinde bir inputu kabul edecek bir deterministic finite automaton
bulamazsınız. o iş dfa'ler için hesaplanabilir değildir.
örneğin pushdown automata
vardır, biraz önceki söylediğimi bulur; fakat a^(n).b^(2n).c^(n) şeklindeki bir inputu kabul edemez.
bu arada, bu iki örnekte bahsettiğim başarısız olma durumları pumping lemma
denilen bir lemma
ile kanıtlanabilir.
tabii bunlardan sonra alan turing'in çıkıp 'bu makine hesaplanabilen her şeyi hesaplar' *
demesiyle yer yerinden oynuyor. burada bahsettiği 'hesaplanabilen' tanımı, bu makineye bağımlı bir tanım oluyor.
fakat alonso church, lambda calculus'u ile sahneye çıktığında, ortada artık bir makine falan yok. church, alan turing'in hesaplanabilir dediği şeyleri birebir açıklayan, ve bunu sadece soyut matematik kullanarak yapan bir mekanizma icat ediyor aslında.
computability (hesaplanabilirlik) konseptini 'bir makinenin çalışmasından meydana gelen bir süreç' olmaktan çıkarıyor church. işte bu yüzden çok önemlidir lambda calculus.