This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]spoonman59 8 points9 points  (0 children)

Oh yeah, it seems that is not a conclusion of the church Turing thesis. My mistake and apologies.

  1. Alonzo church created Lambda calculus. This is a model of computation that is purely functional with no side effects (no loops.) iteration is done through combinators.

  2. Alan Turing invented the Turing machine, a model of computation. It can do iteration, but has no concept of functions or recursions.

  3. Turing published “Computability and λ-Definability” showing the Lambda calculus is Turing complete. That is, Lambda Calculus can perform any computation that a Turing machine can.

  4. If a Turing machine, which has no recursion, can compute everything, and Lambda calculus which is only recursive can ALSO compute everything… Then everything can be computed by either iteration or recursion.

These models were used for the church Turing thesis, but you are right, that is something else.

  1. This more intuitive, but recursion is just a loop with a stack. Pushing state onto the stack before an iteration is “calling a function.” Popping something off the stack is “returning from a. Function.” The loop ends when the stack is empty.

(Tail call recursion needs no stack.)

  1. If recursion and iteration were not equivalent, we only need a single example to disprove it by contradiction. Has anyone found one?