<p>75 years ago there were no computers around. So one had to explain very carefully the <em>mathematical</em> idea of a computer.</p>

<p>Today everybody knows what a computer is, and is probably carrying one around most of the time. This can be used very successfully in teaching because you can skip the rather outdated idea of a machine with a tape. I mean, who uses a tape? (I know, I know, you feel insulted and Turing was a great man and all that, and I agree with you).</p>

<p>You just walk into the class and ask: so it there anything your iPhones can't compute? This immediately gets you into questions about bounded resources. Then you say: well suppose your machine actually had unlimited memory, is there anything it couldn't compute? And you idealize a bit more and limit attention to number-theoretic functions (because you are not interested in Facebook at the moment). You'll have to explain a bit how computers work (as mentioned in the comments, it's good if the students know a programming language because you can use that instead of describing hardware), but after that you can use all the classical arguments of computability theory to derive results. It doesn't matter that your students' mental picture of a machine is iPhone. In fact, it matters: it makes it <em>easier</em> and <em>more relevant</em> for them to know that their iPhone can't do certain things.</p>

CC BY-SA 3.0
2011-05-10T05:35:47.893Z
We still need mathematical models for impossibility results (like lowerbounds) and also for comparing algorithms.
Kaveh
CC BY-SA 3.0
2011-05-10T16:01:09.593Z
@Kaveh: yes of course, and I suggested we should use programming language for that purpose.
Andrej Bauer
CC BY-SA 3.0
2011-05-11T01:23:58.790Z
Hmmm, my problem is complexity theory, I haven't seen anyone use programing languages to teach complexity, I had the feeling that programming languages are not fine grained enough for complexity purposes. Do you think it is possible? Do you know anyone who has done it? (maybe I should post this as a new question since this one was about computability)
Kaveh
CC BY-SA 3.0
2011-05-11T04:31:28.770Z
@Kaveh: I recommend Bob Harper's blog, in particular this post: http://existentialtype.wordpress.com/2011/03/16/languages-and-machines/
Andrej Bauer
CC BY-SA 2.5
2011-02-20T20:29:28.567Z
I quite like this argument, because it goes from the concrete (the iPhone) to the abstract.
Suresh Venkat
CC BY-SA 2.5
2011-02-20T20:31:17.187Z
Here's an interesting puzzle: what are the s-m-n and u-t-m theorems in Haskell?
Andrej Bauer
CC BY-SA 2.5
2011-02-20T20:46:50.377Z
"75 years ago there were no computers around."  This is simply false.  75 years ago there were LOTS of computers around.  They were humans, mostly women; they had advanced mathematics degrees, a few rudimentary mechanical computation tools (like adding machines and slide rules), and lots and lots of paper.  These computers were the backbone of both the Manhattan Project and Bletchley Park during WWII (the Bomb and the Bombe notwithstanding).  This is the computing environment that Turing was modeling: humans with pencil and paper.
Jeffε
CC BY-SA 2.5
2011-02-20T20:57:48.583Z
@Andrej: Good point! Here's the deal for those interested: [utm theorem](http://en.wikipedia.org/wiki/Utm_theorem) and [smn theorem](http://en.wikipedia.org/wiki/Smn_theorem).
Sadeq Dousti
CC BY-SA 2.5
2011-02-20T21:06:29.630Z
@JɛﬀE: So, should we count human beings as alive "Turing machines" or alive "families of circuits"? (Seriously!)
Sadeq Dousti
CC BY-SA 2.5
2011-02-20T21:30:15.910Z
@Jeffe: Come on, you know what I meant.
Andrej Bauer
CC BY-SA 2.5
2011-02-21T03:23:22.923Z
@SadeqDousti: well if they had families working there ;)
Suresh Venkat
CC BY-SA 2.5
2011-02-21T05:15:34.283Z
@Suresh: LOL :) But seriously, I always think whether the human brain acts differently on various input sizes or not. For instance, if you are to prove the "Pythagorean theorem" or the "P vs NP" theorem, the brain acts totally different. IMHO, this is the reason why it is so difficult to simulate the brain with computers...
Sadeq Dousti
CC BY-SA 2.5
2011-02-21T15:44:25.697Z
@Andrej: Yes, I know exactly what you meant, and that's why I objected!  Computer ≠ electronic computer.
Jeffε
CC BY-SA 2.5
2011-02-22T14:06:16.187Z
@JeffE: we can test your hypothesis. Go to your colleagues and ask them to draw a picture of "a computer wearing a short skirt". Please report how many drew a human being.
Andrej Bauer
CC BY-SA 2.5
2011-02-20T20:28:18.280Z
2011-02-20T20:28:18.280Z
Andrej Bauer
<p>"A function is computable if there is an 'effective procedure' for going from input to output."  When introducing this topic, I have in the past pointed out how they (the students) have an effective procedure for solving quadratic equations, but do not have one for solving equations of degree 5 or more.  This can segue into a discussion of how one might formalize 'effective procedure', but that discussion is something you want to have happen, so I think that's a feature, rather than a bug.</p>

CC BY-SA 2.5
2011-02-20T22:00:04.457Z
Nitpicking: [Abel–Ruffini theorem](http://en.wikipedia.org/wiki/Abel–Ruffini_theorem) states that there is no general **algebraic** solution—that is, solution in radicals— to polynomial equations of degree five or higher. However, there are methods, such as the [Bring radical](http://en.wikipedia.org/wiki/Bring_radical), to obtain closed-form solutions of quintic equations.
Sadeq Dousti
CC BY-SA 2.5
2011-02-21T01:40:44.230Z
Your nitpicking is actually right-on.  When discussing computability, you want to talk about things like "allowed operations", and solutions to polynomials are one of those things which gets more complex the closer you look at it.  But for an introduction, I think that the words "effective procedure" and a mention of the quadratic formula make a great starting point.  They aren't entirely correct, but the intuition is pretty right-on, IMO.
Peter Boothe
CC BY-SA 2.5
2011-02-20T16:43:11.090Z
2011-02-20T16:43:11.090Z
Peter Boothe
<p>Perhaps the point is that all of these models aimed to capture what the notion of computability is. The fact that all of them are equivalent, means that the notion they are trying to capture is robust. So although this does not escape your dilemma, this robustness gives credence to the notion that "a function is computable if there is a Turing machine that computes it".</p>

CC BY-SA 2.5
2011-02-20T16:54:08.840Z
2011-02-20T16:54:08.840Z
Dave Clarke
<p>I start out asking "is there any question that no computer could ever answer convincingly?" and lead the discussion toward philosophical questions such as "if a tree falls in the forest does it make a sound?" or "is there an afterlife?"  We quickly get a consensus that human language can express yes/no questions involving paradoxes or concepts that cannot be expressed mathematically, and so, yes, there are non-computable questions.</p>

<p>Then I ask rhetorically whether there are non-computable questions about concepts that <em>can</em> be represented in a computer, e.g. integers and graphs.  I say that yes, one example is the famous halting problem, which is about examining a description of a program and saying whether it has any infinite loops.  Intuitively, it turns out that infinite loops are like black holes, and any program that observes an infinite loop could get trapped in an infinite loop itself.  So any procedure that answers that problem may run forever, so by the definition of "algorithm" no algorithm can answer the halting problem.</p>

<p>Then I dive back into proofs on Turing machines.</p>

CC BY-SA 2.5
2011-02-21T22:58:49.850Z
2011-02-21T22:58:49.850Z
Kevin Wortman
<p>Well, a function is computable if it accepts inputs that are formed or generated by a specific pattern. A specific pattern means all inputs should have a relation, a particular input can be generated by it previous or next input. If the inputs do not have this type of sequence, then there is no possibility to develop a model or function that can accept. One thing more i want to say that is that there is a basic difference between a machine and a human being. A machine could not be formed for non-sequential inputs but humans are. Also this is big interruption of making actual human behaving robots.       </p>

CC BY-SA 3.0
2012-12-26T00:47:27.380Z
The question is about teaching computability. It would be good if you restrict your answer to material answering that question. Keep in mind that the OP is teaching undergraduates, so personal opinions (such as your last three statements) may not be in scope.
Vijay D
CC BY-SA 3.0
2011-05-10T04:30:23.610Z
2012-12-26T00:44:14.100Z
2012-12-26T00:44:14.100Z
vineet kumar
<p>I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. The students immediately asked: "what does computability mean?" and I can't answer unless I teach them Turing machines, and then answer "a function is computable if a Turing machine computes it."</p>

<p>So,</p>

<blockquote>
  <p>Is there a description of computability which does not require resorting to Turing machines, λ-calculus, or similar models of computation? Even an intuitive description will suffice.</p>
</blockquote>

CC BY-SA 2.5
2011-02-20T15:05:31.393Z
"Every function a computer can compute" ?  Usually, I resort to programming languages, as the students are likely to know one.  I've  alsotried going for "any recipe to compute a function" as an intuitive definition of algorithm.
Michaël Cadilhac
CC BY-SA 2.5
2011-02-20T15:45:08.390Z
A problem is computable if it can be solved by a finite set of rules that govern the evolution of discrete dynamical system in finite number of steps.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-20T16:00:34.670Z
Also, you can use Hilbert's tenth problem to explain to the students why it is unsolvable and that the proof of unsolvability required, among other things, formalizing the notion of computability in mathematics.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-20T21:03:22.193Z
Another question: The Church-Turing Thesis states that a function can be computed by some Turing machine if and only if it can be computed by some machine of any other “reasonable and general” model of computation [Goldreich, 2008]. So, is a model-independent notion of computability conceivable?
Sadeq Dousti
<soft-question><computability><turing-machines><teaching>
Problem teaching computability
mcKlane
# Problem teaching computability

(Asked by: username_0 on 2011-02-20)

I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. The students immediately asked: "what does computability mean?" and I can't answer unless I teach them Turing machines, and then answer "a function is computable if a Turing machine computes it."

So,

> Is there a description of computability which does not require resorting to Turing machines, λ-calculus, or similar models of computation? Even an intuitive description will suffice.

**Tags:** soft-question, computability, turing-machines, teaching

> **Comments:**
> **username_1**: "Every function a computer can compute" ?  Usually, I resort to programming languages, as the students are likely to know one.  I've  alsotried going for "any recipe to compute a function" as an intuitive definition of algorithm.  
> **username_2**: A problem is computable if it can be solved by a finite set of rules that govern the evolution of discrete dynamical system in finite number of steps.  
> **username_2**: Also, you can use Hilbert's tenth problem to explain to the students why it is unsolvable and that the proof of unsolvability required, among other things, formalizing the notion of computability in mathematics.  
> **username_3**: Another question: The Church-Turing Thesis states that a function can be computed by some Turing machine if and only if it can be computed by some machine of any other “reasonable and general” model of computation [Goldreich, 2008]. So, is a model-independent notion of computability conceivable?  

---

## 5 answers

### Answer by username_4 on 2011-02-20. Score: 37

75 years ago there were no computers around. So one had to explain very carefully the *mathematical* idea of a computer.

Today everybody knows what a computer is, and is probably carrying one around most of the time. This can be used very successfully in teaching because you can skip the rather outdated idea of a machine with a tape. I mean, who uses a tape? (I know, I know, you feel insulted and Turing was a great man and all that, and I agree with you).

You just walk into the class and ask: so it there anything your iPhones can't compute? This immediately gets you into questions about bounded resources. Then you say: well suppose your machine actually had unlimited memory, is there anything it couldn't compute? And you idealize a bit more and limit attention to number-theoretic functions (because you are not interested in Facebook at the moment). You'll have to explain a bit how computers work (as mentioned in the comments, it's good if the students know a programming language because you can use that instead of describing hardware), but after that you can use all the classical arguments of computability theory to derive results. It doesn't matter that your students' mental picture of a machine is iPhone. In fact, it matters: it makes it *easier* and *more relevant* for them to know that their iPhone can't do certain things.

> **Comments:**
> **username_6**: I quite like this argument, because it goes from the concrete (the iPhone) to the abstract.  
> **username_4**: Here's an interesting puzzle: what are the s-m-n and u-t-m theorems in Haskell?  
> **username_7**: "75 years ago there were no computers around."  This is simply false.  75 years ago there were LOTS of computers around.  They were humans, mostly women; they had advanced mathematics degrees, a few rudimentary mechanical computation tools (like adding machines and slide rules), and lots and lots of paper.  These computers were the backbone of both the Manhattan Project and Bletchley Park during WWII (the Bomb and the Bombe notwithstanding).  This is the computing environment that Turing was modeling: humans with pencil and paper.  
> **username_3**: @Andrej: Good point! Here's the deal for those interested: [utm theorem](http://en.wikipedia.org/wiki/Utm_theorem) and [smn theorem](http://en.wikipedia.org/wiki/Smn_theorem).  
> **username_3**: @JɛﬀE: So, should we count human beings as alive "Turing machines" or alive "families of circuits"? (Seriously!)  
> **username_4**: @Jeffe: Come on, you know what I meant.  
> **username_6**: @SadeqDousti: well if they had families working there ;)  
> **username_3**: @Suresh: LOL :) But seriously, I always think whether the human brain acts differently on various input sizes or not. For instance, if you are to prove the "Pythagorean theorem" or the "P vs NP" theorem, the brain acts totally different. IMHO, this is the reason why it is so difficult to simulate the brain with computers...  
> **username_7**: @Andrej: Yes, I know exactly what you meant, and that's why I objected!  Computer ≠ electronic computer.  
> **username_4**: @JeffE: we can test your hypothesis. Go to your colleagues and ask them to draw a picture of "a computer wearing a short skirt". Please report how many drew a human being.  
> **username_5**: We still need mathematical models for impossibility results (like lowerbounds) and also for comparing algorithms.  
> **username_4**: @username_5: yes of course, and I suggested we should use programming language for that purpose.  
> **username_5**: Hmmm, my problem is complexity theory, I haven't seen anyone use programing languages to teach complexity, I had the feeling that programming languages are not fine grained enough for complexity purposes. Do you think it is possible? Do you know anyone who has done it? (maybe I should post this as a new question since this one was about computability)  
> **username_4**: @username_5: I recommend Bob Harper's blog, in particular this post: http://existentialtype.wordpress.com/2011/03/16/languages-and-machines/  

