Easy-to-describe example of uncomputable function

After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine. A curious philosophy major asked for an example of such a function. Most of the students in the class are not CS students and need not be mathematically adept, so I am limited as to what I can say, except to those students who want to hear more outside of class.

The only example of a particular function that is uncomputable that I could come up with off the top of my head was the halting problem, but that would have required a substantial digression, and it would seem quite obscure to most of the students if I walked them through it. It would also not be sufficiently useful to explain to the class why there must be uncountably many functions that are not Turing-computable. (First step: teach the countable/uncountable distinction.)

Is there an example of an uncomputable function that's relatively easy to describe and understand--more so than the halting problem?

• Post correspondence problem? – Yuval Filmus Feb 11 '20 at 23:34
• Given a multivariate polynomial $p$, is there a way to assign an integer to each of the variables such that $p$ evaluates to 0? This problem, finding solutions to "Diophantine equations", was shown to be hard by the MRDP theorem. A fun example of when Diophantine equations go crazy is discussed here (note that you can multiply through by (🍌+🍎)(🍌+🍍)(🍍+🍎) to get something in the form of a polynomial). That particular puzzle has an extra positivity requirement. – Yonatan N Feb 12 '20 at 0:01
• Calculating the last digit of pi? – alvitawa Nov 5 '20 at 13:41

2 Answers

A classic example of an uncomputable function is The Busy Beaver Problem: For each N, consider all N-state Turing Machines over the alphabet { [blank], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.

• Still not simple or intuitive enough to be obviously of use with my students, but it is relatively simple. Thanks PMar. As with Yuval Filmus's and Yonathan N's suggestions, I can think about whether there's a good way to present it. – Mars Feb 13 '20 at 16:51

The proof that Radò's function $$\Sigma(n)$$ (maximal number of 1 written by an $$n$$ state Turing machine starting on a tape of all 0s before halting) isn't computable is rather simple, once you have a few building blocks. First, by convention Turing machines start in state 1 and halt by moving to the (non-existent) state $$n + 1$$ (so you can build a machine that does $$M_1$$ then $$M_2$$, written $$M_1 \mid M_2$$, by just renumbering the states of $$M_2$$ and copying it after $$M_1$$). Represent number $$N$$ by $$N$$ ones starting at the current head's position. Build a machine $$\mathtt{Twice}$$ that starts with $$N$$ on the tape and stops at the start of $$2 N$$ (can build $$\mathtt{Dup}$$, that copies $$N$$ after itself separated by a 0 -- can be done by overwriting 1 with 0, move to the end and add a 1, go back to the second 0, replace by 1 and go for the next 1, repeat until you hit 0, then move back to the start --, compose it with $$\mathtt{Add}$$ that adds $$M$$ + $$N$$ separated by a single 0 by just squashing them together then moving to the beginning), a machine $$\mathtt{Inc}$$ that increments the number on the tape (very simple, move to the first 0, write a 1 there, move back to the first 1), will also need machines $$\mathtt{Write}_n$$ which writes $$n$$ on the tape and stops at it's beginning (can be done in $$n$$ states, just write a 1 and move left $$N$$ times; we will run this at the start, so it doesn't matter if it messes up the tape). Now assume there is a machine $$\Sigma$$ that reads $$n$$ and writes out $$\Sigma(n)$$. Compose $$\mathtt{Twice} \mid \Sigma \mid \mathtt{Inc}$$, say the result has $$N$$ states. Then $$\mathtt{Write}_N \mid \mathtt{Twice} \mid \Sigma \mid \mathtt{Inc}$$ has $$2 N$$ states, but writes $$\Sigma(2 N) + 1$$, contradiction.

• vonbrand, is this different from the Busy Beaver problem mentioned by @PMar? (Either way, probably more involved than what I needed, optimally, for my students.) – Mars Feb 17 '20 at 4:39