6.3 FUNCIONES COMPUTABLES

Son una formalización de la noción intuitiva de algoritmo y según la Tesis de Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas con un oráculo por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable