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$ – Andrej Bauer Jul 6 at 8:43
  • $\begingroup$ Soare's paper covers a lot of history, and gives links to a lot more. $\endgroup$ – Jim Hefferon Jul 10 at 13:39

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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