Tekst źródłowy strony Twierdzenie Rice’a

'''Twierdzenie Rice’a''' – każda nietrywialna własność [[język rekurencyjnie przeliczalny|języków rekurencyjnie przeliczalnych]] jest nierozstrzygalna.
Twierdzenie zawdzięcza swoją nazwę [[Henry Gordon Rice|Henry’emu Gordonowi Rice’owi]].

== Sformalizowane twierdzenie Rice’a ==
Niech <math>\mathbb A</math> będzie rodziną funkcji n-argumentowych przy <math>n\geqslant 1</math> taką, że:
: <math>\emptyset\neq\mathbb{A}\neq R^{(n)}.</math>

Wówczas zbiór:
: <math>A=\{x\in N:\{x\}^{(n)}\in\mathbb{A}\}</math>

nie jest [[zbiór rekurencyjny|zbiorem rekurencyjnym]].

[[Kategoria:Teoria obliczeń]]
[[Kategoria:Twierdzenia logiki matematycznej|Rice’a]]