obliczalny zbiór

obliczalny zbiór,

mat. zbiór liczb naturalnych (lub zbiór tekstów), dla którego istnieje algorytm rozstrzygający, czy dana liczba (lub tekst) należy do zbioru;

pojęcie z.o. można sprowadzić do pojęcia funkcji obliczalnej: zbiór X jest obliczalny, jeśli jego funkcja charakterystyczna (która przyjmuje wartość 1, jeśli argument należy do zbioru X, a 0 — w przeciwnym wypadku) jest obliczalna.