Hilbert's 10th problem is (in modern terminology) to find an algorithm that will, given a poly
p(x1,...,xn) in Z[x1,...,xn], determine if it has a solution in the integers.
This was shown undecidable by the combined efforts of Davis-Putnam-Robinson and Matiyasevich.
I posted here about the question of: For which (d,n) is H10 undecidable when restricted to degree d and number of vars n?
I was invited to make an article out of the blog post and what I learned from the comments for the Algorithms column of BEATCS. That first draft is
Did I miss an important reference? (Note- I had meant to get out Matiyasevich's book on H10 but have been unable to because of the Pandemic, so if you have it my have stuff I need to know.)
Did I misspell Matiyasevich?
Did I say something stupid?
Please leave comments or email me directly if you have suggestions.
Incidentally I am usually the one who is asking someone else to do an open problems column, a book review, a guest blog. Nice to be the askee instead of the asker for a change of pace.
> I suspect the function is computable. Why? What would a proof that this function is not computable look like? It would have to code a Turing machine computation into a very a restricted equation. This seems unlikely to me.
ReplyDeleteIsn't it possible that the function is not computable, but the proof of this goes through some avenue other than encoding a Turing machine into this form? Can a proof necessarily be transformed into an encoding? Alternatively, isn't it possible that the proof of this does actually encode a Turing machine into this form, but via some currently unknown, alien kind of reduction?
AH- a proof that does not go through turing machines! It would have to go through SOME undecidable problem, perhaps code H10 into a smaller equation! Perhaps Matrix Mortality problem! Food for thought.
DeleteAnd indeed, some new technique may be needed. I will modify my paper to reflect those thoughts.
this may not sound exactly related, but my feeling is that there is a connection here, and hope you can work in these refs. there is a neat analysis of TMs that counts symbols vs states and tries to find whether universal TMs (UTMs) exist for those symbols/ states. it is not done wrt number theory, but wrt CS. there is likely a rough mappinng between H(d,n) and this other map, TM(sy, st). the existing research in CS is wrt busy beaver functions.
ReplyDeletebasically another way to see this more generally is that there are all kinds of problems with parameters that cross into an undecidable boundary for various parameter ranges.
think conways FracTran language is also another neat/ key reference along these lines. feel it should be cited whenever Hilbert 10th is cited.
other relatively recent related research, yedidia + aaronson worked on building small TMs that capture arithmetic logic and lead to undecidability. also related to busy beaver research.
over the years have worked on coding small TMs for real problems myself etc., think it would be nice if someone built a TM compiler as open source for related research, have something like it from yrs ago.
https://cstheory.stackexchange.com/a/11614/7884
https://arxiv.org/abs/1605.04343
https://vzn1.wordpress.com/2016/01/22/undecidability-the-ultimate-challenge/
Another minimalist computational model is combinatory logic. John Tromp's Lambda Calculus and Combinatory Logic Playground
Deletementions a "206 bit binary lambda calculus (blc) self-interpreter".
I'm not sure how this complexity compares with Turing machines, or whether it would be easier to apply to problems like Hilbert's 10th.
AH- the connection is that it is possible that a more DETAILED study of TMs, perhaps small ones that are a focus of your work and the other refs you give, might make the proofs of undecidabilty easier and may even be a way to solve solve some problems. I will later today work that into my discussion at the end of future directions.
ReplyDeleteIf you want to be acknowledged in the paper, email me your name- it seems to not be at any of the links you send.