11.3. Машины произвольного доступа и вычислимые функции

Опишем другую алгоритмическую модель, представляющую собой идеализированную ЭВМ и предложенную в 70-х годах XX века с целью моделирования реальных вычислительных машин и анализа сложности вычислений.

Машина произвольного доступа (МПД) состоит из бесконечного числа регистров R₁, R₂, …, в каждом из которых может быть записано натуральное число из . Пустьесть число, записанное в регистре,.Состоянием машины или конфигурацией назовем последовательность чисел . Функционирование машины заключается в изменении конфигураций путем выполнениякоманд в порядке их написания.

Машина имеет следующие типы команд.

Команды обнуления. Для всякого имеется команда. Действие командызаключается в замене содержимого регистрана 0. Содержимое других регистров не меняется. Обозначение действия

:

:= 0.

Команды прибавления единицы. Для всякого имеется команда. Действие командызаключается в увеличении содержимого регистрана 1. Содержимое других регистров не меняется. Обозначение действия:

:= + 1.

Команды переадресации. Для всех имеется команда. Действие командызаключается в замене содержимого регистрачислом— хранящимся в регистре. Содержимое других регистров не меняется (включая и). Обозначение действия:

:=или .

Команды условного перехода. Для всяких имеется команда. Действие этой команды заключается в:

сравнении содержимого регистров и, затем:

а) если =, то МПД переходит к выполнению команды с номером (идентификатором)q в списке команд;

b) если  , то МПД переходит к выполнению следующей команды в списке команд.

Конечная, упорядоченная последовательность команд данных типов составляет программу МПД.

Пусть зафиксирована начальная конфигурация чисел и программа. Тогда однозначно определена последовательность конфигураций, гдеесть конфигурация, полученная из конфигурацииприменением команды. Пусть на некотором шаге выполнена командаи получена конфигурация. Тогда, еслине есть команда условного перехода, то следующая конфигурацияесть конфигурация, полученная изприменением команды. Еслиесть команда условного перехода, т.е. I_t = J(m, n, q), то получается изприменением команды, если=в конфигурациии команды, если. Последовательность конфигураций будет обозначаться такжеP(a₁, a₂, …) или и называтьсявычислением.

Вычисление (работа машины) останавливается, если:

выполнена последняя команда, т.е. t = s и не есть команда условного перехода;

если I_t = J(m, n, q), =в конфигурациииq > s;

если I_t = J(m, n, q),  в конфигурациииt = s.

Если вычисление остановилось, то последовательность содержимого регистровназываетсязаключительной конфигурацией. Если последовательность конечна, то говорим, что МПД применима к начальной конфигурациии пишемP(a₁, a₂, …) или . В противном случае говорим, что МПД неприменима ки пишемP(a₁, a₂, …) или .

Будем рассматривать только такие начальные конфигурации, в которых имеется конечное число элементов, отличных от нуля. Будем писать вместодля таких конфигураций. Ясно, что любогоt конфигурация будет содержать конечное число отличных от нуля элементов, если этим свойством обладает конфигурация.

Теперь условимся, что понимать под вычислением функций на МПД. Рассмотрим частичные функции f типа . Пусть— фиксированная программа. Пусть. Будем говорить, что вычисление дает результатb, если и в заключительной конфигурации. Обозначение:. Будем говорить, что программаР вычисляет функцию f, если для любых выполнимо

.

Назовем функцию f вычислимой (на МПД), если существует программа Р, которая вычисляет f. Класс вычислимых (на МПД) функций обозначим Е.

Заметим, что любая программа Р для любого n  1 на начальных конфигурациях вида определяетn-местную частичную функцию , такую, что для всех

Ясно, что разные программы могут вычислять одну и ту же функцию.

Распространим понятие алгоритмической вычислимости на предикаты, заданные на множестве . Пусть— произвольный такой предикат. Определим характеристическую функциюпредиката соотношением:

Будем называть предикат  разрешимым, если его характеристическая функция вычислима, и не разрешимым в противном случае.

Это понятие соответствует вопросу о наличии алгоритма для проверки свойства, определяемого предикатом.

Теперь распространим понятие вычислимости на функции, отличные от рассматриваемого типа.

