Özyineleme (Recursion) teoremi nedir?

Ö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 yapmak gerekir. Ardından recursion teoremi, tıpkı T gibi çalışan ancak tanımı otomatik olarak yapılmış yeni bir R makinesi üretir.

Başka bir açıdan:

Özyineleme (Recursion) teoremi, hesaplanabilirlik teorisinde ileri düzey çalışmalarda önemli bir rol oynayan matematiksel bir yaklaşımdır. Matematiksel mantığa, kendi kendini yeniden üreten sistemlerin teorisine ve hatta bilgisayar virüslerine bağlantıları vardır.

Özyineleme (Recursion) teoremini izah etmek için yaşam araştırmasında kullanılan bir paradokstan bahsedelim. Kendi kopyalarını oluşturabilen makineler yapma ihtimali var mıdır? sorusuna cevap aranmaktadır.

1. Canlılar makinelerdir.
2. Canlılar kendiliğinden çoğalabilirler.
3. Makineler kendi kendine çoğalamazlar.

Özyineleme (Recursion) teoremi 3.durumun yanlış olduğunu ortaya koyar.

Özyineleme (Recursion) teoremi:

T, t:E*xE*->E* fonksiyonunu işleyen bir Turing makinesidir. R, r:E*->E* fonksiyonunu her w girdisi için işleyen bir Turing makinesidir. r(w)=t(,w).

Bu tanıma göre T Turing Makinesi, R Turing makinesini otomatik olarak üretir.

Bilgisayar virüsleri, kendi kendilerine çoğalan bir yapıdadırlar.

Videolu anlatım: