Hesaplanamayan Fonksiyonlar: Hesaplamanın Sınırlarını Anlamak

Hesaplanabilirlik teorisinde, bir fonksiyon herhangi bir algoritma tarafından hesaplanamıyorsa hesaplanamaz olarak adlandırılır. Başka bir deyişle, fonksiyonun çıktısını üretmek için giriş verilerine uygulanabilecek herhangi bir prosedür yoktur. süresiz olarak. Bu işlev hesaplanamaz çünkü belirli bir programın durup durmayacağını belirleyebilecek genel bir algoritma yoktur. Hesaplanamayan işlevlerin diğer örnekleri arasında belirli bir Turing makinesinin durmadan önce kaç adım atacağını soran Meşgul Kunduz işlevi ve Belirli bir resmi sistemin tutarlı mı yoksa tutarsız mı olduğunu soran Entscheidungsproblem. Bu işlevler aynı zamanda herhangi bir algoritma tarafından hesaplanamadıkları için hesaplanamazlar.