4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Can I ask for a source of the definition you're using? E.g., the text from which I teach discrete math (Rosen), at a community college, doesn't include such a clause in its definition of "algorithm". I'd suggest you'd be fine to just set that aside for a middle-school class, or leave it until later. In my case I even leave the Halting Problem aside until the last day of class (at which point the course halts). $\endgroup$
    – Daniel R. Collins
    Commented Dec 1, 2020 at 3:49
  • 1
    $\begingroup$ @DanielR.Collins I'm pretty sure the first place I saw it was Computer Science Illuminated by Dale and Lewis. You may be right about leaving it out for the tweenagers. $\endgroup$
    – Bob Brown
    Commented Dec 1, 2020 at 16:00
  • $\begingroup$ For what it's worth, looking at my 1E Dale/Lewis, I don't see that as part of their definition. Consider: following Rosen I emphasize that an algorithm: (a) halts in finite time, and (b) gives correct solutions. The fact that the problem is theoretically solvable seems immediately implied, and therefore not needed explicitly. The existence of problems not-theoretically-solvable seems like a separate, higher-order issue that can be left for later. Indeed, Dale/Lewis leave the idea of "unsolvable" problems for the very last section of the book, just like I do now. Maybe I got it there. $\endgroup$
    – Daniel R. Collins
    Commented Dec 1, 2020 at 22:49
  • $\begingroup$ @DanielR.Collins Not Dale/Lewis, eh? I'll have to poke around. I'm sure it was in a CS0 book, but I gave many of my books away when I retired. $\endgroup$
    – Bob Brown
    Commented Dec 1, 2020 at 23:32

6 Answers 6

Reset to default
2
$\begingroup$

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.

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

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

See https://academic.oup.com/comjnl/article/7/4/313/354243

Small note by C. Strachey

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ First time I notice "goto L". $\endgroup$
    – Michel Billaud
    Commented Apr 1, 2020 at 10:40
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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." $\endgroup$
    – Bob Brown
    Commented Apr 6, 2020 at 2:35
  • 1
    $\begingroup$ @BobBrown Yes, I was just trying to explain why I think you are right to be wary of such examples. $\endgroup$
    – kaya3
    Commented Apr 6, 2020 at 2:39
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This seems rather like one of the Euler Problems. Now I want to go do it :) $\endgroup$
    – Ben I. ♦
    Commented Apr 1, 2020 at 0:05
  • 1
    $\begingroup$ @BenI., much too simple for an Euler Problem. $\endgroup$
    – Buffy
    Commented Apr 1, 2020 at 0:28
2
$\begingroup$

Emil Post's correspondence problem is quite a good example. Its nice because it can often be solved by inspection in simple cases but there is no known algorithm for doing so. Its good to know about too - twice in my career I have been asked to solve it, so knowing it was undecidable certainly helped me.

https://en.wikipedia.org/wiki/Post_correspondence_problem

Unscrupulous employers can exploit the undecidability by preventing their employees from validating their payslips. If employees are paid in multiple parts for jobs performed over multiple contracts matching the payments to the work is an example.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.