Opregnede sæt
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. maj 2021; checks kræver 7 redigeringer .En enumerable mængde ( effektivt enumerable , rekursively enumerable , semi-decidable set [1] ) er et sæt af konstruktive objekter (for eksempel naturlige tal ), som alle elementer kan opnås ved hjælp af en eller anden algoritme . Komplementet til en optællingsmængde kaldes corecursively enumerable [2] . Hvert talrige sæt er aritmetiske . Et corecursively tællerbart sæt kan ikke tælles, men er altid aritmetisk. Opregnede sæt svarer til niveauet hierarki
Hvert løseligt sæt er talværdigt. Et opregnbart sæt kan bestemmes, hvis og kun hvis dets komplement også kan optælles. Med andre ord kan et sæt afgøres, hvis og kun hvis det både kan optælles og corekursivt opregnes. En delmængde af et tælleligt sæt kan ikke tælles (og er muligvis ikke engang aritmetisk).
Sættet af alle tællelige delmængder er et tælleligt sæt , og sættet af alle ikke-tællelige undersæt er utælleligt .
Varianter af definition
Forskellige formaliseringer af begrebet en algoritme svarer til forskellige formelle definitioner af begrebet en talløse mængde, som viser sig at være ækvivalente. Baseret på begrebet en rekursiv funktion kan numerable sæt af naturlige tal således defineres som billeder af delvist rekursive funktioner af en variabel (derfor kaldes numerable sæt af naturlige tal undertiden "rekursivt numerable mængder"). På samme måde kan talløse sæt af ord i nogle alfabet A introduceres som sæt af output fra Turing-maskiner med eksternt alfabet A , eller som sæt af ord i alfabet A af output af normale algoritmer på alfabet A.
I teorien om algoritmer er påstanden bevist, at numerable sæt, og kun numerable sæt, kan tjene som domæner af algoritmer. Dette giver os mulighed for at introducere en anden tilsvarende måde at definere begrebet et talløse sæt på. Således kan talløse sæt af naturlige tal betragtes som rækkerne af rekursive funktioner, sæt af ord - anvendelsesområderne for Turing-maskiner eller normale algoritmer med de tilsvarende alfabeter.
Eksempler
- Det tomme sæt er talværdigt.
- Ethvert afgørbart sæt (især ethvert endeligt sæt ) er talværdigt.
- Antallet af Turing-maskiner, der stopper ved en tom indgang, er også talbar (selv om den ikke kan afgøres , da dens komplement ikke kan tælles).
- Projektionen af et tælleligt sæt kan tælles.
- Foreningen og skæringen af et endeligt antal tællelige mængder er også tællelige.
- Sættet af naturlige tal, hvis decimalnotation forekommer som en delstreng i decimalnotationen af tallet π , kan tælles, og hvis π er normal , endda trivielt løseligt (hele sættet af naturlige tal).
- Sættet af rationelle tal mindre end Khaitins konstant Ω er talbart, men kan ikke bestemmes.
- Men mængden af rationelle tal, der er større end Khaitins konstant Ω, kan ikke tælles (selvom den kan tælles aritmetisk og korekursivt).
- Sættet af bevisbare udsagn i førsteordens aritmetik er talrige.
- Men sættet af sande udsagn i første-ordens aritmetik er hverken tælleligt eller corecursively tælleligt (og er ikke engang aritmetik, hvilket udgør påstanden af Tarskis sætning om uudtrykkeligheden af sandhed i aritmetik).
Diophantine
Ethvert talløse sæt af heltal (eller tupler af heltal) har en diophantinsk repræsentation , det vil sige, det er en projektion af mængden af alle løsninger af en eller anden algebraisk diophantinsk ligning.
Dette betyder især, at ethvert tælleligt sæt falder sammen med sættet af positive værdier, der tages for heltalsparametre af et eller andet polynomium med heltalskoefficienter. Dette resultat blev etableret af Yuri Matiyasevich .
Se også
Noter
- ↑ A. E. Pentus, M. R. Pentus, Matematisk teori om formelle sprog, Foredrag 14: Algoritmiske problemer // Intuit.ru, 07/09/2007
- ↑ Barwise, Kenneth John. Opslagsbog om matematisk logik. Del 3: rekursionsteori. — M .: Nauka, 1982.