Zbiór rekurencyjny
Z Wikipedii
Zbiór rekurencyjny – podzbiór (zbioru liczb naturalnych) dla którego można skonstruować algorytm, który w skończonym czasie rozstrzyga czy dana liczba należy do zbioru czy też nie. Inne nazwy tego pojęcia to zbiór obliczalny oraz zbiór rozstrzygalny.
Własność ogólniejsza (słabsza) to bycie zbiorem rekurencyjnie przeliczalnym.
[edytuj] Definicje
- Zbiór jest zbiorem rekurencyjnym jeśli istnieje funkcja rekurencyjna taka, że dla każdego
- f(n) = 0 wtedy i tylko wtedy gdy
- Zbiór jest zbiorem rekurencyjnie przeliczalnym jeśli istnieje funkcja rekurencyjna taka, że .
[edytuj] Przykłady
- Zbiór pusty oraz zbiór są obliczalne.
- Każdy skończony podzbiór jest obliczalny.
- Zbiór liczb pierwszych jest rekurencyjny.
[edytuj] Podstawowe własności
- Każdy zbiór rekurencyjny jest też zbiorem rekurencyjnie przeliczalnym.
- Nieskończony zbiór rekurencyjnie przeliczalny musi zawierać nieskończony podzbiór rekurencyjny.
- Istnieją zbiory rekurencyjnie przeliczalne które nie są rekurencyjne.
- Zbiór jest rekurencyjny wtedy i tylko wtedy gdy zarówno X jak i są rekurencyjnie przeliczalne.
- Jeśli zbiory są rekurencyjne, to także zbiory oraz są rekurencyjne.