Compreendendo a não deciduidade em matemática e ciência da computação

Não deciduidade é um termo usado no contexto da matemática e da ciência da computação para descrever uma propriedade de certos problemas ou funções que não podem ser resolvidos ou computados por um algoritmo determinístico.

Em outras palavras, não deciduidade se refere ao fato de que alguns problemas ou funções não podem ser resolvidos ou calculado por uma sequência finita de etapas que garantem terminar com um resultado correto. Em vez disso, esses problemas ou funções podem exigir um número infinito de etapas ou podem não ter solução alguma.

Exemplos de problemas não decíduos incluem o problema da parada (que pergunta se um determinado programa irá eventualmente parar ou ser executado indefinidamente), a hipótese de Riemann ( uma conjectura sobre a distribuição de números primos) e a Conjectura de Collatz (uma afirmação sobre o comportamento de uma sequência específica de números). Esses problemas são considerados não caducos porque não podem ser resolvidos por um algoritmo determinístico, e sua resolução é considerada além das capacidades de qualquer programa de computador.

Em contraste, problemas decíduos são aqueles que podem ser resolvidos por um algoritmo determinístico, como adição, multiplicação e classificação de uma lista de números. Os problemas decíduos têm um número finito de soluções possíveis e podem ser resolvidos seguindo um conjunto de regras ou etapas que garantem um resultado correto.