0
$\begingroup$

I have been searching the web for a mathematical model of a register machine and have fallen short. The closest I have found is found here:

enter image description here

But I am looking for more detail than what is provided there, such as similar to the Turing Machine definition using tuples:

enter image description here

What resource describes the mathematical definition of either register machines or RAM machines at this level of formality? If none exist, how would you describe it (or please write the definition here otherwise for reference).

$\endgroup$

1 Answer 1

2
$\begingroup$

In my taste the register machine definition you found is good to go. The only difference is that it specifies its components using the phrase "is specified by", whereas the second definition lists those components explicitly as a 7-tuple.

The components of the register machine in tuple style are probably a sequence of registers, a set of labels, and a list of instructions, one for each label. What is perhaps lacking is the specification of an initial label, where the computation starts.

Your Turing machine might be formally specified, but it contains only the hardware (states and alphabet) and the program (transition function) but it lacks semantics: how do we build computations, what is the behaviour of the machine? The register machine does contains some semantics, although in words only, "add 1 to the contents of register $R$", but quite sufficient to see what is the meaning of the instructions.

Note there is no unique formalization of a register machine. There are variuos possibilities for the available instruction types. Wikipedia lists various historical variants.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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