2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Post correspondence problem? $\endgroup$ – Yuval Filmus Feb 11 '20 at 23:34
  • 4
    $\begingroup$ 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. $\endgroup$ – Yonatan N Feb 12 '20 at 0:01
  • $\begingroup$ Calculating the last digit of pi? $\endgroup$ – alvitawa Nov 5 '20 at 13:41
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Mars Feb 13 '20 at 16:51
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$ – Mars Feb 17 '20 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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