Zbiór rekurencyjny

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Zbiór rekurencyjnypodzbió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.

Definicje[edytuj | edytuj kod]

  • Zbiór jest zbiorem rekurencyjnym jeśli istnieje funkcja rekurencyjna taka, że dla każdego
wtedy i tylko wtedy, gdy
  • Zbiór jest zbiorem rekurencyjnie przeliczalnym jeśli istnieje funkcja rekurencyjna taka, że .

Przykłady[edytuj | edytuj kod]

Następujące zbiory są rekurencyjne:

Podstawowe własności[edytuj | edytuj kod]

  • 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 jak i są rekurencyjnie przeliczalne.
  • Jeśli zbiory są rekurencyjne, to także zbiory oraz są rekurencyjne.