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

Опишем другую алгоритмическую модель, представляющую собой идеализированную ЭВМ и предложенную в 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-местную частичную функцию , такую, что для всех

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

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

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

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

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

Пусть 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