Answers.Body: <p>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 <em>all</em> the digits of pi (an infinite sequence) isn't computable, though a TM can compute any prefix. </p>
  
  <p>But you don't even need to discuss irrational numbers to come up with an example. A TM can't list <em>all</em> of the odd integers. </p>
  
  <p>The Halting Problem on the other hand is concerned with time. Any computation must take a finite (though unknown) amount of time. </p>
  
  <p>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). </p>
  
  <p>And I think that an accurate description of the limits of a TM lets you avoid magic as well as the fundamentally unknowable. </p>
  
  <p>Owen Astrachan (Duke U) once presented a simple illustration of the Halting Problem. If you look on <a href="https://users.cs.duke.edu/~ola/papers.html" rel="nofollow noreferrer">his "papers" page</a>, follow the link labelled <em>Self Reference</em> (a pdf). I've pointed to the containing page since it should be of general interest to readers here. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T11:01:39.160Z
Answers.LastActivityDate: 2020-03-31T12:30:40.937Z
Answers.LastEditDate: 2020-03-31T12:30:40.937Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>I guess I'm not understanding what the problem is with <em>fuzzy</em> 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.  </p>
  
  <p>If you want something more mathematical that they can still probably understand, ask them whether the last digit of <span class="math-container">$\pi$</span> is computable, even by the fastest computer that could ever exist in some theoretical universe.</p>
  
  <p>Finally, there's always my favorite undecidable problem on Wikipedia: <a href="https://en.wikipedia.org/wiki/List_of_undecidable_problems#cite_note-9" rel="nofollow noreferrer">Determining whether a player has a winning strategy in a game of Magic: The Gathering.</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T10:21:10.087Z
Answers.Text: Thank you.  I *really like* the 'last digit of pi' question.
Answers.UserDisplayName: Bob Brown
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T10:51:38.167Z
Answers.Text: Well, except that the last digit of pi doesn't exist. Close, but I can't award any cigars.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T12:34:08.527Z
Answers.Text: Like I needed any more papers to read to procrastinate :)
Answers.UserDisplayName: D. Ben Knoble
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T03:40:04.797Z
Answers.LastActivityDate: 2020-03-31T03:40:04.797Z
Answers.UserDisplayName: Ben I.
Answers.Body: <p>Strachey's proof for the Halting Problem is accessible to anyone who accepts reasoning by contradiction.</p>
  
  <p>See 
  <a href="https://academic.oup.com/comjnl/article/7/4/313/354243" rel="noreferrer">https://academic.oup.com/comjnl/article/7/4/313/354243</a></p>
  
  <p><a href="https://i.sstatic.net/XrkFg.png" rel="noreferrer"><img src="https://i.sstatic.net/XrkFg.png" alt="Small note by C. Strachey"></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-01T10:40:54.497Z
Answers.Text: First time I notice "goto L".
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T16:12:54.510Z
Answers.LastActivityDate: 2020-03-31T16:12:54.510Z
Answers.UserDisplayName: Michel Billaud
Answers.Body: <p>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 <em>consistent</em> with the formal definition, to avoid promoting misconceptions.</p>
  
  <p>Here are two concrete examples which work both intuitively while still being formally uncomputable:</p>
  
  <ul>
  <li>There is no algorithm which takes an arbitrary calendar date as input, and outputs an array containing the lottery numbers for that date.</li>
  <li>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.</li>
  </ul>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T02:35:47.460Z
Answers.Text: 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."
Answers.UserDisplayName: Bob Brown
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T02:39:37.640Z
Answers.Text: @BobBrown Yes, I was just trying to explain why I think you are right to be wary of such examples.
Answers.UserDisplayName: kaya3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T02:08:27.703Z
Answers.LastActivityDate: 2020-04-06T02:08:27.703Z
Answers.UserDisplayName: kaya3
Answers.Body: <p>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.</p>
  <p><a href="https://en.wikipedia.org/wiki/Post_correspondence_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Post_correspondence_problem</a></p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T22:34:28.230Z
