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 $\mathbb {A}$ będzie rodziną funkcji n-argumentowych przy $n\geqslant 1$ taką, że:

$\emptyset \neq \mathbb {A} \neq R^{(n)}.$

Wówczas zbiór:

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

nie jest zbiorem rekurencyjnym.