Twierdzenie Rice’a

Twierdzenie Rice’a – każda nietrywialna własność języków rekurencyjnie przeliczalnych jest nierozstrzygalna. Twierdzenie zawdzięcza swoją nazwę Henry’emu Gordonowi Rice’owi.

Sformalizowane twierdzenie Rice’a

Niech $𝔸$ będzie rodziną funkcji n-argumentowych przy $n⩾1$ taką, że:

$\mathrm{\varnothing }\ne 𝔸\ne R^{(n)}.$

Wówczas zbiór:

$A=\{x\in N:\{x{\}}^{(n)}\in 𝔸\}$

nie jest zbiorem rekurencyjnym.