Answers.LastActivityDate: 2020-11-29T22:34:28.230Z
Answers.UserDisplayName: Jon Guiton
Answers.Body: <p>This isn't an answer, but you might find it interesting for this age level. </p>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <p>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 <em>imagine</em>, 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. </p>
  
  <p>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. </p>
  
  <p>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 <em>can</em> compute the repeating prefix. </p>
  
  <hr>
  
  <p>Since it isn't an answer, I've marked it for community ownership.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-01T00:05:37.417Z
Answers.Text: This seems rather like one of the Euler Problems. Now I want to go do it :)
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-01T00:28:07.537Z
Answers.Text: @BenI., much too simple for an Euler Problem.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-31T17:33:07.003Z
Answers.LastActivityDate: 2020-04-01T00:20:15.637Z
Answers.LastEditDate: 2020-04-01T00:20:15.637Z
Answers.UserDisplayName: Buffy
Body: <p>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 <em>not</em> Turing computable.  I've used "solve world hunger" in the past, but but that seems fuzzy and amorphous.</p>
  
  <p>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 <a href="http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html" rel="nofollow noreferrer">Scooping the Loop Snooper</a> and have even assigned it as reading, but it would still take too much classroom time.)</p>
  
  <p>Suggestions, either of new ideas or of a way to make "Label an arbitrary statement..." sing to the students would be most appreciated.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-01T03:49:11.637Z
Comments.Text: 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).
Comments.UserDisplayName: Daniel R. Collins
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-01T16:00:04.423Z
Comments.Text: @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.
Comments.UserDisplayName: Bob Brown
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-01T22:49:36.653Z
Comments.Text: 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.
Comments.UserDisplayName: Daniel R. Collins
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-01T23:32:04.170Z
Comments.Text: @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.
Comments.UserDisplayName: Bob Brown
Tags: <lesson-ideas>
Title: Counter-Example for Computability
ThreadText: # Counter-Example for Computability
  
  (Asked by: username_0 on 2020-03-30)
  
  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](http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html) 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.
  
  **Tags:** lesson-ideas
  
  > **Comments:**
  > **username_1**: 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).  
  > **username_0**: @username_1 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.  
  > **username_1**: 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.  
  > **username_0**: @username_1  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.  
  
  ---
  
  ## 6 answers
  
  ### Answer by username_3 on 2020-03-31. Score: 2 | Accepted answer
  
  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.](https://en.wikipedia.org/wiki/List_of_undecidable_problems#cite_note-9)
  
  > **Comments:**
  > **username_0**: Thank you.  I *really like* the 'last digit of pi' question.  
  > **username_2**: Well, except that the last digit of pi doesn't exist. Close, but I can't award any cigars.  
  > **username_4**: Like I needed any more papers to read to procrastinate :)  
  
  ---
  
  ### Answer by username_5 on 2020-03-31. Score: 6
  
  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](https://i.sstatic.net/XrkFg.png)](https://i.sstatic.net/XrkFg.png)
  
  > **Comments:**
  > **username_5**: First time I notice "goto L".  
  
  ---
  
  ### Answer by username_6 on 2020-04-06. Score: 4
  
  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.
  
  > **Comments:**
  > **username_0**: 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."  
  > **username_6**: @username_0 Yes, I was just trying to explain why I think you are right to be wary of such examples.  
  
  ---
  
  ### Answer by username_7 on 2020-11-29. Score: 2
  
  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.
  
  
  ---
  
  ### Answer by username_2 on 2020-03-31. Score: 2
  
  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.
  
  > **Comments:**
  > **username_3**: This seems rather like one of the Euler Problems. Now I want to go do it :)  
  > **username_2**: @BenI., much too simple for an Euler Problem.  
  
  ---
  
  ### Answer by username_2 on 2020-03-31. Score: 1
  
  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](https://users.cs.duke.edu/~ola/papers.html), 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.
  
  
  ---
  
  