Rekursivt enumerable sæt

I beregnelighed, der traditionelt kaldes rekursion teori, et sæt S af naturlige tal kaldes rekursivt enumerable, computably enumerable, semidecidable, bevises eller Turing-genkendelige, hvis:

  • Der er en algoritme, således at sættet af input, for hvilke der algoritmen standser præcis S.

Eller, ækvivalent,

  • Der er en algoritme, der opregner de medlemmer af S. Det betyder, at dens output er simpelthen en liste over medlemmerne af S: S1, S2, S3, .... Hvis det er nødvendigt, denne algoritme kan køre for evigt.

Den første betingelse foreslår hvorfor udtrykket semidecidable bruges nogle gange; det andet foreslår derfor computably enumerable anvendes. Forkortelserne R.E. og C.E. anvendes ofte, selv på tryk, i stedet for den fulde sætning.

I beregningsmæssige kompleksitetsteori, kompleksiteten klassen indeholder alle rekursivt enumerable sæt er RE. I rekursion teori gitter af R.E. sæt under inklusion betegnes.

Formel definition

Et sæt S naturlige tal kaldes rekursivt enumerable hvis der er en delvis rekursiv funktion, hvis domæne er nøjagtigt S, hvilket betyder, at funktionen er defineret, hvis og kun hvis dens input er medlem af S.

Tilsvarende formuleringer

Følgende er alle ækvivalente egenskaber af et sæt S naturlige tal:

  • Der er et polynomium fra heltal til heltal sådan, at den indstillede S indeholder nøjagtig de ikke-negative tal i sit sortiment.

Ækvivalensen af ​​semidecidability og enumerability kan opnås ved teknikken med sammenkædning.

De Diophantine beskrivelser af et rekursivt enumerable sæt, mens ikke så ligetil eller intuitive som de første definitioner, blev fundet af Yuri Matiyasevich som en del af den negative løsning på Hilbert 's tiende Problem. Diophantine sæt forud rekursion teori og er derfor historisk set den første måde at beskrive disse sæt. Antallet af bundne variabler i ovenstående definition af Diophantine sæt er den bedste hidtil kendte; Det kan være, at et lavere antal kan anvendes til at definere alle Diophantine sæt.

Eksempler

  • Hver rekursiv sæt er rekursivt enumerable, men det er ikke sandt, at hver rekursivt enumerable sæt er rekursiv. For rekursive sæt, skal algoritmen også sige, hvis et input ikke er i sættet - dette er ikke påkrævet for rekursivt enumerable sæt.
  • Et rekursivt enumerable sprog er en rekursivt enumerable delmængde af et formelt sprog.
  • Mængden af ​​alle beviselige sætninger i en effektivt præsenteret aksiomatisk system er et rekursivt enumerable sæt.
  • Matiyasevich sætning hedder det, at hver rekursivt enumerable sæt er en Diophantine sæt.
  • De enkle sæt er rekursivt enumerable men ikke rekursiv.
  • De kreative sæt er rekursivt enumerable men ikke rekursiv.
  • Enhver produktiv sæt er ikke rekursivt enumerable.
  • Givet en Gödel nummerering af beregnelige funktioner, sættet er rekursivt enumerable. Dette sæt koder standsning problem, da det beskriver inputparametre, som hver Turing-maskine stopper.
  • Givet en Gödel nummerering af beregnelige funktioner, sættet er rekursivt enumerable. Dette sæt koder for problemet med at sætte en funktionsværdi.
  • Givet en delvis funktion f fra naturlige tal ind i de naturlige tal, f er en delvis rekursiv funktion, hvis og kun hvis grafen for f, det vil sige mængden af ​​alle par, således at f er defineret, er rekursivt enumerable.

Egenskaber

Hvis A og B er rekursivt enumerable sæt derefter A ∩ B, A ∪ B og A × B er rekursivt enumerable sæt. Den preimage af et rekursivt enumerable sæt under en delvis rekursiv funktion er et rekursivt enumerable sæt.

Et sæt er rekursivt enumerable hvis og kun hvis det er på niveau med aritmetiske hierarki.

Et sæt kaldes co-rekursivt enumerable eller co-re hvis dens komplement er rekursivt enumerable. Ækvivalent, et sæt er co-R. E. hvis og kun hvis det er på det aritmetiske hierarki.

Et sæt A er rekursiv hvis og kun hvis både A og komplementet af A er rekursivt enumerable. Et sæt er rekursiv, hvis og kun hvis den enten er rækkevidden af ​​et stigende total rekursiv funktion eller begrænset.

Nogle par af rekursivt enumerable sæt er effektivt adskilles og nogle er ikke.

Bemærkninger

Ifølge Kirken-Turing tese, enhver effektivt beregnelig funktion er beregnelig med en Turing-maskine, og dermed et sæt S er rekursivt enumerable hvis og kun hvis der er nogle algoritme, der giver en opregning af S. Dette kan ikke tages som en formel definition , men fordi kirken-Turing tese er en uformel formodninger snarere end en formel aksiom.

Definitionen af ​​et rekursivt enumerable sættet som domænet af en delvis funktion, snarere end intervallet i alt rekursiv funktion, er almindeligt i moderne tekster. Dette valg er motiveret af, at der i generaliserede rekursionsudtryk teorier, såsom α-rekursion teori er definitionen svarer til domæner vist sig at være mere naturligt. Andre tekster bruger definitionen i form af tællinger, hvilket svarer til rekursivt enumerable sæt.

  0   0
Forrige artikel Flete House
Næste artikel Château d'Angers

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha