tag:blogger.com,1999:blog-3722233.post44450853695391906..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: My Survey on Hilbert's 10th for particular (d,n) is ready for you to help me on!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-38441775418720160122021-01-16T13:50:41.195-06:002021-01-16T13:50:41.195-06:00Another minimalist computational model is combinat...Another minimalist computational model is combinatory logic. John Tromp's <a href="https://tromp.github.io/cl/cl.html" rel="nofollow">Lambda Calculus and Combinatory Logic Playground</a><br />mentions a "206 bit binary lambda calculus (blc) self-interpreter".<br /><br />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.Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49414800617636490642021-01-06T12:27:26.575-06:002021-01-06T12:27:26.575-06:00AH- the connection is that it is possible that a m...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. <br /><br />If you want to be acknowledged in the paper, email me your name- it seems to not be at any of the links you send. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1594232609343537562021-01-06T12:13:42.531-06:002021-01-06T12:13:42.531-06:00this may not sound exactly related, but my feeling...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.<br />basically 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. <br />think conways FracTran language is also another neat/ key reference along these lines. feel it should be cited whenever Hilbert 10th is cited.<br />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.<br />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.<br /><br />https://cstheory.stackexchange.com/a/11614/7884<br /><br />https://arxiv.org/abs/1605.04343<br /><br />https://vzn1.wordpress.com/2016/01/22/undecidability-the-ultimate-challenge/<br />vznhttp://vzn1.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89207704521854952972021-01-06T10:27:12.204-06:002021-01-06T10:27:12.204-06:00AH- a proof that does not go through turing machin...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. <br /><br />And indeed, some new technique may be needed. I will modify my paper to reflect those thoughts.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74340089536623582172021-01-06T08:04:32.435-06:002021-01-06T08:04:32.435-06:00> I suspect the function is computable. Why? W...> 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.<br /><br />Isn'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?Dániel Vargahttps://www.blogger.com/profile/10626372642275036283noreply@blogger.com