Twierdzenie Rice’a
(Przekierowano z 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 edytuj
Niech będzie rodziną funkcji n-argumentowych przy taką, że:
Wówczas zbiór:
nie jest zbiorem rekurencyjnym.