Beräknbart otaliga - Computably enumerable

I beräkningsteorin kallas en uppsättning S av naturliga tal för beräkningsbart uppräkningsbara (ce) , rekursivt uppräkningsbara (om) , halvavgörbara , delvis avgörbara , listbara , bevisbara eller Turing-igenkännliga om:

• Det finns en algoritm så att uppsättningen ingångsnummer för vilka algoritmen stannar är precis S .

Eller, på motsvarande sätt,

• Det finns en algoritm som räknar medlemmarna i S . Det betyder att dess utmatning helt enkelt är en lista över alla medlemmar i S : s ₁ , s ₂ , s ₃ , .... Om S är oändligt kommer denna algoritm att köra för alltid.

Det första villkoret antyder varför termen semidecidable ibland används. Mer exakt, om ett tal finns i uppsättningen, kan man bestämma detta genom att köra algoritmen, men om numret inte finns i uppsättningen körs algoritmen för alltid och ingen information returneras. En uppsättning som är "helt avgörbar" är en beräknad uppsättning . Det andra villkoret föreslår varför beräknbart uppräkningsbart används. Förkortningarna ce och re används ofta, även i tryck, istället för hela frasen.

I beräkningskomplexitet teori , den komplexitet klassen är innehåller alla computably uppräknings set RE . I rekursionsteori betecknas gitteret av ce -uppsättningar som ingår . ${\ displaystyle {\ mathcal {E}}}$

Formell definition

En uppsättning S av naturliga tal kallas computably uppräkningsbar om det finns en partiell beräkningsbar funktion vars område är exakt S , vilket innebär att funktionen definieras om och endast om dess ingång är medlem i S .

Ekvivalenta formuleringar

Följande är alla ekvivalenta egenskaper hos en uppsättning S med naturliga tal:

Semidecidability:

• Uppsättningen S kan beräknas räknas. Det vill säga, S är domänen (co-range) för en delberäknbar funktion.
• Det finns en delberäknbar funktion f så att:
  $${\ displaystyle f (x) = {\ begin {cases} 1 & {\ mbox {if}} \ x \ i S \\ {\ mbox {odefinierad/stannar inte}} \ & {\ mbox {if}} \ x \ notin S \ end {case}}}$$

  

Uppräkningsbarhet:

• Uppsättningen S är intervallet för en delberäknbar funktion.
• Uppsättningen S är intervallet för en total beräkningsbar funktion, eller tom. Om S är oändligt kan funktionen väljas för att vara injektiv .
• Uppsättningen S är intervallet för en primitiv rekursiv funktion eller tom. Även om S är oändligt kan värden upprepas i detta fall.

Diofantin:

• Det finns ett polynom p med heltalskoefficienter och variabler x , a , b , c , d , e , f , g , h , i som sträcker sig över de naturliga talen så att
  $${\ displaystyle x \ i S \ Vänsterhögerpil \ existerar a, b, c, d, e, f, g, h, i \ (p (x, a, b, c, d, e, f, g, h, i) = 0).}$$

  
  (Antalet bundna variabler i denna definition är det mest kända hittills; det kan vara att ett lägre antal kan användas för att definiera alla Diophantine -uppsättningar.)
• Det finns ett polynom från heltal till heltal så att uppsättningen S innehåller exakt de icke-negativa talen i sitt intervall.

Ekvivalensen av semidecidabilitet och uppräkningsbarhet kan erhållas med tekniken för samsvetsning .

Diofantiska karakteriseringar av en beräkningsbart uppräkningsbar uppsättning, även om de inte var lika enkla eller intuitiva som de första definitionerna, hittades av Yuri Matiyasevich som en del av den negativa lösningen på Hilberts tionde problem . Diophantine -uppsättningar föregår rekursionsteori och är därför historiskt sett det första sättet att beskriva dessa uppsättningar (även om denna ekvivalens bara anmärktes mer än tre decennier efter införandet av beräknbart otaliga uppsättningar).

En beräknad uppräkning av uppsättningen för alla Turing -maskiner som stannar på en fast ingång: Simulera alla Turing -maskiner (uppräknade på vertikal axel) steg för steg (horisontell axel) med hjälp av den visade diagonaliseringsplaneringen. Skriv ut dess nummer om en maskin avslutas. På så sätt skrivs så småningom ut antalet av varje avslutande maskin. I exemplet skriver algoritmen ut "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ..."

Exempel

