Matiyasevich has reformulated RH as a computer science problem : "a particular explicitly presented register machine with 29 registers and 130 instructions never halts", see this reference .

Is that type of problem tractable with current knowledge ? If not, what are some key challenges, and what are the most advanced results so far (in terms of number of registers and instructions, or any relevant complexity measure) ?

  • 5
    $\begingroup$ This is not the way it works. There are no general methods how to treat halting problems for specific machines (after all, the general problem is undecidable). The way to show whether a particular machine halts is to figure out the underlying mathematics of what the machine is doing, and see if it makes it terminate. In this case, this means: figure out that the machine actually verifies instances of RH, solve the RH, and answer the halting problem accordingly. $\endgroup$ Jan 4 at 16:06
  • 4
    $\begingroup$ Moral: reformulating a problem in a different language only helps if it adds insight, not if it just obfuscates the problem. $\endgroup$ Jan 4 at 16:07
  • $\begingroup$ I find the absence of any method surprising. Are there not a least different classes of register machines for which more can be said? $\endgroup$ Jan 5 at 10:09
  • 3
    $\begingroup$ Yes, of course, sometimes you can, see this interesting attempt for example github.com/mmjb/T2. But as it is undecidable, you cannot expect anything fully automatized. And as Emil already put it elegantly, if proving termination boils down to solving an long standing open question, it is unlikely such automated tools will solve it anyway, the mathematical formulation being already way more informative than an obscure program... It looks like trying to prove a statement of ZFC from its Gödel number. $\endgroup$
    – holf
    Jan 5 at 11:40

Your Answer

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

Browse other questions tagged or ask your own question.