Según la Tesis de Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidas por funciones recursivas, cálculo lambda, o algoritmos de Markov .