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