Hesaplanabilirlik teorisi

Özyinelemeli fonksiyon teorisi olarak da bilinen hesaplanabilirlik teorisi, algoritmaların ve bunlarla ilişkili bilgi işlem cihazlarının özelliklerini inceleyen matematiksel mantığın bir dalıdır. Bilgisayar biliminin temelidir ve teorik bilgisayar bilimindeki karmaşıklık teorisi ve algoritmik bilgi teorisi gibi diğer teorilerle yakından ilişkilidir.

Hesaplanabilirlik teorisinin temeli, bir fonksiyonun ancak ve ancak bir Turing makinesi tarafından hesaplanabilmesi durumunda hesaplanabileceğini belirten Church-Turing tezidir. Hesaplanabilir bir fonksiyon, bilgisayarda yazılabilen ve değerlendirilebilen herhangi bir algoritma, formül veya kuraldır. Bilgisayarlarda kullanılan tüm algoritmalar hesaplanabilirlik teorisine dayanmaktadır.

Teori, 1930'larda Alan Turing'in çalışmalarından başlayarak bir dizi farklı araştırmacı tarafından geliştirildi. 1950'lerin sonlarında teori iyice geliştirildi ve otomat teorisi, programlama dilleri ve yapay zeka gibi diğer alanlara da uygulandı. Hesaplama teknolojisi ilerledikçe hesaplanabilirlik teorisinin teorileri ve uygulamaları da gelişti.

Hesaplanabilirlik teorisi, algoritmaların karmaşıklığını ve bunların nasıl çözülebileceğini analiz etmenin yanı sıra bilgisayarların sınırlamalarını anlamak için kullanılır. Ayrıca algoritmaların doğruluğunu kanıtlamak için de kullanılır. Son olarak, fonksiyonların ve yüklemlerin ifade edilmesi ve hesaplanmasındaki sınırlamaları incelemek için kullanılır.