Zestaw obliczalny - Computable set
W teoria obliczalności , wykorzystując zestaw z liczb naturalnych nazywa obliczalny , rekurencyjne lub rozstrzygalne czy istnieje algorytm , który wykonuje szereg jako wejście, kończy się po skończonym czasie (być może w zależności od danego numeru) i poprawnie decyduje liczby należy do zestawu, czy nie.
Zestaw, który nie jest obliczalny, nazywany jest nieobliczalnym lub nierozstrzygalnym .
Bardziej ogólna klasa zbiorów niż te obliczalne składa się z policzalnie wyliczalnych (ce) zbiorów , zwanych również zbiorami półrozstrzygalnymi . W przypadku tych zbiorów wymagane jest jedynie, aby istniał algorytm, który prawidłowo decyduje, kiedy liczba znajduje się w zbiorze; algorytm może nie dać odpowiedzi (ale nie złej) dla liczb spoza zestawu.
Definicja formalna
Podzbiór z liczb naturalnych nazywa obliczeniowy jeśli istnieje całkowita funkcja obliczalną taki sposób, że w przypadku i jeśli . Innymi słowy, zbiór jest obliczalny wtedy i tylko wtedy, gdy funkcja wskaźnika jest obliczalna .
Przykłady i nie-przykłady
Przykłady:
- Każdy skończony lub cofinite podzbiór liczb naturalnych jest obliczalny. Obejmuje to te specjalne przypadki:
- Zbiór pusty jest obliczalny.
- Cały zbiór liczb naturalnych jest obliczalny.
- Każda liczba naturalna ( zgodnie z definicją w standardowej teorii mnogości ) jest obliczalna; to znaczy zbiór liczb naturalnych mniejszych od danej liczby naturalnej jest obliczalny.
- Podzbiór liczb pierwszych jest obliczalny.
- Rekurencyjne język jest obliczalny podzbiorem języka formalnego .
- Zbiór liczb Gödla dowodów arytmetycznych opisanych w artykule Kurta Gödla „O formalnie nierozstrzygalnych zdaniach Principia Mathematica i pokrewnych systemach I” jest obliczalny; patrz twierdzenia Gödla o niezupełności .
Bez przykładów:
- Zestaw maszyn Turinga, które zatrzymują się, nie jest obliczalny.
- Klasy Izomorfizm dwóch skończonych kompleksów symplicjalnego nie obliczeniowy.
- Zestaw zajętych mistrzów bobrów nie jest obliczalny.
- Dziesiąty problem Hilberta nie daje się obliczyć.
Nieruchomości
Jeśli to zbiór obliczalny wtedy uzupełnieniem od A jest zbiór obliczalny. Jeśli A i B są zestawami obliczalnymi, to A ∩ B , A ∪ B i obraz A × B w funkcji parowania Cantora są zestawami obliczalnymi.
To zbiór obliczalny wtedy i tylko wtedy, gdy A i dopełnienie od A są zarówno CE . Obraz wstępny obliczalnego zbioru w ramach całkowitej funkcji obliczalnej jest zbiorem obliczalnym. Obraz obliczalnego zbioru pod całkowitym obliczalnym bijekcją jest obliczalny. (Ogólnie obraz obliczalnego zestawu w ramach funkcji obliczalnej jest ce, ale prawdopodobnie nie jest obliczalny).
A jest zbiór obliczalny wtedy i tylko wtedy, gdy jest na poziomie od hierarchii arytmetycznej .
A jest zbiorem obliczalnym wtedy i tylko wtedy, gdy jest albo zakresem niezmniejszającej się całkowitej funkcji obliczalnej, albo zbiorem pustym. Obraz obliczalnego zestawu pod nie zmniejszającą się całkowitą funkcją obliczalną jest obliczalny.
Bibliografia
- Cutland, N. Obliczalność . Cambridge University Press, Cambridge-Nowy Jork, 1980. ISBN 0-521-22384-9 ; ISBN 0-521-29465-7 .Linki zewnętrzne
- Rogers, H. Theory of Recursive Functions and Effective Computability , MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1
- Soare, R. Rekurencyjnie policzalne zbiory i stopnie. Perspektywy w logice matematycznej. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7