Computável

Computável é um termo da teoria da computabilidade que descreve aquilo que pode ser obtido por um algoritmo finito. Em termos formais, uma função f: N^k -> N é computável se existe uma máquina de Turing que, dada a entrada x, produz f(x) em tempo finito. Modelos de computação equivalentes incluem a máquina de Turing, o cálculo lambda e as funções recursivas; a Tese de Church–Turing afirma que esses modelos definem a mesma classe de funções efetivamente computáveis.

Um problema de decisão é computável (ou decidível) se existe um algoritmo que responde sim ou não para todas as entradas. Nem todos os problemas são computáveis: o problema da parada, por exemplo, não possui um algoritmo geral que funcione para todas as entradas. Existe também a noção de decidibilidade parcial ou reconhecimento; conjuntos recursivamente enumeráveis são aqueles para os quais existe uma máquina que imprime os elementos em uma lista infinita, sendo chamados de semi-decidíveis.

Quanto aos números reais, um número real é computável se existe um algoritmo que, para cada n, fornece uma aproximação com precisão de n dígitos. Não obstante, a maioria dos reais não é computável, ou seja, não há algoritmo que produza suas dígitos com eficiência.

História e impacto: os conceitos foram formalizados na década de 1930 por Alonzo Church e Alan Turing, com contribuições de outros como Stephen Kleene. A teoria da computabilidade fundamenta parte da ciência da computação teórica, verificação formal, criptografia e teoria da complexidade, delineando limites fundamentais do que pode ser calculado.