Twierdzenie o podstawie (obliczalność)

W teorii obliczalności istnieje wiele twierdzeń bazowych . Z twierdzeń tych wynika, że ​​określone rodzaje zbiorów zawsze muszą mieć takie elementy, które pod względem stopnia Turinga nie są zbyt skomplikowane. Jedna rodzina twierdzeń $;$ skutecznie zamkniętych zbiorów (to znaczy niepustych zbiorów w hierarchii arytmetycznej ) te twierdzenia są badane jako część klasycznej teorii obliczalności. Inna rodzina twierdzeń bazowych dotyczy niepustych $)$ analitycznych jasnej powierzchni (to znaczy w analitycznej te twierdzenia są badane jako część teorii hiperarytmetycznej .

Skutecznie domknięte zbiory

Efektywnie domknięte zbiory są przedmiotem badań w klasycznej teorii obliczalności. Efektywnie zamknięty zbiór to zbiór wszystkich ścieżek przechodzących przez jakieś obliczalne poddrzewo drzewa binarnego ${\ Displaystyle 2 ^ {<\ omega}}$ . Zbiory te są domknięte w sensie topologicznym jako podzbiory przestrzeni $Cantora$ , a dopełnieniem efektywnego efektywny zbiór otwarty w sensie efektywnych przestrzeni polskich . Kleene udowodnił w 1952 r., że istnieje niepusty, efektywnie domknięty zbiór bez obliczalnego punktu (Cooper 1999, s. 134). Twierdzenia o podstawach pokazują, że muszą istnieć punkty, które nie są „zbyt dalekie” od bycia obliczalnymi w nieformalnym sensie.

Klasa jest podstawą efektywnie zamkniętych zbiorów, jeśli każdy niepusty efektywnie domknięty zbiór zawiera członka $}} \ subseteq 2 ^ {\ omega}}$${\ mathcal {$ (Cooper 2003, s. 329). Twierdzenia o podstawach pokazują, że poszczególne klasy są w tym sensie bazami. Twierdzenia te obejmują (Cooper 1999, s. 134):

• niskiej podstawie : każdy niepusty $ma$ element niskiego stopnia
• Twierdzenie o bazie wolnej od hiperimmunizacji : każdy niepusty $, który$ wolny od hiperimmunizacji.
• Twierdzenie o podstawie : każdy niepusty $rekurencyjnie$ ma element, który ma (re) stopień .

$z$ zestaw jest $Turinga$ , jeśli skok _ _ _ ${\ Displaystyle X}$ ma stopień wolny od hiperimmunizacji , jeśli każda suma obliczalna funkcja $f \ okrężnica \ mathbb {N} \ do \ mathbb {N}}$$Displaystyle$ zdominowana przez X {\ displaystyle X} całkowita obliczalna funkcja $n$ co oznacza ${\ Displaystyle f (n) \ równoważnik g (n)}$ dla wszystkich $\ displaystyle n}$ ).

Żadne dwa z powyższych trzech twierdzeń nie mogą być połączone dla zbioru spójnych uzupełnień PA (lub tylko EFA ; stopnie Turinga są takie same). Jedynym stopniem re Turinga, który oblicza spójną realizację PA, jest 0'. Jednak twierdzenie o niskiej bazie i twierdzenie o bazie wolnej od hiperimmunizacji można połączyć z unikaniem stożka, tj. dla każdego nieobliczalnego X możemy wybrać członka (jak w twierdzeniu), który nie oblicza X . Twierdzenia relatywizują również powyżej dowolnej rzeczywistości.

Zestawy analityczne Lightface

Istnieją również podstawowe twierdzenia $zbiorów$ Te podstawowe twierdzenia są badane jako część teorii hiperarytmetycznej . Jednym z twierdzeń jest twierdzenie o bazie Gandy'ego, które jest analogiczne do twierdzenia o niskiej bazie. Twierdzenie o podstawie Gandy'ego pokazuje, że każdy niepusty $zbiór$ element, który jest hiperarytmetycznie niski, to znaczy jego hiperskok ma ten sam ten sam hiperstopień (a dla nawet ten sam stopień Turinga), co zestaw Kleene'a. ${\ displaystyle {\ mathcal {O}}}$ .

•   Cooper, SB (1999). „Teoria stopni lokalnych”, w Handbook of Computability Theory , ER Griffor (red.), Elsevier, s. 121–153. ISBN 978-0-444-89882-1
•   — (2003), Teoria obliczalności , Chapman-Hall. ISBN 1-584-88237-9

Linki zewnętrzne

• Simpson, S. „ Przegląd twierdzeń bazowych ”, slajdy z Computability Theory and Foundations of Mathematics , Tokyo Institute of Technology, 18–20 lutego 2013 r.