Counter-Example for Computability

I am a retired college teacher, now trying to teach computing to middle school kids. One of the parts of the definition of "algorithm" is that it must be "effectively computable." I'm looking for an example that is not Turing computable. I've used "solve world hunger" in the past, but but that seems fuzzy and amorphous.

Today I've spent some time with "Label an arbitrary statement as true or false," but I can't make it sing in a way that kids will say, "Yeah... that's right." Busy Beaver and the halting problem are both too complicated to explain in a few minutes. (I know about Scooping the Loop Snooper and have even assigned it as reading, but it would still take too much classroom time.)

Suggestions, either of new ideas or of a way to make "Label an arbitrary statement..." sing to the students would be most appreciated.

I guess I'm not understanding what the problem is with fuzzy when talking about computability with a group of 12 year olds. They can instantly grok the notion that the question isn't one that computers can address. You could also go with moral/ethical dilemnas.

If you want something more mathematical that they can still probably understand, ask them whether the last digit of $$\pi$$ is computable, even by the fastest computer that could ever exist in some theoretical universe.

Finally, there's always my favorite undecidable problem on Wikipedia: Determining whether a player has a winning strategy in a game of Magic: The Gathering.

• Thank you. I really like the 'last digit of pi' question. – Bob Brown Mar 31 at 10:21
• Well, except that the last digit of pi doesn't exist. Close, but I can't award any cigars. – Buffy Mar 31 at 10:51
• Like I needed any more papers to read to procrastinate :) – D. Ben Knoble Mar 31 at 12:34

Strachey's proof for the Halting Problem is accessible to anyone who accepts reasoning by contradiction.

• First time I notice "goto L". – Michel Billaud Apr 1 at 10:40

This isn't an answer, but you might find it interesting for this age level.

I've included it because at this stage of development, some discussion of finite, infinite, bounded, and unbounded might be a useful concept to teach.

It is a programming assignment in two parts. A number is rational if and only if its decimal expansion repeats a finite sequence of digits infinitely. This results in the two parts of the assignment.

For example 3/7 = 0.428571... where the ellipsis is the infinite repetition of the six digits just preceding it. And 1/5 = .20 just repeats 0 infinitely.

Part 1 of the assignment. Write a program in your favorite programming language that will take a rational number - a fraction - less than 1 (so that it's leftmost digit will be 0) and find the minimal decimal repeating sequence. For 3/7 it would be 4, 2, 8, 5, 7, 1. This is actually an exploration of the standard "by-hand" division algorithm that was and maybe is known to all students.

Part 2. Take a repeating decimal value less than 1 and find the fraction equivalent to it with the fraction given in lowest terms. That is, find the numerator and the denominator of the fraction in lowest terms. This requires finding the GCD of two values so that you can reduce a first computed value to lowest terms. 3/7 is quite interesting as an example here since it probably requires finding the GCD of two rather large values.

There is a lot to talk about here, including various ways to find GCD and even to find the digits of the decimal expansion one after the other. You can also use it as an introduction to irrational numbers, since a student can imagine, at least, a non repeating decimal. Using a diagonal process you can even demonstrate the existence of such a value. You can also explore the maximum length of the repeating sequence for a rational number wrt the denominator of the fraction in lowest terms.

And a fun fact is that .9..., with 9's repeating forever, is equal to 1. Therefore the decimal expansion needn't be unique 1 is also 1.0.

And note, in the context of the question asked here, while a TM can't compute "all the digits" of 3/7 (an infinite sequence), it can compute the repeating prefix.

Since it isn't an answer, I've marked it for community ownership.

• This seems rather like one of the Euler Problems. Now I want to go do it :) – Ben I. Apr 1 at 0:05
• @BenI., much too simple for an Euler Problem. – Buffy Apr 1 at 0:28

I would beware of vague examples like "solve world hunger" because it is not a well-defined mapping from program inputs to program outputs. The problem description doesn't tell you what input such a program would expect, nor how to determine whether the program's output is correct. So, it doesn't capture the formal idea of computability. I wouldn't try to teach a formal definition at school level, but I'd still try to teach something consistent with the formal definition, to avoid promoting misconceptions.

Here are two concrete examples which work both intuitively while still being formally uncomputable:

• There is no algorithm which takes an arbitrary calendar date as input, and outputs an array containing the lottery numbers for that date.
• There is no algorithm which takes as input an arbitrary calendar date and a person's name, and outputs the first word that person speaks on that date.

As well as it being intuitively impossible to predict lottery numbers in the future, a truly random sequence is uncomputable in the formal sense with probability 1. For the second example, you can give the following proof: whatever algorithm you write, I can run it with tomorrow's date and my own name, wait until midnight and then say any word your algorithm didn't output.

• I really like the examples, but I'm pretty sure "fuzzy and amorphous" means the same thing as "not a well-defined mapping from program inputs to program outputs." – Bob Brown Apr 6 at 2:35
• @BobBrown Yes, I was just trying to explain why I think you are right to be wary of such examples. – kaya3 Apr 6 at 2:39

The key feature of a Turing Machine is that it is finite, though unbounded. Any problem that implies actual infinity either in time (halting) or space (the tape), isn't Turing Computable. So, computing all the digits of pi (an infinite sequence) isn't computable, though a TM can compute any prefix.

But you don't even need to discuss irrational numbers to come up with an example. A TM can't list all of the odd integers.

The Halting Problem on the other hand is concerned with time. Any computation must take a finite (though unknown) amount of time.

And even though the TM is normally described as having an infinite tape, the requirement that an algorithm terminate (finite time) implies that only a finite section of the tape can be read or written (finite space).

And I think that an accurate description of the limits of a TM lets you avoid magic as well as the fundamentally unknowable.

Owen Astrachan (Duke U) once presented a simple illustration of the Halting Problem. If you look on his "papers" page, follow the link labelled Self Reference (a pdf). I've pointed to the containing page since it should be of general interest to readers here.