Church-Turing tezi nedir? Açıklayınız?

Church-Turing tezi nedir? Açıklayınız?

Alonzo Church tarafından ortaya atılan teze göre, herhangi bir algoritma, herhangi bir donanımda çalışabiliyorsa, bu donanıma karşılık gelen bir Turing makinesi olduğudur. Daha basit bir ifadeyle, Turing makineleri, herhangi bir donanımın yaptığı algoritmasal işlemleri yerine getirebilir.

Church-Turing tezi:
Mekanik olarak yapılabilen her hesaplamayı yapabilecek bir Turing makinesi vardır.

Church-Turing tezine göre, Turing makinesiyle gerçekleştirilemeyen hesaplamalar karar verilemez (undecidable) olarak adlandırılır.

Church, algoritmaları tanımlamak için lambda-calculus adlı bir gösterge sistemi kullandı. Turing bunu makinesi ile yaptı. Bu iki tanımın eşdeğer olduğu gösterildi. Biçimsel olmayan algoritma anlayışı ile kesin tanım arasındaki bu bağlantı Church-Turing tezi olarak anılmaktadır.

Etiketler: , ,

Yorum Yapın