[Solved]: Upper bound on register machine contents

Problem Detail: 

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?

Asked By : Cosmic Ossifrage

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11678

3.2K people like this

 Download Related Notes/Documents