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

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

Wówczas zbiór:

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

nie jest zbiorem rekurencyjnym.