lambda calculus

• (bkz: alan turing)'in doktora supervisoru olan (bkz: alonso church)'ün "hesaplanabilirlik bakış açısıyla bakıldığında işlev kavramı nasıl olmalıdır?" sorusuna verdiği fonksiyonel tabanlı cevaptır "lambda calculus". turing makineleri de aynı soruya durum tabanlı bir çözüm getirdiğinden, sıklıkla beraber anılırlar. (bkz: chuch-turing hipotezi).
  
  church'e göre bir fonksiyon, içine bakmamanız gereken bir kara kutudur. bu fonksiyon bazı girdiler alır, bunları bir şekilde işler ve bir çıktı üretir. fonksiyonun işleme mantığı önemli değildir ancak "pure" olmaları şarttır. yani: girdiler harici bir parametreye (duruma) bağlı olarak ürettikleri sonuç değişmez ve yan etki de üretmezler. bu açıdan bakıldığında durum tabanlı turing makineleri ile taban tabana zıttır denebilir.
  
  lx. x+1
  lx.ly x+y
  
  şeklinde yazılırlar.
  
  bu notasyon kullanarak sıralı satırların işlenmesi rutini ile çalışan veya gelecekte çalışacak herhangi bir program kodlanabilir (aynı turing makinelerinde olduğu gibi).
  
  bu bilgilere dayanarak, turing makineleri ile kodlanabilen herhangi bir programın lambda calculus ile; lambda notasyonu ile kodlanabilen her programın turing makineleri ile kodlanabileceğini söyleyebiliriz.
  
  ml ailesi ve haskell gibi fonksiyonel programlama dillerinin temelinde lambda calculus yatar. son beş on yıldır bilinen bir çok oop programa dili de lambda calculus'u temel özellik olarak sunmaktadır.