Случайный доступ к машине: Модель вычислений и анализ сложности.

In computer science, random access machine (RAM or RA machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA machine is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. The 'registers' are intuitively equivalent to main memory of a common computer, except for the additional ability of registers to store natural numbers of any size. Like the counter machine, the RA machine contains the execution instructions in the finite state portion of the machine (the so called Harvard architecture). The RA machine's equivalent of the universal Turing machinewith its program in the registers as well as its datais called the random access stored program machine or RASP machine. It is an example of the so called von Neumann architecture and is closest to the common notion of a computer. Together with the Turing machine and counter machine models, the RA machine and RASP machine models are used for computational complexity analysis. Van Emde Boas (1990) calls these three together with the pointer machine, "sequential machine" models, to distinguish them from "parallel random access machine" models.

The concept of a random access machine (RAM) starts with the simplest model of all, the so called counter machine model. Two additions move it away from the counter machine, however. The first enhances the machine with the convenience of indirect addressing; the second moves the model toward the more conventional accumulator based computer with the addition of one or more auxiliary (dedicated) registers, the most common of which is called "the accumulator".

If we eschew the Minsky approach of one monster number in one register, and specify that our machine model will be "like a computer" we have to confront this problem of indirection if we are to compute the recursive functions (also called the μ recursive functions )both total and partial varieties. Our simpler counter machine model can do a "bounded" form of indirectionand thereby compute the sub class of primitive recursive functionsby using a primitive recursive "operator" called "definition by cases" (defined in Kleene (1952) p. 229 and Boolos Burgess Jeffrey p. 74). Such a "bounded indirection" is a laborious, tedious affair. "Definition by cases" requires the machine to determine/distinguish the contents of the pointer register by attempting, time after time until success, to match this contents against a number/name that the case operator explicitly declares. Thus the definition by cases starts from e. g. the lower bound address and continues ad nauseam toward the upper bound address attempting to make a match:
Is the number in register N equal to 0? If not then is it equal to 1? 2? 3? 65364? If not then we're at the last number 65365 and this had better be the one, else we have a problem! "Bounded" indirection will not allow us to compute the partial recursive functionsfor those we need unbounded indirection aka the μ operator. Suppose we had been able to continue on to number 65367, and in fact that register had what we were looking for. Then we could have completed our calculation successfully! But suppose 65367 didn't have what we needed. How far should we continue to go? To be Turing equivalent the counter machine needs to either use the unfortunate single register Minsky Gödel number method, or be augmented with an ability to explore the ends of its register string, ad infinitum if necessary. (A failure to find something "out there" defines what it means for an algorithm to fail to terminate; cf Kleene (1952) pp. 316ff Chapter XII Partial Recursive Functions, in particular p. 323 325.) See more on this in the example below.

The definitional fact that any sort of counter machine without an unbounded register "address" register must specify a register "r" by name indicates that the model requires "r" to be finite, although it is "unbounded" in the sense that the model implies no upper limit to the number of registers necessary to do its job(s). For example, we do not require r < 83,617,563,821,029,283,746 nor r < 2^1,000,001, etc. Thus our model can "expand" the number of registers, if necessary to perform a certain computation. However this does mean that whatever number the model expands to must be finiteit must be indexable with a natural number: ω is not an option. We can escape this restriction by providing an unbounded register to provide the address of the register that specifies an indirect address.