tag:blogger.com,1999:blog-3722233.post3270621784797289581..comments2024-04-20T13:30:48.050-05:00Comments on Computational Complexity: A table for Matrix Mortality- what I wanted for Hilbert's 10th problemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-25199715194248001192020-07-17T12:37:10.242-05:002020-07-17T12:37:10.242-05:00Even if the problem does not mention Turing machin...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50260725054913651192020-07-16T22:11:11.029-05:002020-07-16T22:11:11.029-05:00Thanks for both your comments. If you are right th...Thanks for both your comments. If you are right then the students are doing Google-search and Pattern-matching in a terrible way.<br /><br />Pure copying without understanding.<br /><br />Fortuantely it was only one student who mentioned Kruskal Trees,<br />though I wonder if some who got it right (with the Matrix problem) were as clueless but just happened to copy a correct<br />answer.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63361098604954068722020-07-06T20:45:55.670-05:002020-07-06T20:45:55.670-05:00(Another point I forgot to stress, having to do wi...(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.)Aatu Koskensiltahttps://www.blogger.com/profile/10999226899475411504noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67109675744594448292020-07-06T20:27:45.367-05:002020-07-06T20:27:45.367-05:00My take on the Kruskal business is that it’s proba...My 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”.Aatu Koskensiltahttps://www.blogger.com/profile/10999226899475411504noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7027579506410370362020-07-06T12:42:45.590-05:002020-07-06T12:42:45.590-05:00@j2kun: To the contrary, there is a lot of researc...@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 STACSAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66841833982284148242020-07-06T11:50:43.086-05:002020-07-06T11:50:43.086-05:00Another rich source of undecidable non-turing-mach...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.<br /><br />I 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.j2kunhttps://www.blogger.com/profile/08041921049916424212noreply@blogger.com