Saturday, December 19, 2015

The programming language for Register Machines


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 state is an m + 1-tuple <K, R_1, ..., R_m> of natural numbers, where intuitively K is the
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.

Given a state s = <K, R_1, ..., R_m> and a
program P = <c_0, ..., c_(h−1)>, the next state s' = NextP(s) is intuitively the state resulting
when 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
  • 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