---

### Answer by username_8 on 2011-02-20. Score: 12

"A function is computable if there is an 'effective procedure' for going from input to output." When introducing this topic, I have in the past pointed out how they (the students) have an effective procedure for solving quadratic equations, but do not have one for solving equations of degree 5 or more. This can segue into a discussion of how one might formalize 'effective procedure', but that discussion is something you want to have happen, so I think that's a feature, rather than a bug.

> **Comments:**
> **username_3**: Nitpicking: [Abel–Ruffini theorem](http://en.wikipedia.org/wiki/Abel–Ruffini_theorem) states that there is no general **algebraic** solution—that is, solution in radicals— to polynomial equations of degree five or higher. However, there are methods, such as the [Bring radical](http://en.wikipedia.org/wiki/Bring_radical), to obtain closed-form solutions of quintic equations.  
> **username_8**: Your nitpicking is actually right-on.  When discussing computability, you want to talk about things like "allowed operations", and solutions to polynomials are one of those things which gets more complex the closer you look at it.  But for an introduction, I think that the words "effective procedure" and a mention of the quadratic formula make a great starting point.  They aren't entirely correct, but the intuition is pretty right-on, IMO.  

---

### Answer by username_9 on 2011-02-20. Score: 8

Perhaps the point is that all of these models aimed to capture what the notion of computability is. The fact that all of them are equivalent, means that the notion they are trying to capture is robust. So although this does not escape your dilemma, this robustness gives credence to the notion that "a function is computable if there is a Turing machine that computes it".


---

### Answer by username_10 on 2011-02-21. Score: 6

I start out asking "is there any question that no computer could ever answer convincingly?" and lead the discussion toward philosophical questions such as "if a tree falls in the forest does it make a sound?" or "is there an afterlife?" We quickly get a consensus that human language can express yes/no questions involving paradoxes or concepts that cannot be expressed mathematically, and so, yes, there are non-computable questions.

Then I ask rhetorically whether there are non-computable questions about concepts that *can* be represented in a computer, e.g. integers and graphs. I say that yes, one example is the famous halting problem, which is about examining a description of a program and saying whether it has any infinite loops. Intuitively, it turns out that infinite loops are like black holes, and any program that observes an infinite loop could get trapped in an infinite loop itself. So any procedure that answers that problem may run forever, so by the definition of "algorithm" no algorithm can answer the halting problem.

Then I dive back into proofs on Turing machines.


---

### Answer by username_11 on 2011-05-10. Score: 0

Well, a function is computable if it accepts inputs that are formed or generated by a specific pattern. A specific pattern means all inputs should have a relation, a particular input can be generated by it previous or next input. If the inputs do not have this type of sequence, then there is no possibility to develop a model or function that can accept. One thing more i want to say that is that there is a basic difference between a machine and a human being. A machine could not be formed for non-sequential inputs but humans are. Also this is big interruption of making actual human behaving robots.

> **Comments:**
> **username_12**: The question is about teaching computability. It would be good if you restrict your answer to material answering that question. Keep in mind that the OP is teaching undergraduates, so personal opinions (such as your last three statements) may not be in scope.  

---

