[Overview] [Previous] [Next]

A Random-Access Machine

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:

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