• Varje beräknad uppsättning är beräknbart räknbar, men det är inte sant att varje beräknbart uppräkningsbar uppsättning är beräknbar. För beräkningsbara uppsättningar måste algoritmen också säga om en ingång inte finns i uppsättningen - detta krävs inte av beräkningsbart uppräkningsbara uppsättningar.
• Ett rekursivt uppräkningsbart språk är en beräknbart uppräkningsbar delmängd av ett formellt språk .
• Uppsättningen av alla bevisbara meningar i ett effektivt presenterat axiomatiskt system är en beräknbart uppräkningsbar uppsättning.
• Matiyasevichs sats säger att varje beräknbart uppräkningsbar uppsättning är en Diophantine -uppsättning (det motsatta är trivialt sant).
• De enkla uppsättningarna kan beräknas räknas men inte beräknas.
• De kreativa uppsättningarna kan beräknas räknas men inte beräknas.
• Alla produktiva uppsättningar är inte beräkningsbara.
• Med tanke på en Gödel -numrering av de beräkningsbara funktionerna är uppsättningen (var är Cantor -parningsfunktionen och indikerar definierad) beräknbart räknbar (jfr bild för ett fast x ). Denna uppsättning kodar stoppproblemet eftersom den beskriver ingångsparametrarna för vilka varje Turing -maskin stannar.${\ displaystyle \ phi}$${\ displaystyle \ {\ langle i, x \ rangle \ mid \ phi _ {i} (x) \ downarrow \}}$${\ displaystyle \ langle i, x \ rangle}$${\ displaystyle \ phi _ {i} (x) \ downarrow}$${\ displaystyle \ phi _ {i} (x)}$
• Med tanke på en Gödel -numrering av de beräkningsbara funktionerna är uppsättningen beräknbart räknbar. Denna uppsättning kodar för problemet med att bestämma ett funktionsvärde.${\ displaystyle \ phi}$${\ displaystyle \ {\ left \ langle x, y, z \ right \ rangle \ mid \ phi _ {x} (y) = z \}}$
• Med tanke på en partiell funktion f från de naturliga talen till de naturliga talen, är f en delberäknbar funktion om och endast om grafen för f , det vill säga uppsättningen av alla par så att f ( x ) definieras, kan beräknas räknas.${\ displaystyle \ langle x, f (x) \ rangle}$

Egenskaper

Om A och B är beräkningsbart uppräkningsbara uppsättningar är A ∩ B , A ∪ B och A × B (med det beställda paret av naturliga nummer mappade till ett enda naturligt tal med Cantor -parningsfunktionen ) beräkningsvärda mängder. Den preimage av en computably uppräkningsbar uppsättning under ett partiellt computable funktion är en computably uppräkningsbar uppsättning.

En uppsättning kan beräknas räknas om och bara om den ligger på den aritmetiska hierarkins nivå . ${\ displaystyle \ Sigma _ {1}^{0}}$

En uppsättning kallas co-computably-uppräkningsbar eller co-ce om dess komplement är beräknbart räknbart. På motsvarande sätt samsas en uppsättning om och bara om den ligger på den aritmetiska hierarkins nivå . Komplexitetsklassen för samberäknbart uppräkningsbara uppsättningar betecknas som co-RE. ${\ displaystyle T}$ ${\ displaystyle \ mathbb {N} \ setminus T}$${\ displaystyle \ Pi _ {1}^{0}}$

En uppsättning A är beräkningsbar om och endast om både A och komplementet till A är computably uppräkningsbar.

Vissa par beräknbart uppräkningsbara uppsättningar är effektivt separerbara och andra inte.

Anmärkningar

Enligt Church-Turings hypotes , är vilken som helst effektivt beräkningsfunktion kan beräknas av en Turing maskin , och sålunda en uppsättning S är computably uppräkningsbar om och endast om det finns någon algoritm som ger en uppräkning av S . Detta kan emellertid inte tas som en formell definition, eftersom tesen Church – Turing är en informell gissning snarare än ett formellt axiom.

Definitionen av en beräknbart uppräkningsbar uppsättning som domänen för en delfunktion, snarare än intervallet för en total beräkningsbar funktion, är vanlig i samtida texter. Detta val motiveras av det faktum att i generaliserade rekursionsteorier, såsom α-rekursionsteori , har definitionen som motsvarar domäner visat sig vara mer naturlig. Andra texter använder definitionen när det gäller uppräkningar, vilket är ekvivalent för beräkningsbart uppräkningsbara uppsättningar.

Referenser

• Rogers, H. Theory of Recursive Functions and Effective Computability , MIT Press . ISBN  0-262-68052-1 ; ISBN  0-07-053522-1 .
• Soare, R. Rekursivt otaliga uppsättningar och grader. Perspektiv i matematisk logik. Springer-Verlag , Berlin, 1987. ISBN  3-540-15299-7 .
• Soare, Robert I. Rekursivt otaliga uppsättningar och grader. Tjur. Amer. Matematik. Soc. 84 (1978), nr. 6, 1149–1181.