patternMinor
Intuition for Church-Turing thesis for Turing machines
Viewed 0 times
thesisformachineschurchturingintuition
Problem
I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion -- holds for mu-recursion. It reflects exactly the type of algorithms that I can carry out with my own brain.
I cannot see an analogous intuition for understanding why the Turing machine can execute any physically computable algorithm -- i.e. how did Turing "see" that the Turing machine was a good definition to use? Is there a good way to "imagine" the algorithms I perform in terms of the Turing machine, as opposed to general recursion as I am used to?
I cannot see an analogous intuition for understanding why the Turing machine can execute any physically computable algorithm -- i.e. how did Turing "see" that the Turing machine was a good definition to use? Is there a good way to "imagine" the algorithms I perform in terms of the Turing machine, as opposed to general recursion as I am used to?
Solution
Imagine you are performing a computation by hand with a pencil and a stack of paper. [1] There is a limit on how many pieces of information you can keep in working memory at a time (sometimes claimed to be seven plus or minus two). So when you can't keep everything in your head, you write some of it down on a sheet of paper. And when you fill up a sheet, you put it in a pile for later reference and pull out another sheet. But there is a limit on how many sheets of paper you can look at at a time, too; you will have to flip between sheets as you work.
Turing machines are an abstraction of this idea of local computation. A Turing machine can write down as much auxiliary information as it wants, but it can only look at a finite amount of it at a time. A Turing machine head is like your brain's working memory—it can only store so much stuff before it has to write it down somewhere to avoid forgetting it.
The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations. That is, any physically realizable computation can be broken down into a series of steps, each of which operates on $O(1)$ bits of information; there is no primitive operation that requires, say $O(n)$ arguments and cannot be reduced to operations with fewer arguments. [2] Or: anything you can compute in the real world can be computed given an unlimited stack of pencils and paper.
[1] Recall that the word "computer" in Turing's time referred to a human profession!
[2] A primitive operation that accepts an unbounded number of arguments is exactly what the oracle in an oracle Turing machine provides—hence why oracle machines can be more powerful than Turing machines.
Turing machines are an abstraction of this idea of local computation. A Turing machine can write down as much auxiliary information as it wants, but it can only look at a finite amount of it at a time. A Turing machine head is like your brain's working memory—it can only store so much stuff before it has to write it down somewhere to avoid forgetting it.
The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations. That is, any physically realizable computation can be broken down into a series of steps, each of which operates on $O(1)$ bits of information; there is no primitive operation that requires, say $O(n)$ arguments and cannot be reduced to operations with fewer arguments. [2] Or: anything you can compute in the real world can be computed given an unlimited stack of pencils and paper.
[1] Recall that the word "computer" in Turing's time referred to a human profession!
[2] A primitive operation that accepts an unbounded number of arguments is exactly what the oracle in an oracle Turing machine provides—hence why oracle machines can be more powerful than Turing machines.
Context
StackExchange Computer Science Q#128620, answer score: 3
Revisions (0)
No revisions yet.