Conjuntos recursivamente enumeráveis: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 27:
:*Existe uma função computável f tal que:
::<math>f(x) = ▼
\left\{\begin{matrix} ▼
0 &\mbox{if}\ x \in S \\▼
\mbox{indefinido/não pára}\ &\mbox{if}\ x \notin S▼
\end{matrix}\right.▼
</math>▼
:Enumerabilidade
Linha 34 ⟶ 40:
:*O conjunto S é o intervalo de uma função recursiva primitiva ou vazia. Mesmo se S é infinito, repetição de valores podesm ser necessárias nesse caso.
:Diofantina
▲::<math>f(x) =
▲\left\{\begin{matrix}
:*Existe um polinômio p com coeficientes inteiros e variáveis x, a, b, c, d, e, f, g, h, i variando ao longo dos números naturais tais que
▲0 &\mbox{if}\ x \in S \\
::<math>x \in S \Leftrightarrow \exists a,b,c,d,e,f,g,h,i \ ( p(x,a,b,c,d,e,f,g,h,i) = 0).</math>
▲\mbox{indefinido/não pára}\ &\mbox{if}\ x \notin S
▲\end{matrix}\right.
▲</math>
== Exemplos ==
== Propridedades ==
| |||