Um conjunto S de números naturais é chamado se existe uma função recursiva parcial (também conhecida
como função computável) na qual o domínio é exatamente S, significando que a função é definida se e somente se sua entrada é membro de S. Assinale a alternativa que preenche corretamente a lacuna.Escolha uma:
a.
recursivamente tratável
b.
recursivamente enumerável
c.
computavelmente tratável
d.
enumerável
e.
decidível
1 Resposta
Clique aqui para adicionar a sua resposta.
yarawaneska49
B. Recursivamente enumerável.
Explicação:
Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se:
Existe um algoritmo tal que o conjunto de números de entrada para qual o algoritmo pára é exatamente o conjunto de números em S.
Ou, equivalentemente,
Existe um algoritmo que enumera os membros de S. Isso significa que sua saída é simplesmente uma lista de membros de S: s1, s2, s3, ... . Se necessário, esse algoritmo pode rodar para sempre.