UTM teoremi - UTM theorem

Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (Ağustos 2019) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

İçinde hesaplanabilirlik teorisi, UTM teoremveya evrensel Turing makinesi teorem, hakkında temel bir sonuçtur Gödel numaralandırması setinin hesaplanabilir işlevler. Bir hesaplanabilirin varlığını doğrular evrensel işlev, başka herhangi bir hesaplanabilir işlevi hesaplayabilen.^[1] Evrensel işlev, evrensel Turing makinesi, teoremin adı budur.

Roger eşdeğer teoremi hesaplanabilir fonksiyonların Gödel numaralandırmasının karakterizasyonu s_mn teorem ve UTM teoremi.

Teoremi

Teorem, bir kısmi hesaplanabilir işlev sen hesaplanabilir her işlev için iki değişken vardır. f tek değişkenli e öyle var ki ${ displaystyle f (x) simeq u (e, x)}$ hepsi için x. Bu, her biri için xya f(x) ve sen(e,x) hem tanımlıdır hem de eşittir veya her ikisi de tanımsızdır.^[2]

Teorem böylece, φ_e(x) gibi sen(e, x), sıra φ₁, φ₂,… Kısmi hesaplanabilir fonksiyonların bir numaralandırmasıdır. İşlev ${ displaystyle u}$ teoremin ifadesine evrensel fonksiyon denir.

Referanslar

• Rogers, H. (1987) [1967]. Özyinelemeli Fonksiyonlar Teorisi ve Etkili Hesaplanabilirlik. İlk MIT basın ciltsiz baskısı. ISBN  0-262-68052-1.CS1 bakimi: ref = harv (bağlantı)
• Soare, R. (1987). Özyinelemeli olarak numaralandırılabilir kümeler ve dereceler. Matematiksel Mantıkta Perspektifler. Springer-Verlag. ISBN  3-540-15299-7.CS1 bakimi: ref = harv (bağlantı)

Bu matematiksel mantık ile ilgili makale bir Taslak. Wikipedia'ya şu yolla yardım edebilirsiniz: genişletmek.