<<

A Register Machine (abbreviated RM) is a computer model specified by a

program P = <c_0, ..., c_(h−1)>, consisting of a finite sequence of commands.

Intuitively, the commands operate on registers R_1, R_2, ..., each capable of storing an arbitrary

natural number.

The possible commands are:

- R_i <= 0 A
- R_i <= R_i + 1
- if R_i = R_j goto k

A

instruction counter (i.e. the number of the next command to be executed) and R_1, ..., R_m

are the current values of the registers.

**state**is an m + 1-tuple <K, R_1, ..., R_m> of natural numbers, where intuitively K is theinstruction counter (i.e. the number of the next command to be executed) and R_1, ..., R_m

are the current values of the registers.

Given a state s = <K, R_1, ..., R_m> and a

program P = <c_0, ..., c_(h−1)>, the

when command c_K is applied to the register values given by s.

program P = <c_0, ..., c_(h−1)>, the

**next state**s' = NextP(s) is intuitively the state resultingwhen command c_K is applied to the register values given by s.

**Input/Output conventions**

A program P computes a (partial) function f(a_1, . . . , a_n) as

follows:

follows:

- initially place a_1, ..., a_n in R_1, ..., R_n and set all other registers to 0
- start execution

with command c0. That is, the initial state is

s_0 = <0, a_1, ..., a_n, 0, ..., 0>

If P halts starting in state s0, the final value of R_1 must be f(a_1, ..., a_n).

>> [source]

Finally I found (again) the definition of this simple imperative programming language, that I remembered from my Formal Methods course. It is more primitive than While (def), it has GOTOs and to me it offers a very clear model for computation, similar to that offered by BASIC, and in some sense very

**mechanical**.

## No comments:

## Post a Comment