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>; <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 machine. (You can prove this by using the language to implement a Turing machine, then using a Turing machine to emulate the language.)

In other words: this language is powerful enough to compute anything that can be
computed in *any* programming language.