<<
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.
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.
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
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