A interseção de infinitos conjuntos recursivos é recursiva?

É a interseção de infinitos conjuntos recursivos $\bigcap_{i}U_{i}$(onde cada conjunto é diferente) recursivo? Recursivamente enumerável? Eu sei que a união não precisa ser recursiva, porque decidir se um elemento está no conjunto$U_i$ é o mesmo que decidir o problema da parada, já que para cada elemento você terá que decidir se a função que calcula se $x \in U_i$para alguns terminarei.$i$

Como você já conhece os sindicatos, pode descobrir isso lembrando as leis de Morgan: o complemento de uma união é o complemento da interseção de complementos. Com isso em mente: deixe$U_i$ser o conjunto de (índices de) máquinas de Turing que não param dentro$i$etapas de execução. Então, o complemento$\mathbb{N} \setminus U_i$ é o conjunto de (índices) daquelas máquinas que param na primeira $i$ passos.

Agora temos:

A propósito, você afirma que "decidir se um elemento está no conjunto $U_i$ é o mesmo que decidir o problema da parada ... "o que não é necessariamente verdadeiro. Por exemplo, se eu definir $U_i = \{42\}$ para todos $i$, então todo o $U_i$são decidíveis. Você precisa prestar atenção ao que seu$U_i$são.

Para cada $i\in \mathbb{N}$, toma $S_i = \mathbb{N}\setminus \{i\}$. Agora você pode criar qualquer conjunto que desejar$X = \bigcap_{i\notin X}S_i$.

Da mesma forma, uma prova mais fácil de que uma união de conjuntos recursivos pode ser qualquer coisa é deixar $T_i=\{i\}$ e agora qualquer conjunto $X$ é $X = \bigcup_{i\in X}T_i$.