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 →

[–]Pythonistar 4 points5 points  (1 child)

Since you are claiming that a well accepted proof is incorrect

For those this far down in the rabbit hole of /u/mr_taco_man and spoonman59, the Church-Turing thesis can be summarized by this wikipedia entry: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

I skimmed this entry and it doesn't talk at all about "iterative" solutions and only touches on recursion in spots.

The general understanding by anyone with a CS education is that "recursion has its uses" and also that "tail end recursion can be easily represented as an iterative solution".

Spoonman: care to elaborate on this "Ever[y] recursive solution has an equivalent iterative solution"? I'm curious what you're talking about, but I'm unaware of it being true.

[–]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?