Twierdzenie Rice'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

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

Wówczas zbiór:

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

nie jest zbiorem rekurencyjnym