Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be equivalent.

What is the reason behind this? Has recursion theory simply gone out of fashion or is there a fundamental/mathematical reason explaining this?

  • 2
    $\begingroup$ Gödel himself was much in favor of Turing's analysis of computability and his notion of machines. He explicitly wrote somewhere, but I cannot find it right now, that he preferred Turing's ideas to general recursive functions (which Gödel invented). If anyone knows of the comments I have in mind, please provide a reference. $\endgroup$ Commented Jul 6, 2020 at 8:43
  • $\begingroup$ Soare's paper covers a lot of history, and gives links to a lot more. $\endgroup$ Commented Jul 10, 2020 at 13:39

1 Answer 1


With Turing machines you can talk about computer concepts such as running time and space usage. This is harder with $\mu$-recursive functions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.