função computável

Funções computáveis são os objetos básicos de estudo na teoria da computabilidade. Funções computáveis são uma analogia formalizada da noção intuitiva de algoritmos. Elas são usadas para discutir a computabilidade sem se referir a algum modelo de computação concreto, como a máquina de Turing e a máquina registradora. Entretanto, o conjunto das funções computáveis é equivalente ao conjunto de funções computáveis numa máquina de Turing. No entanto, qualquer definição precisa fazer referência a algum modelo específico de computação, mas todas as referências válidas geram a mesma classe de funções. Modelos particulares de computabilidade que dão origem ao conjunto de funções computáveis são as funções Turing-computáveis e as funções μ-recursivas. Antes de uma definição precisa do termo, matemáticos usavam informalmente o termo "efetivamente computável". Desde então, esse termo vem sendo identificado como função computável. Note que a computabilidade efetiva de tais funções não implica que elas são eficientemente computáveis, isto é, a execução em certa quantidade tolerável de tempo. De fato, pode-se mostrar que para algumas funções computáveis, qualquer algoritmo que a implemente será ineficiente na medida em que seu tempo de execução crescerá exponencialmente (ou mesmo superexponencialmente) de acordo com o tamanho da entrada. Os campos da computação factível e complexidade computacional estudam funções que podem ser computadas eficientemente. De acordo com a tese de Church-Turing, funções computáveis são exatamente as funções que podem ser calculadas usando um dispositivo mecânico de calculo dado uma quantidade ilimitada de espaço de armazenamento e de tempo de execução. De maneira equivalente, a mesma tese define que qualquer função que possui um algoritmo é computável. Observe que um algoritmo, neste sentido, é interpretado como sendo uma sequência de passos que uma pessoa, com tempo ilimitado e caneta e papéis infinitos, pode seguir. Os axiomas de Blum podem ser usados para definir uma teoria de complexidade computacional abstrato, sobre o conjunto de funções computáveis. Na teoria da complexidade computacional, o problema de se determinar a complexidade de uma função computável é conhecido como problema de função.