Conjuntos recursivamente enumeráveis: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado
KLBot2 (discussão | contribs)
m Bot: A migrar 11 interwikis, agora providenciados por Wikidata em d:Q676835
m Ajuste de link.
Linha 42:
A equivalência da semidecidibilidade e enumerabilidade pode ser obtida através da técnica de [[Dovetailing (computer science)|dovetailing]].
 
As caracterizações Diofantina de um conjunto recursivamente enumerável, embora não tão simples ou intuitivo como as primeiras definições, foram encontradas por [[Yuri Matiyasevich]] como parte da solução negativa do [[Hilbert's tenth problem|décimo problema de HibertHilbert]].
Conjuntos diofantinos antecedem a teoria da recursão e são, historicamente, a primeira maneira de descrever esses conjuntos (embora essa equivalência apenas tenha sido demonstrada mais de três décadas depois da introdução dos conjuntos recursivamente enumeráveis). O número de variáveis associadas na definição acima de [[Teorema de Matiyasevich|conjunto Diofantino]] é a mais conhecida até agora; pode ser que um número menor possa ser usado para definir todos os conjuntos diofantinos.
== Exemplos ==
 
* Todo conjunto recursivo é recursivamente enumerável, mas não é verdade que todo conjunto recursivamente enumerável é recursivo.
* Uma [[Linguagem recursivamente enumerável|linguagem recursivamente enumeravel]] é um subconjunto recursivamente enumerável de uma linguagem formal.