We will define a random-access machine as follows: Data types.
The only data type we will support is the natural numbers 0, 1,
2, 3, .... (However, numbers may be arbitrarily large.)
Variables. We will allow an arbitrary number of variables, each
capable of holding a single natural number. All variables will
be initialized to 0. Tests. We will allow the following test:
<variable> = 0 Statements. Our language will have the following
types of statements: if <test> then <statement> else
<statement>; while <test> do <statement>; <variable> :=
<variable> + 1;(increment) <variable> := <variable> -
1;(decrement) (Note: Decrementing a variable whose value is
already zero has no effect.) In addition, we will permit
statements to be executed in sequence <statement>; <statement>;
...), and we will use parentheses to group a sequence of
statements into a single statement. This begins to look like a
"real" programming language, albeit a very weak one. Here's the
point: this language is equivalent in power to a Turing mach