22
$\begingroup$

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.

$\endgroup$
4
  • 10
    $\begingroup$ "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. $\endgroup$ Feb 20, 2011 at 15:05
  • 5
    $\begingroup$ 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. $\endgroup$ Feb 20, 2011 at 15:45
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 20, 2011 at 16:00
  • $\begingroup$ 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? $\endgroup$ Feb 20, 2011 at 21:03

5 Answers 5

37
$\begingroup$

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.

$\endgroup$
14
  • 2
    $\begingroup$ I quite like this argument, because it goes from the concrete (the iPhone) to the abstract. $\endgroup$ Feb 20, 2011 at 20:29
  • 2
    $\begingroup$ Here's an interesting puzzle: what are the s-m-n and u-t-m theorems in Haskell? $\endgroup$ Feb 20, 2011 at 20:31
  • 18
    $\begingroup$ "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. $\endgroup$
    – Jeffε
    Feb 20, 2011 at 20:46
  • 10
    $\begingroup$ @Jeffe: Come on, you know what I meant. $\endgroup$ Feb 20, 2011 at 21:30
  • 8
    $\begingroup$ @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. $\endgroup$ Feb 22, 2011 at 14:06
12
$\begingroup$

"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.

$\endgroup$
2
  • 3
    $\begingroup$ Nitpicking: 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, to obtain closed-form solutions of quintic equations. $\endgroup$ Feb 20, 2011 at 22:00
  • $\begingroup$ 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. $\endgroup$ Feb 21, 2011 at 1:40
8
$\begingroup$

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".

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Vijay D
    Dec 26, 2012 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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