Prosty zestaw

W teorii obliczalności podzbiór liczb naturalnych nazywamy prostym , jeśli jest przeliczalny (ce) i współnieskończony (tj. jego dopełnienie jest nieskończone), ale każdy nieskończony podzbiór jego dopełnienia nie jest ce. Zbiory proste to przykłady zbiorów ce, które nie są obliczalne .

Związek z problemem Posta

Proste zestawy zostały opracowane przez Emila Leona Posta w poszukiwaniu zestawu ce niekompletnego w Turingu. To, czy takie zbiory istnieją, jest znane jako problem Posta . Post musiał udowodnić dwie rzeczy, aby otrzymać swój wynik: że zbiór prosty A nie jest obliczalny i że problem zatrzymania K nie jest redukowany przez Turinga do A . Udało mu się w pierwszej części (co z definicji jest oczywiste), ale w drugiej udało mu się tylko udowodnić redukcję wiele-jeden .

Pomysł Posta został zweryfikowany przez Friedberga i Muchnika w latach pięćdziesiątych XX wieku przy użyciu nowatorskiej techniki zwanej metodą priorytetów . Dają konstrukcję dla zbioru, który jest prosty (a zatem nieobliczalny), ale nie pozwala obliczyć problemu zatrzymania.

Definicje formalne i niektóre własności

$jednolitą$ dalszej części listę ce wszystkich zestawów ce.

Zbiór nazywany ${\ Displaystyle W_ {e} {\ tekst {nieskończony}} \ implikuje W_ {e} \ nie \ subseteq I}$ odpornym $,$ jeśli $nieskończony$ $mi$ dla mamy . Lub równoważnie: nie ma nieskończonego podzbioru, $.$ jest ce
Zbiór nazywany jest prostym $,$ jeśli jest ce, a jego dopełnienie
Zbiór $N}$ jest skutecznie odpornym , jeśli $displaystyle I \ subseteq \ mathbb$ nieskończony, ale istnieje funkcja rekurencyjna taka, że dla każdego indeksu ja $} \displaystyle e}$ $\$ , mamy to ${\ Displaystyle W_ {e} \ subseteq I \ implikuje \ # (W_ {e}) <f (e)}$ .
Zbiór nazywany jest efektywnie prostym, jeśli jest ce, a jego dopełnienie $jest$ Każdy efektywnie prosty zestaw jest prosty i kompletny w sensie Turinga.
Zbiór $N$ hiperimmunologicznym , jeśli $} \displaystyle p_ {I}}$ $nieskończony$ , ale nie jest zdominowany obliczeniowo, gdzie ${\ displaystyle I \ subseteq \$ mathbb to lista członków w kolejności ${\ displaystyle I} .$
Zbiór nazywany jest hiperprostym $,$ jeśli jest prosty, a jego dopełnienie

Notatki

Soare, Robert I. (1987). Rekurencyjnie przeliczalne zbiory i stopnie. Badanie funkcji obliczalnych i zbiorów generowanych obliczeniowo . Perspektywy w logice matematycznej . Berlin: Springer-Verlag . ISBN 3-540-15299-7 . Zbl 0667.03030 .
Odifreddi, Piergiorgio (1988). Klasyczna teoria rekurencji. Teoria funkcji i zbiorów liczb naturalnych . Studia z logiki i podstaw matematyki . Tom. 125. Amsterdam: Północna Holandia. ISBN 0-444-87295-7 . Zbl 0661.03029 .
Nies, André (2009). Obliczalność i losowość . Oxford Logic Guides. Tom. 51. Oksford: Oxford University Press. ISBN 978-0-19-923076-1 . Zbl 1169.03034 .