Uppräknat set

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 maj 2021; kontroller kräver 7 redigeringar .

En uppräknad uppsättning ( effektivt uppräknad , rekursivt uppräknbar , semi-avgörbar uppsättning [1] ) är en uppsättning konstruktiva objekt (till exempel naturliga tal ), vars alla element kan erhållas med hjälp av någon algoritm . Komplementet av en uppräknad uppsättning kallas corecursively enumerable [2] . Varje uppräknad uppsättning är aritmetisk . En korkursivt uppräknbar mängd kanske inte är uppräknbar, men är alltid aritmetisk. Uppräknade mängder motsvarar nivån på den aritmetiska hierarkin $\Sigma _{1}^{0}$ , och rekursivt uppräknade - till nivån $\Pi _{1}^{0}.$

Varje lösbar uppsättning är uppräknad. En uppräknad uppsättning kan avgöras om och endast om dess komplement också kan räknas upp. Med andra ord, en mängd är avgörbar om och endast om den är både uppräknbar och korkursivt uppräknbar. En delmängd av en uppräknad uppsättning kanske inte är uppräknbar (och kanske inte ens är aritmetisk).

Uppsättningen av alla uppräknbara delmängder är en räknebar uppsättning , och uppsättningen av alla icke-uppräknbara delmängder är oräknelig . $\mathbb {N}$ $\mathbb {N}$

Definitionsvarianter

Olika formaliseringar av begreppet en algoritm motsvarar olika formella definitioner av begreppet en uppräknad mängd, vilka visar sig vara likvärdiga. Sålunda, baserat på konceptet med en rekursiv funktion , kan uppräknade uppsättningar av naturliga tal definieras som bilder av partiellt rekursiva funktioner av en variabel (därför kallas uppräknade uppsättningar av naturliga tal ibland "rekursivt uppräknade uppsättningar"). På liknande sätt kan otaliga uppsättningar av ord i vissa alfabet A introduceras som uppsättningar av utdata från Turing-maskiner med externt alfabet A , eller som uppsättningar av ord i alfabetet A av utdata från normala algoritmer på alfabetet A.

I teorin om algoritmer bevisas påståendet att numerable sets, och endast numerable sets, kan fungera som domäner av algoritmer. Detta tillåter oss att introducera ett annat likvärdigt sätt att definiera begreppet en uppräknad uppsättning. Således kan otaliga uppsättningar av naturliga tal betraktas som intervallen av rekursiva funktioner, uppsättningar av ord - tillämplighetsområdena för Turing-maskiner eller normala algoritmer med motsvarande alfabet.

Exempel

Den tomma uppsättningen är uppräknad.
Varje avgörbar mängd (i synnerhet vilken ändlig mängd som helst ) är uppräknad.
Antalet Turing -maskiner som stannar vid en tom ingång kan också räknas upp (även om det inte går att avgöra , eftersom dess komplement inte kan räknas upp).
Projektionen av en uppräknad uppsättning är uppräknbar.
Unionen och skärningspunkten mellan ett ändligt antal uppräknade mängder kan också räknas upp.
Mängden naturliga tal vars decimalnotation förekommer som en delsträng i decimalnotationen för talet π är uppräknad, och om π är normal , till och med trivialt lösbar (hela uppsättningen naturliga tal).
Uppsättningen av rationella tal mindre än Khaitins konstant Ω är uppräknad men inte avgörbar.
Men mängden rationella tal som är större än Khaitins konstant Ω är icke-uppräknade (även om den är aritmetiskt och korkursivt uppräknbar).
Uppsättningen bevisbara påståenden i första ordningens aritmetik är uppräknad.
Men mängden sanna påståenden i första ordningens aritmetik är varken uppräknbar eller corekursivt uppräknbar (och är inte ens aritmetik, vilket utgör påståendet i Tarskis teorem om sanningens outsäglighet i aritmetiken).

Diophantine

Varje numerabel uppsättning av heltal (eller tuplar av heltal) har en diofantisk representation , det vill säga det är en projektion av uppsättningen av alla lösningar av någon algebraisk diofantisk ekvation.

Detta betyder i synnerhet att varje uppräknad mängd sammanfaller med uppsättningen positiva värden som tas för heltalsparametrar av något polynom med heltalskoefficienter. Detta resultat fastställdes av Yuri Matiyasevich .

Se även

Immunuppsättning

Anteckningar

↑ A. E. Pentus, M. R. Pentus, Matematisk teori om formella språk, Föreläsning 14: Algoritmiska problem // Intuit.ru, 07/09/2007
↑ Barwise, Kenneth John. Uppslagsbok om matematisk logik. Del 3: Rekursionsteori. — M .: Nauka, 1982.

Litteratur

Rogers H. Teori om rekursiva funktioner och effektiv beräkningsbarhet: [transl. från engelska. ] / red. V. A. Uspensky: per. från engelska. V. A. Dushsky, M. I. Kanovich, E. Yu. Nogina. — M .: Mir, 1972.