Özyineleme (Recursion) teoremi nedir? T, t:Ʃ^*×Ʃ^*→Ʃ^* fonksiyonunu hesaplayan bir Turing makinesi olsun. Ve bir r:Ʃ^*→Ʃ^* fonksiyonunu hesaplayan, her bir w için r(w)=t(,w) olan bir R Turing makinesi olsun. Kendi tanımını elde edip ardından bununla hesaplama yapabilen bir Turing makinesi yapmak için yalnızca, makinenin tanımını ekstra bir giriş olarak alan, yukarıda belirtildiği gibi bir T makinesi>>>
Etiket Arşivleri: Hesaplanabilirlik Teorisi
Hesaplama teorisi (Theory of computation) bilgisayar biliminin bir problemin belirli bir algoritma ve hesap modeli ile çözülüp çözülemeyeceğini veya çözülürse ne kadar hızlı ve verimli bir şekilde çözüleceğini inceleyen bilim dalıdır. Başlıca 2 dala ayrılır: Karmaşıklık Teorisi (Complexity Theory) ve Hesaplanabilirlik Teorisi (Computability Theory). Karmaşıklık teorisi genelde karar verme problemleri (decision problems) ile uğraşır. Karar>>>