I told my formal lang theory class about Hilbert's 10th problem as a natural example of an undecidable question- that is, an example that had nothing to do with Turing Machines. On the final I asked

*Give an example of an undecidable problem that has nothing to do with Turing Machines.*

Because of the pandemic this was a 2-day take home final which was open-book, open-notes, open-web. So they could have looked at my slides.

And indeed, most of them did give Hilbert's 10 problem (more formally, the set of all polynomials in many vars over Z which have a Diophantine solution).

But some did not. Some said there could never be such a problem (this is an incorrect answer), Some were incoherent. One just wrote ``Kruskal Trees'' (not sure if he was referring to MSTs or WQOs or to something that Clyde Kruskal did in class one day).

One student said that the problem of, given a CFG G, is the complement of L(G) also CFG.

This is indeed undecidable and does not have to do with TMs. I doubt the student could have proven that. I doubt I could have proven that. I do not doubt that my advisor Harry Lewis could have proven that, and indeed I emailed him asking for a proof and he emailed me a sketch, which I wrote out in more detail here.

The most interesting answer was given by some students who apparently looked at the web (rather than at my slides) for lists of problems and found the following called Matrix Mortality:

{ (M_1,...,M_L) : such that some product of these matrices (you are allowed to use a matrix many times) is the 0 matrix}

Why was this the most interesting? The TA did not know this problem was undecidable until he saw it on the exams and looked it up. I did not know it was undecidable until my TA told me.

I then raised the question: How many matrices to you need and how big do their dimensions have to be?

Unlike H10, there IS a table of this. In this paper they have such a table. I state some results:

Undecidable:

6 matrices, 3x3

4 matrices, 5x5

3 matrices 9x9

2 matrices 15x15

Decidable

2 matrices 2x2

So there are some gaps to fill, but there is not the vast gulf that exists between dec and undec for Hilberts 10th problem. I also note that the paper was about UNDEC but mentioned the DEC results, where as the papers on H10 about UNDEC seem to never mention the DEC.

I am glad to know another natural Undec problem and I will likely tell my students about it next spring. And much like H10, I won't be proving it.

An open problem in education: how come some of my students got it wrong? gave an answer that was not in my notes or slides? One student told me it was easier to google

*Natural Undecidable Questions*

then look through my slides. Another one said:

*In class you said `this is a natural undecidable problem'.*

*On the exam you said `a problem that does not mention Turing Machines'*

*I did not know they were the same.*

That student submitted the Matrix problem stated above. It IS a fair point that `natural' is an

undefined term. But the problem on the final used the well defined concept `does not mention Turing Machines'

Another rich source of undecidable non-turing-machine problems are the word problems on finitely-presented groups. I.e., given a group presentation in terms of generators and relators, and given a single word, determine if that word represents the identity element of the group.

ReplyDeleteI don't think anybody studies the contours of this problem anymore, since most reference books I found when I was interested in this problem were typeset using a typewriter. My impression was that the area of study was too intractable, and they had already classified many special subclasses of groups that had solvable word problems.

@j2kun: To the contrary, there is a lot of research going on in computational group theory which gets regularly published e.g. at ICALP (B), LICS or STACS

ReplyDeleteMy take on the Kruskal business is that it’s probably a reference to the independence of the Kruskal tree theorem from ATR_0 (the theory in reverse mathematics corresponding to the Feferman-Schütte analysis of predicativity). (The.theorem is equivalent to Pi-1-2 - BI_0 over ATR_0, where the letter soup is again a bit of proof theoretic jargon.) This would of course involve a confusion about the intended meaning of ”undecidability”.

ReplyDelete(Another point I forgot to stress, having to do with the confusion over the intended meaning of ”undecidable”, is that if you Google *natural undecidable problems* you will in all likelihood be lead to discussion about theorems undecidable in formal theories capturing some natural mathematical principles that are themselves *natural” in the sense their statements don’t involve proof-theoretic machinery and coding, but are rather expressed in terms that have an ordinary, non-logicky sort of mathematical feel to them, e.g. the Paris-Harrington theorem, the sort of things Harvey Friedman is always on about, etc.)

ReplyDeleteThanks for both your comments. If you are right then the students are doing Google-search and Pattern-matching in a terrible way.

DeletePure copying without understanding.

Fortuantely it was only one student who mentioned Kruskal Trees,

though I wonder if some who got it right (with the Matrix problem) were as clueless but just happened to copy a correct

answer.

Even if the problem does not mention Turing machines, I think that for many (all?) of these undecidable questions, the proof of undecidability amounts to implementing a Turing machine in that problem, with the machine halting or not depending on the solution to that problem. Is there a good example of an undecidable problem where the proof really does not involve constructing a Halting problem?

ReplyDelete