3
$\begingroup$

I am doing some work on register machine theory which revolves around a 2-register register machine and attempting to show that it is not possible to compute an upper-bound on the final contents of its two registers on the basis of its program code and initial input, in halting configurations only. I believe this can be related in some way to the busy beaver problem, but I cannot quite see how, and the stipulations that it is for halting configurations only has confused me somewhat.

What do I know so far?

  • Clearly a register machine configuration specified by the 3-tuple (instruction label, register 0, register 1) has an infinite number of possible states, owing to the abstract nature of the machines, as no practical limit is imposed on the size of the natural numbers which can be stored in each register.

  • I considered whether I could simply define a partial function $f : \mathbb{N}^3 \to \mathbb{N}$ where the arguments are the program encoded as a natural number and the initial contents of the two registers, but I do not think this gets me anywhere. I defined the function to be undefined when the partial function computed by the register machine specification is undefined on the given input, as the problem specifies computing the upper bound for halting configurations only.

    Therefore, I cannot use a diagonal argument to suggest it would imply the halting problem, because being undefined for a non-halting configuration suggests it would not.

  • Secondly, I tried to come up with a proof on the basis that there is an infinite number of possible configurations which a 2-register machine can be in. In particular, there is an infinite number of possible programs $e \in \mathbb{N}$ which could be executed, and each of those programs can be executed on an infinite number of initial register configurations $\mathbb{N}^2$.

    By construction, if there is a machine which can decide this partial function for any given combination, then I thought it may be the case that it required an infinite number of states in which to do so - which is of course not possible, as a register machine must be specified by a finite number of instructions.

I am not confident that either approach is correct or not, and wonder whether either of the above is a correct tact or if a formal proof exists for this?

$\endgroup$
1
$\begingroup$

Hint: Your computation model is Turing-complete. If you could compute an upper bound, that would enable you to solve the halting problem.

$\endgroup$
  • $\begingroup$ Thanks! I see the logic - if a machine does not halt, then it is possible to build a counter example such that any upper bound will eventually be exceeded, so if the upper bound could be computed for such a machine, it leads to solving the halting problem. Does the stipulation "in halting configurations only" modify this result, though? I think that was the bit which threw me right off. $\endgroup$ – Cosmic Ossifrage Apr 30 '13 at 16:45
  • $\begingroup$ The stipulation is just fine, as you're only interested in halting configurations anyhow. Plus, non-halting problems in which the counters don't increase indefinitely can actually be detected. $\endgroup$ – Yuval Filmus Apr 30 '13 at 22:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.