RAM0

[codedot]

Модель RAM0 (Schönhage's zero-parameter successor RAM model) - это компьютер с двумя регистрами (z и n) и шестью командами (Z, A, L, N, S и C), который эквивалентен SMM (Schönhage's storage modification machine model).

Как следует из названия, команды RAM0, за исключением, пожалуй, условного перехода, не имеют параметров. Одна из ее особенностей - алгоритм умножения n-битных чисел за линейное время O(n). Этот, на первый взгляд, парадоксальный результат говорит о том, что механизм RAM сам по себе обладает определенной вычислительной мощностью.

На языке Си команды RAM0 выглядят следующим образом:

#ifndef _RAM0_H
#define _RAM0_H

#include <stdlib.h>

extern void **n, **z;

#define Z	z = NULL
#define A	++z
#define L	z = *z
#define N	n = z
#define S	*n = z

#define C(label) \
	do { \
		if (z) \
			goto label; \
	} while (0)

#endif

Ниже пример программы:

#include "ram0.h"

void **n, **z;

main()
{
	loop: Z; A; L; N; S; C(loop);

	return !z;
}

Интересно, что система сохраняет Тьюринг-полноту, даже если заменить условный переход безусловным. Эта задача рассматривается в статьях "Blind graph rewriting systems" и "A compact encoding for λ-terms in interaction calculus".