Пусть D — некоторое множество, и — функция отn переменных. Зафиксируем эффективное кодирование множества D натуральными числами , т.е. зададим инъективную функцию. Пусть— ее обратная. Тогда для функцииможно однозначно определить функцию, гдеили

,

для любых .

Будем называть функцию f вычислимой тогда и только тогда, когда функция f^* вычислима.

Пример 11.1. Кодирование множества целых чисел Z. Пусть

Таким образом, можно считать определенным понятие вычислимости целочисленных функций. Позднее будут рассмотрены эффективные кодирования и других областей.

Рассмотрим примеры вычислимых функций (на МПД).

а) Функция f(x, y) = x + y. Эта функция может быть вычислена следующей программой при начальной конфигурации (x, y, 0, 0, …). P = I₁ I₂ I₃ I₄, где I₁ = J(3, 2, 5), I₂ = S(1), I₃ = S(3), I₄ = J(1, 1, 1). Данная программа прибавляет 1 к x до тех пор, пока r₃ не станет равным y.

b) Функция

Эта функция может быть вычислена программой Р = I₁ I₂ I₃ I₄ I₅ I₆, где I₁ = J(1, 2, 6), I₂ = S(3), I₃ = S(2), I₄ = S(2), I₅ = J(1, 1, 1), I₆ = T(3, 1).

Данная программа прибавляет 1 к r₃ и 2 к r₂ до тех пор, пока r₂ не станет равным x, тогда r₃ даст результат.

Поскольку доказательства вычислимости конкретных функций связаны с предъявлением конкретных программ, их вычисляющих, то следует ввести некоторые соглашения о составлении и записи программ. Аналогично композиции машин Тьюринга можно ввести композицию программ МПД.

Пусть . Будем говорить, чтоР имеет стандартный вид, если для всякой команды условного перехода J(m, n, q) выполнимо . Две программыР и назовем эквивалентными, если они определяют одни и те жеn-местные функции, т.е. для всех.

Утверждение 11.2. Для всякой программы Р существует эквивалентная ей программа стандартного вида .

Доказательство. Пусть . Тогда определимгде для любого

.

Ясно, что удовлетворяет нужным требованиям, что требовалось доказать.

Пусть теперь даны две программы P и Q стандартного вида. Образуем программу (где,) с учетом нумерации, т.е. командыJ(m, n, q) заменены на J(m, n, s + q). Тогда результат действия программы PQ совпадает с результатом вычисления по программе P, к которому применена программа Q.

Заметим, что для всякой программы Р существует минимальное натуральное число r(P) такое, что для всех , входящих в команды изР, т.е. S(n), Z(n), T(m, n), J(m, n, q) выполнено m, n < r(P). Это число иногда называют ширина, ранг программы Р.

Смысл числа r(P) состоит в том, что регистры сt > r(P) в ходе вычисления по программе Р не будут менять свое содержание и не будут влиять на содержимое регистров , поэтому их можно использовать для других вычислений.

Заметим также, что можно организовывать вычисление, используя программу Р, в случае, когда входы программы находятся в регистрах , а результат заносится в. Далее для простоты положим, что регистрыотличны от.

Пусть Р вычисляет f в стандартном понимании вычислимости. Тогда программа

будет вычислять и результат запишет в. Данную программу обозначим.

Пример 11.3. Функция f(x, y) = xy — вычислимая функция. Пусть Н — программа, вычисляющая функцию x + y (пример а) ). Тогда вычисляется программой

Программа Р вычисляет xy по правилу

Как следует из изложенного, язык программ МПД содержит основные процедуры языков программирования и позволяет устраивать композицию (соединение) программ и использовать программы в качестве подпрограмм других программ. Это является основанием для предположения о том, что введенный класс вычислимых функций в точности отвечает классу алгоритмически вычислимых функций. Данное предположение называется тезисом Черча (для МПД). Так же как и тезис Тьюринга, данный тезис доказать нельзя, однако принятие его позволяет истолковывать утверждения о несуществовании МПД для решения конкретных задач как утверждения о несуществовании алгоритмов вообще.

Л е к ц и я 12