Definicje

• Zbiór L ⊆ {0, 1}^{∗} jest cz_{}eściowo obliczalny, jeśli L = L(M), dla pewnej maszyny Turinga M.

• Funkcja f : {0, 1}^{∗} ⊇ dom(f) ⟶ {0, 1}^{∗} jest cz_{}eściowo obliczalna, gdy istnieje taka maszyna Turinga M, że L(M) = dom(f) oraz, dla każdego w ∈ dom(f),

q_{1}w ⊢_{M}^{∗} q_{2}v ⟺ f(w) = v

• Funkcja f jest (całkowicie) obliczalna, gdy jest cz_{}eściowo obliczalna i dom(f) = {0, 1}^{∗}.

• Zbiór L ⊆ {0, 1}^{∗} jest obliczalny, gdy istnieje funkcja obli-

czalna χ_{L}, taka że

χ_{L}(w) = 1, gdy w ∈ L
= 0, gdy w ∉ L

Fakt Każdy zbiór obliczalny jest również cz_{}eściowo obliczalny.

Uwaga. Stwierdzenie odwrotne nie jest prawdziwe !

Fakt (twierdzenie Turinga - Posta) Jeśli L ⊆ {0, 1}^{∗} i L̄ = {0, 1}^{∗} \ L s_{}a cz_{}eściowo obliczalne, to s_{}a również obliczalne.

Przykład Zbiór {w : w ∉ L(M_{w})} nie jest cz_{}eściowo obliczalny.

Teza Turinga–Churcha Każda funkcja obliczalna w intuicyjnym sensie jest obliczalna przez pewn_{}a maszyn_{}e Turinga; podobnie dla j_{}ezyków.