Czy zbiory są rekurencyjne

[mkzor56]

Mam problem z zadaniem

Zweryfikuj, czy poniższe zbiory są rekurencyjne:

1 \(\displaystyle{ A = \left\{ x \in \NN : \left( \exists y \in \NN\right) x \in W _{y} \right\}}\)
2. \(\displaystyle{ B = \left\{ x \in \NN : \left( \exists y \in \NN\right) y \in W _{x} \right\}}\)

Sformułuj twierdzenia, na których opiera się Twoje rozwiązanie

[ldurniat]

Przypomnij jak są określone zbiory \(\displaystyle{ W_x}\) oraz \(\displaystyle{ W_y.}\)

[mkzor56]

\(\displaystyle{ W _{x}}\) - dziedzina funkcji o numerze x

[ldurniat]

Sądzę, że \(\displaystyle{ A=\mathbb{N}}\) oraz o rekurencyjności zbioru \(\displaystyle{ B}\) przesądza tw. Problem Stopu jest nierozstrzygalny, dostępne pod adresem

Kod: Zaznacz cały

http://logic.amu.edu.pl/images/2/29/Klunder.pdf

str. 34