Problema de decisão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 19:
Formalmente, tem-se ainda que um problema de decisão é um subconjunto ''A'' dos números naturais. Usando os números de [[Godel]], é possível estudar outros conjuntos, como as linguagens formais. O "problema" informal é decidir quando um dado número está em um determinado conjunto.
Um problema de decisão é chamado de '''decidível''' ou '''efetivamente solúvel''' se ''A'' é um [[conjunto recursivo]]. Um problema é chamado '''parcialmente decidível''', '''semi-decidível''', '''solúvel''' ou '''provável''' se ''A'' é um [[conjunto recursivamente enumerável]]. Do contrário, o problema é chamado de '''indecidível'''.
| |||