Zbiór rekurencyjny

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.

DefinicjeEdytuj

  • 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ładyEdytuj

Następujące zbiory są rekurencyjne:

Podstawowe własnościEdytuj

  • 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.