Hesaplanabilir izomorfizm - Computable isomorphism

İçinde hesaplanabilirlik teorisi iki set ${ displaystyle A; B subseteq mathbb {N}}$ nın-nin doğal sayılar vardır hesaplanabilir izomorfik veya özyinelemeli izomorfik eğer varsa Toplam önyargılı hesaplanabilir işlev ${ displaystyle f iki nokta üst üste mathbb {N} - mathbb {N}}$ ile ${ displaystyle f (A) = B}$ . Tarafından Myhill izomorfizm teoremi,^[1] hesaplanabilir izomorfizm ilişkisi, bire bir indirgeme ilişkisiyle çakışır.

İki Numaralandırmalar ${ displaystyle nu}$ ve ${ displaystyle mu}$ arandı hesaplanabilir izomorfik hesaplanabilir bir bijeksiyon varsa ${ displaystyle f}$ Böylece ${ displaystyle nu = mu circ f}$

Hesaplanabilir olarak izomorfik numaralandırmalar, bir kümede aynı hesaplanabilirlik kavramını tetikler.

Referanslar

^ Teorem 7.VI, Hartley Rogers, Jr., Özyinelemeli fonksiyonlar teorisi ve etkili hesaplanabilirlik

Rogers, Hartley, Jr. (1987), Özyinelemeli fonksiyonlar teorisi ve etkili hesaplanabilirlik (2. baskı), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, BAY 0886890.

P ≟ NP

Bu teorik bilgisayar bilimi –İlgili makale bir Taslak. Wikipedia'ya şu yolla yardım edebilirsiniz: genişletmek.

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

[1] Teorem 7.VI, Hartley Rogers, Jr., Özyinelemeli fonksiyonlar teorisi ve etkili hesaplanabilirlik

[1]