Computation Sequence

Given a register machine with upper register index and a Configuration of a Register Machine of length , we can define the action of on . We say that transforms to . The definition is as expected based on the -instructions.

Definition

If is a register machine with upper register index and input , then the computation sequence of with input is defined by recursion:

We say that he computation halts if there is some element in the sequence . Otherwise, we say that the computation sequence does not halt.

Note

We require the input to be of appropriate length but we just conventionally pad it with empty words if it is not.