Problemas algorítmicos en las matemáticas II

2. Las máquinas de Turing

Por lo tanto, en lugar de considerar algoritmos para determinar si una relación entre números naturales tiene lugar, podernos considerar algoritmos para calcular efectivamente los valores de una función aritmética, Es, pues, necesario precisar el concepto de función efectivamente calculable. Es esto lo que efectúa TURING: da un concepto preciso de máquina y define una función aritmética  f como efectivamente calculable si existe una tal máquina  para calcular el valor de f para cada argumentoLas máquinas de Turing / Funciones recursivas