11.3. Машины произвольного доступа и вычислимые функции
Опишем другую алгоритмическую модель, представляющую собой идеализированную ЭВМ и предложенную в 70-х годах XX века с целью моделирования реальных вычислительных машин и анализа сложности вычислений.
Машина произвольного доступа (МПД) состоит из бесконечного числа регистров R1, R2, …, в каждом из которых может быть записано натуральное число из . Пусть
есть число, записанное в регистре
,
. Состоянием машины или Конфигурацией назовем последовательность чисел
. Функционирование машины заключается в изменении конфигураций путем выполнения Команд в порядке их написания.
Машина имеет следующие типы команд.
Команды обнуления. Для всякого имеется команда
. Действие команды
заключается в замене содержимого регистра
на 0. Содержимое других регистров не меняется. Обозначение действия
:
:= 0.
Команды прибавления единицы. Для всякого имеется команда
. Действие команды
заключается в увеличении содержимого регистра
на 1. Содержимое других регистров не меняется. Обозначение действия
:
:=
+ 1.
Команды переадресации. Для всех имеется команда
. Действие команды
заключается в замене содержимого регистра
числом
— хранящимся в регистре
. Содержимое других регистров не меняется (включая и
). Обозначение действия
:
:=
или
à
.
Команды условного перехода. Для всяких имеется команда
. Действие этой команды заключается в:
Сравнении содержимого регистров и
, затем:
А) если =
, то МПД переходит к выполнению команды с номером (идентификатором) Q в списке команд;
B) если ¹
, то МПД переходит к выполнению следующей команды в списке команд.
Конечная, упорядоченная последовательность команд данных типов составляет Программу МПД.
Пусть зафиксирована начальная конфигурация чисел и программа
. Тогда однозначно определена последовательность конфигураций
, где
есть конфигурация, полученная из конфигурации
применением команды
. Пусть на некотором шаге выполнена команда
и получена конфигурация
. Тогда, если
не есть команда условного перехода, то следующая конфигурация
есть конфигурация, полученная из
применением команды
. Если
есть команда условного перехода, т. е. IT = J(M, N, Q), то
получается из
применением команды
, если
=
в конфигурации
и команды
, если
¹
. Последовательность конфигураций будет обозначаться также P(A1, A2, …) или
и называться Вычислением.
Вычисление (работа машины) останавливается, если:
Выполнена последняя команда, т. е. T = S И не есть команда условного перехода;
Если IT = J(M, N, Q), =
в конфигурации
и Q > S;
Если IT = J(M, N, Q), ¹
в конфигурации
и T = S.
Если вычисление остановилось, то последовательность содержимого регистров
называется Заключительной конфигурацией. Если последовательность
конечна, то говорим, что МПД применима к начальной конфигурации
и пишем P(A1, A2, …)¯ или
. В противном случае говорим, что МПД неприменима к
и пишем P(A1, A2, …) или
.
Будем рассматривать только такие начальные конфигурации, в которых имеется конечное число элементов, отличных от нуля. Будем писать вместо
для таких конфигураций. Ясно, что любого 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 = I1 I2 I3 I4, где I1 = J(3, 2, 5), I2 = S(1), I3 = S(3), I4 = J(1, 1, 1). Данная программа прибавляет 1 к X до тех пор, пока R3 не станет равным Y.
B) Функция
Эта функция может быть вычислена программой Р = I1 I2 I3 I4 I5 I6, где I1 = J(1, 2, 6), I2 = S(3), I3 = S(2), I4 = S(2), I5 = J(1, 1, 1), I6 = T(3, 1).
Данная программа прибавляет 1 к R3 и 2 к R2 до тех пор, пока R2 не станет равным X, тогда R3 даст результат.
Поскольку доказательства вычислимости конкретных функций связаны с предъявлением конкретных программ, их вычисляющих, то следует ввести некоторые соглашения о составлении и записи программ. Аналогично композиции машин Тьюринга можно ввести композицию программ МПД.
Пусть . Будем говорить, что Р имеет стандартный вид, если для всякой команды условного перехода 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 по правилу
Как следует из изложенного, язык программ МПД содержит основные процедуры языков программирования и позволяет устраивать композицию (соединение) программ и использовать программы в качестве подпрограмм других программ. Это является основанием для предположения о том, что введенный класс вычислимых функций в точности отвечает классу алгоритмически вычислимых функций. Данное предположение называется Тезисом Черча (для МПД). Так же как и тезис Тьюринга, данный тезис доказать нельзя, однако принятие его позволяет истолковывать утверждения о несуществовании МПД для решения конкретных задач как утверждения о несуществовании алгоритмов вообще.
< Предыдущая | Следующая > |
---|