Twierdzenie Rice’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Twierdzenie Rice'a)
Skocz do: nawigacja, szukaj

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