Глава 9. Конечные автоматы

Автоматом является устройство, управляющее и кон­тролирующее само себя. Обычный компьютер с програм­мой способен при достаточном запасе энергии контроли­ровать сам себя и, следовательно, является автоматом. Как таковые, компьютеры изучались много лет, однако более естественно рассматривать программу и машину, в которой она содержится, как отдельные компоненты.

Конечно, для выполнения вычислений нам нужна не только программа, но и машина, на которой эти вычис­ления могут выполняться. Однако здесь мы не стремим­ся приступать к детальному изучению теории вычисле­ний, поэтому, за исключением тех случаев, где это необ­ходимо для полноты, мы ограничим наше внимание ма­тематическим описанием некоторых конечных машин.

Несмотря на эти замечания, мы начнем (в § 1) с об­щего введения, которое показывает границы того, что ма­шины могут выполнять. Далее (§ 2) мы изучим матема­тические модели устройств (обычно их малые фрагмен­ты), а затем (в § 3) связанную с этим алгебру.

§ 1. Общие понятия

Все используемые па практике компьютерные устрой­ства ограничены (некоторым образом) количеством ин­формации, которую они могут хранить,— они конечны. Цель данного параграфа — показать, как можно делать утверждения о программах без утомительного рассмот­рения синтаксических деталей; затем мы продемонстри­руем, что даже при отсутствии ограничения па размеры памяти существуют задачи, которые нельзя решить.

1.1. Универсальная машина. Несмотря на использование многочисленных различных типов данных и мно­жеств символов внутри реальных программ, для теорети­ческого изучения достаточно ограничиться рассмотрени­ем программ, которые действуют на множестве V = N {0}, Это равносильно изучению программ, вычисляющих теоретико-числовые функции, которые будут введе­ны в § 2; наша непосредственная задача — описать идеа­лизированный компьютер, позволяющий запоминать эле­менты V, с которыми можно осу­ществлять преобразования, и дать детальное описание того, как могут быть представлены программы для машины.

П редположим, что машина имеет память, состоящую из неограничен­ного числа регистров: R₁, R₂, R₃ и т. д., и что содержание каждого ре­гистра R₁ есть r₁ V. Это можно изобразить так, как это сделано на рис. 9.1.

Для более ясного изложения удобно разрешить использование многих операций, действующих лад регистрами, однако па самом деле необходимы лишь две операции:

R_n R_n+1, R_n R_n–1.

Обозначая содержимое регистра n до операции и после через r_n и r’_n соответственно, можно описать результаты выполнения этих операций следующим образом:

R_n R_n+1 _n= r_n + 1,

R_n R_n–1 _n =

Кроме операций, изменяющих значения регистров па­мяти, необходимо, чтобы машина имела связь с програм­мой для того, чтобы влиять на ее работу. Необходимой в этом случае является только одна операция, а именно та, которая осуществляется сравнение R_n = 0. Однако, как и прежде, мы будем разрешать более общие формы опе­раций такого рода. Результат R_n = 0 справедлив тогда и только тогда, когда = 0, и это условие используется для управления программами. Множество регистров вместе с описанными выше определениями называется машиной с неограниченной памятью (МНГ).

Программы состоят из конечной совокупности опера­ций, занумерованных от 1 до некоторого n N. Мы не будем вдаваться в детали, а выведем-более общие заклю­чения об этих программах. Поэтому не будем давать фор­мального определения такой структуры. Рисунков 9.2 и 9.3 достаточно, чтобы понять, какого рода конструкции допустимы в ней.

Программа на рис. 9.2 не предназначена для выпол­нения особо разумных вычислений, однако она указывает

вид блок-схемы программы для нашей машины. Заме­тим, что все это может быть записано не обязательно в виде рисунка. Например, можно написать:

1: если R₂ = 0 то перейти к 4 иначе перейти к 2

2: R₂ R₂ – 1 (затем перейти к 3)

3: R₁ R₁ + 1 (затем перейти к 4)

4: если R₂ = 0 то перейти к 6 иначе перейти к 5

5: R₃ R₃ – 1 (затем перейти к 2)

6: STOP

На рис. 9.3 представлена более общая форма про­граммы, в которую включены макрокоманды , и про­верки . Это могут быть стандартные команды того ти­па, который уже определен, или же они могут быть пред­ставлены последовательностью основных команд, кото­рым для удобства чтения даны имена (подобно подпро­грамме), детали которых уже где-то определены. Такие последовательности будем называть макропоследователь­ностями.

Сейчас мы можем описать некоторые из этих макро­последовательностей, которые обеспечат связь с после­дующими темами, а также помогут убедить читателя,

Рис. 9.3 Рис. 9.4

что наше небольшое число простых команд на самом де­ле является достаточно мощным средством.

Пример 1.1. может быть реализовано сле­дующим фрагментом программы, где метки х, у и z вы­браны так, чтобы не пересекаться с другими командами в программе:

х: если R_t = 0 то перейти к z иначе перейти к у

у: – 1 (затем перейти к х)

z: ?

В терминах блок-схем этот фрагмент программы изобра­жен на рис. 9.4.

Пример 1.2. Сейчас, определяя макрокоманду, удовлетворяющую предыдущему примеру, и включая в явном виде выражения «go to» («перейти к») только тог­да, когда мы уклоняемся от выполнения команды «go to next instruction» («перейти к следующей команде»), мы можем дать раскрытие формулы m (для некоторого ):

Очередное расширение множества команд требует ис­пользования «рабочей памяти». Мы будем предполагать, что по крайней мере в простейших случаях читатель в состоянии придумать подходящую стратегию работы с памятью, и, следовательно, не будем специально упоми­нать о том, как выбираются эти дополнительные регистры. Случаи, когда количество требуемой памяти неиз­вестно (такие, как стеки и т. п.), будут рассмотрены ниже *).

Пример 1.3. Используя R_k в качестве рабочего ре­гистра, мы можем скопировать содержимое R_j в R_i (R_i R_j). Делая это, мы уничтожаем содержимое R_i, ко­торое в дальнейшем должно быть восстановлено. Следу­ющая программа осуществляет требуемые вычисления:

R_k

х: if = 0 then go to у

R_k R_k + 1

R_j R_j – 1 then go to x

y: R_i

w: if R_k = 0 then go to z

R_i R_i+1

R_j R_j+1

R_k R_k –1 then go to w

z: //

Сейчас мы вернемся к «собственно» арифметическим вычислениям. Сложение и вычитание строятся непосред­ственно, однако, поскольку в регистрах существуют ограничения на значения величин, операция вычитания должна быть несколько модифицирована. Подобным же образом можно выполнить умножение и усеченное де­ление.

Пример 1.4. Сложение R_i R_i + R_k, имеющее ре­зультатом r_i = r_j + r_k, может быть выполнено следую­щим образом:

R_j R_k

х: if R_j = 0 then go to у

R_i R_i + 1

R_j R_j – 1 then go to x

y:

Чтобы получить полную программу в терминах основных команд, мы должны расшифровать макрокоманду «R_j R_k»как это было сделано в примере 1.3. С этого вре­мени мы не будем требовать доказательства таких рас­шифровок.

Подобным образом «ограниченное вычитание» R_i R_j R_k может быть выполнено как

R_j R_k

х: if R_j = 0 then go to у

R_i R_i – 1

R_j R_j – 1 then go to x

y:

Заметим, что если первоначальные значения R_i и R_k бы­ли такие, что r_i < r_k то после r_i итераций операция R_j ← R_j – 1 не будет иметь эффекта.

Аналогично R_i ← R_i * R_k может быть представлено как

R_j 0

R_i R_k

х: if R_j = 0 then go to у

R_i R_i – 1

R_j R_j + R_i then go to x

y: R_i R_j //

В большинстве случаев таким же способом, каким может быть расширено множество операций над регистрами пу­тем определения макрокоманд, можно также ввести ко­манды сравнения, которые на первый взгляд оказывают­ся более сложными, однако в действительности строятся из последовательностей стандартных операций и опера­ций сравнения.

Пример 1.5. Мы можем записать операцию «if R_i > R_k then go to x else go to у» («если R_i > R_k, то перейти к х; иначе перейти к у») следующим образом:

R_j R_i

R_i R_j R_i

if R_j = 0 then go to у else go to x

Этими операциями условного перехода мы можем до­полнить наше множество первоначальных арифметиче­ских операций вместе с операцией деления «R_i R_j R_k, где r_i = 0, если r_k = 0». В нашем случае этой операции соответствует следующий алгоритм:

R_j 0

if R_k = 0 then go to x

y: if R_j < R_k then go to x

R_i R_i + 1

if R_j = R_k then go to x

R_j R_j – R_k then go to y

x: R_i R_i

Из менее общего, но необходимого приложения, ко­торое кратко приведено ниже, следуют две операции, связанные с точностью усечения при делении целых чисел.

Пример 1.6. Если r_i 0, операция «если R_k — де­литель R_i, то перейти к х; иначе перейти к у» действу­ет следующим образом:

if R_k = 0 then go to у

R_j R_i

R_i R_j R_k

R_i R_j R_k

if R_j = R_i then go to x else go to у

При помощи этой (возможно, несколько странной) опе­рации и операции сравнения вида R_i = m (оставленной в качестве упражнения) мы можем проверить, является ли г₍ простым числом.

Ясно, что можно операцию «если R_i простое, то пе­рейти к х; иначе перейти к у» смоделировать следующим образом:

if R_i = 0 then go to у

if R_i = 1 then go to у

R_j R_i –1

z: if R_j = 1 then go to x

if R_i делитель R_j then go to у

R_j R_i –1 then go to z //

Перед последним примером этого параграфа мы дол­жны упомянуть, как в машине вводятся данные и выво­дится результат. Предположим, что мы хотим вычислить значение теоретико-числовой функции f: Vⁿ V^m. Зна­чения m и n известны перед началом выполнения соот­ветствующей программы; поэтому мы можем вначале вы­делить n регистров (в которые должны быть загружены начальные значения перед началом выполнения про­граммы) для входных данных и m регистров (которые не должны быть обязательно отличными от выбранных вна­чале) для выходных данных. Когда программа останав­ливается, мы предполагаем, что некоторый «внешний представитель» может выдать «ответы» из соответствую­щих мест. Это, конечно, разумный путь моделирования потоков данных в программе, поскольку точно показыва­ет взаимодействие операций ввода-вывода. С этими согла­шениями пример 1.7 может рассматриваться или как полная программа (в которой R_i и R_j выбраны как вход­ные и выходные регистры), или как схема для подпро­граммы.

П р и м е р 1.7. Последовательность команд приведен­ных ниже, помещает n-е простое число в R_j где п явля­ется содержимым R_i, предполагается, что п не равно нулю:

(Start)

R_k R_i –1

R_i 2

х: if R_k = 0 then go to у

R_j R_j + 1

z: if R_j простое then go to w

R_i R_j + 1 then go to z

w: R_k R_k — 1 then go to x

у: (stop) //

Сейчас мы объясним наш очевидный интерес к простым числам.

1.2. Кодирование программ. Программы п. 1.1 могли работать с элементами из = N {0}. Мы должны объяс­нить, как в принципе можно любую программу рассмат­ривать в качестве программы такого типа. Это можно сделать, описав способы, при помощи которых различные типы данных могут быть закодированы в элементы из V. Для этого рассматриваем данные предложения над под­ходящими алфавитами и, следовательно, почти как по­стороннее следствие этого процесса получаем также ме­тод для кодирования предложений на языках програм­мирования, а именно сами программы.

Основное математическое средство, используемое для этой цели, это теорема о единственности разложения, из­вестная также как основная теорема арифметики. Эта теорема устанавливает, что произвольный элемент из V является или 0, или 1 либо может быть выражен един­ственным образом как произведение упорядоченных про­стых чисел. Ясно, что если n ∈ V\{0, 1} и

где q₁, ..., q_n, s₁, ..., s_n — все простые числа такие, что

то i = j и s_k = q_k для всех k, 1 k i. Напомним, что простые числа — это элементы из N, которые делятся только на 1 и на самих себя.

Полное доказательство этой теоремы несложно, но его запись существенно отвлекла бы нас от основной за­дачи. Поэтому вместо доказательства мы предлагаем рас­смотреть конструкцию алгоритма (процедуры/програм­мы) для выделения упорядоченных простых множителей q₁,..., q_t для любого данного n. Таким образом, избегая деталей ввода и вывода, мы можем использовать схему, представленную на рис. 9.5.

Предположим теперь, что некоторая программа чита­ет данные, которые состоят из последовательности сим­волов алфавита А = {x, у, z}. Произвольно выбирая по­рядок φ для элементов из А, можно получить φ(1) = x, φ(2) = у, φ(3) = z. Если вводимая последовательность i имеет длину n и выражается как α₁ α₂ … α_n, где α_i ∈ A,тогда существует последовательность

φ ^-1(α₁) φ ^-1(α₂)…φ ^-1(α_n)

над {1, 2, 3}. Взяв первые п простых чисел р₁ ..., р_n, мы можем составить число

назовем его Ф(а). Пусть по соглашению Ф(А) = 1.

Чтобы проиллюстрировать использование этой общей формулы, закодируем строку «хухz» посредством 1, 2, 3

Рис. 9.5

следующим образом: 2¹3²5¹7³«=30870. Используя теоре­му о единственности разложения на простые множители и тот факт, что Ф^-1 является биекцией, имеем, что «хухz» является единственной строкой над А, которая дает это значение. Следовательно, применяя Ф, мы можем «обратить» вычисления, чтобы восстановить строку «хухz».

При помощи этой процедуры все строки над А можно закодировать таким образом, чтобы они имели разные значения в множестве V. Это в силу упорядоченности, индуцируемой Z (поскольку V Z), влечет упорядочен­ность строк из А*. Например, «ху» > «ух».

Необходимо отметить два фактора, связанных с этим методом. Во-первых, поскольку А конечно, в N сущест­вуют значения, которые не являются кодами какой-либо строки в А* (например, не существует α ∈ А* такого, что Ф(α) = 2⁵, так как иначе a ∈ А: φ^-1(5) = а, а такого а не существует). Во-вторых, поскольку элементы А* явля­ются неограниченными, то таковыми являются и коды. (Для любого n ∈ N возьмем простое р_т>п и рассмотрим строку

α = α₁... α_m...α_q

такую, что |α| ≥ m; тогда отсюда следует, что

Используя методику, описанную в § 3 гл. 3, преобразу­ем кодирование Ф так, чтобы получить новое кодирова­ние, которое сохраняет порядок, полученный Ф, но ис­пользует все V. Это один из тех случаев, когда трудно дать арифметическую формулу для вычисления изменен­ных кодов, однако все еще достаточно легко описать спо­соб их получения.

Очевидно, что новое кодирование Ψ с областью значе­ний V задается формулой α |{β: Ф(β) < Ф(α)}|. В частном случае для рассмотренного в примере множе­ства А и его упорядочения φ первые десять значений Ф и Ψ приведены в табл. 9.1.

Таблица 9.1

Чтобы получить эти коды и выполнить процедуры ко­дирования, требуется машина, способная понимать и со­здавать символы вне алфавита D = {0, 1, 2, ..., 8, 9}, на котором определены элементы множества V. Для этого необходимо только устройство, позволяющее имитировать действие φ (и φ^-1), некоторым простым способом воздей­ствуя на таблицу ввода-вывода; остаток процедуры коди­рования, включающий Ф u можно потом учесть при помощи машины с неограниченной памятью.

Следовательно, любой ввод в данную компьютерную систему может рассматриваться как конечная строка (взятая из потенциально бесконечного множества строк над некоторым конечным алфавитом), и если применить описанный выше процесс к соответствующему алфавиту А, то эту строку можно преобразовать в единственный элемент V. Обратная процедура, примененная к получен­ному значению из V, дает значение над другим алфа­витом В.

Следовательно, программа Р: А* → В* похожа на соответствующую программу Р': V → V, где

Р: а → Ф^-1 (Р'(Ф(α))), Р': n → Ф (Р(Ф^-1 (α))),

В еличина используемых значений даже в простых ситуа­циях делает примеры непригодными, однако связанные

Рис. 9.6

диаграммы па рис. 9.6 восстанавливают сущность пропу­щенных этапов.

Переходы, включающие детальную спецификацию Р', являются сложными и не обязательно соответствуют Р «очевидным» образом. Однако если Р вычислимо, то и Р' вычислимо.

Как отмечалось выше, мы можем также применять такие же кодирующие процедуры к программам, и, следо­вательно, расширив Ψ таким образом, чтобы можно было игнорировать семантически неверные программы так же, как и программы, включающие синтаксические ограни­чения, можно перечислить все программы для данной системы, использующей числа из V. Мы предполагаем, что для того, чтобы программа превосходила любое за­данное в V число, к пей можно добавить неограниченное множество кодов, которые содержат произвольно много нулевых утверждений, таких, как R_i ← R_i. Однако в большинстве языков программирования существует мно­го избыточности в синтаксисе; поэтому в лучшем случае мы будем обращать внимание только на лексические зна­ки. Прежде чем пытаться сделать замечания общего ха­рактера, рассмотрим, что можно сделать с простым язы­ком, который использовался ранее в машине с неограни­ченной памятью. Существует четыре типа команд:

х: R_i ← R_i + 1 then go to у

x: R_i ← R_i – 1 then go to у

x: if R_i = 0 then go to у else go to z

x: stop

(Без потери общности мы можем предполагать, что все программы начинаются с команды, помеченной индек­сом 1.) Все, что мы должны знать из команды х,— это, какой тип операции должен выполняться, на каком ре­гистре и какая команда выполняется следующей. Для того чтобы можно было использовать ту же самую схему для всех команд, введем формат

(тип, регистр, правильный выход, неправильный выход). Обозначая команды «останов» («stop»), «больше», «мень­ше» и «равно нулю» через 0, 1, 2 и 3 соответственно, получаем Ф-уровневое кодирование типичных утвержде­ний, как показано ниже:

Ф (R_i – R_i + 1 then go to у) = 2¹3ⁱ5^y7^y

Ф (R_i – R_i – 1 then go to y) = 2²3ⁱ5^y7^y

Ф (if R_i = 0 then go to у else go to z) = 2³3ⁱ5^y7^y

Ф (stop) = 2⁰3⁰5⁰7⁰ = 1.

Поэтому команда Ф содержит всю информацию, необхо­димую для ее выполнения или, если необходимо, для перехода к следующему шагу выполнения программы.

Поскольку все строки в А* конечны, а блок-схема программы для машины с бесконечной памятью сверху не ограничена, то каждая отдельная программа имеет n утверждений, n ∈ N. Тогда можно распространить Ф на программы следующим образом:

где «prog» состоит из n помеченных утверждений, из ко­торых 1-м является s_i.

Из Ф (prog) можно получить Ф(s_i) выделением ком­поненты p_f, и, следовательно, разлагая это- значение на простые сомножители, мы можем узнать детали утверж­дения, помеченного номером i.

Используя подходящую «урезающую» функцию Ψ, мы получаем кодирование, которое является биекцией между ρ, множеством всех программ для машины с бес­конечной памятью и V.

1.3. Проблема останова. Теперь мы можем доказать, что конструкции некоторых общих программ невозмож­ны: не только потому, что мы не находим решения, но и потому, что решение может не существовать. Формаль­ные доказательства ограничим рассмотрением двух ос­новных случаев. Первое из доказательств получим, ис­ходя из начальных принципов, а затем докажем, как второе выводится из первого, иллюстрируя, таким образом, общее использование техники сведения одних задач к другим. После этого сформулируем перечень проблем, относительно которых будет показано, что они неразре­шимы подобным образом.

Строго говоря, все утверждения, приведенные ниже, относятся к программам па машине с бесконечной па­мятью со специальным кодированием функций Ψ₁ и Ψ₂. Однако, задав произвольную «универсальную» машину и подходящий язык программирования, мы в состоянии построить адекватные кодирующие функции, и, следова­тельно, полученные результаты применимы п в общем случае.

Первой задачей, относительно которой мы докажем ее неразрешимость, является задача самоприменимости.

Теорема. Для машины с бесконечной памятью не существует программы, которая для любой заданной программы А при ее кодировании а = Ψ₁ (A) будет оста­навливаться с выходным значением 0, если А (а) оста­навливается (т. е. программа А останавливается, если входное значение равно а), и с выходным значением 1, если А (а) не останавливается.

Доказательство. Будем строить доказательство от противного. Предположим, что такая программа су­ществует; назовем ее В. Итак, В(а) останавливается с результатом, равным 0, если а приводит программу А к останову, и с результатом, равным 1, если а не приводит к останову А.

И зменим программу В следующим об­разом. Заменим команду останова услов­ной петлей, так что, если выходной ре­гистр имеет значение 0, мы обходим эту команду; в противном случае — останов. Назовем эту программу С (рис. 9.7). Име­ем следующее: С (х) останавливается (и имеет то же самое выходное значение, что и В(х)) тогда и только тогда, когда выходное значение равно 1.

Рассматривая С при входном значении с = Ψ(С), получаем противоречие: так С(с) останавливается тогда и только тогда, когда С(с) = В(с)= 1, то В(с)= 1 тогда и только тогда, когда С(с) не останавливается. От­сюда следует, что С не может существовать, а поэтому и В не существует. //

Предыдущее доказательство по стилю подобно тому, которое использовалось, чтобы опровергнуть существова­ние множества Рассела в примере 1.1 гл. 1. Кажется, что оно носит тривиальный характер, однако, подобно многим другим кратким математическим рассуждениям, является достаточно тонким. Следует на это обратить внимание перед тем, как использовать этот факт при доказательст­ве более общего результата — неразрешимости проблемы останова.

Теорема. Для машины с бесконечной памятью не существует программы, которая по произвольным входным данным, представляющим программу и ее данные, будет определять, останавливается программа на этих данных или нет.

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

Очевидно, что программа требует ввода двух сортов данных: a(=Ψ₁(A))—кода программы А и x(=Ψ₂(X)), где X—входные данные для А. Это может быть закоди­ровано обычным путем — с использованием двух различ­ных простых чисел р и q. Пусть входные данные будут p^aq^x, и предположим, что существует программа для ре­шения нашей задачи; назовем ее В. Тогда B(p^aq^x) оста­навливается с результатом 1, если А(Х) останавливается, и останавливается с результатом 0, если А(Х) не оста­навливается. В этом случае из В можно создать новую программу С, добавляя к началу В последовательность команд, которые превращают содержимое i-го входного элемента в (pq)^t. Тогда

Следовательно, С решает проблему самоприменимости, о которой мы знаем, что она неразрешима. Следовательно, С не существует, а поэтому не существует и В. //

Проблема останова является классическим результа­том о неразрешимости в теории компьютеров. Приведен­ное здесь доказательство использует общую технику све­дения одной задачи к другой. Далее показывается, что первая задача неразрешима, поскольку если бы это было не так, то была бы разрешима и другая задача, о которой известно, что она неразрешима.

Используя этот принцип (и соответствующие конст­рукции, детали которых здесь опускаются), можно пока­зать, что многие другие проблемы также неразрешимы. В частности, неразрешимы следующие проблемы:

а) останавливается или нет произвольная программа, если входное значение равно 0;

б) останавливается или нет произвольная программа при любых входных данных;

в) выполнено ли равенство L(G)= для произволь­ной контекстно-зависимой грамматики G;

г) выполнено ли равенство L(G₁) L(G₂) = , где G₁ и G₂ — произвольные контекстно-свободные грам­матики;

д) выполнено ли равенство L(G)=T*, где G = (N, Т, Р, S)-— произвольная контекстно-свободная грамматика;

е) выполнено ли равенство L(G₁) = L(G₂), где G₁ и G₂ — произвольные контекстно-свободные грамматики;

ж) является ли произвольная контекстно-свободная грамматика неоднозначной.

1.4. «Расширенная» машина. Насколько реалистичной является машина с бесконечной памятью в качестве мо­дели компьютера? Память такой машины, очевидно, пре­восходит память любой существующей машины, которая подвергается ограничениям как на число регистров, так и на значения, которые могут содержаться в каждом ре­гистре. Однако эта идеализация в пределах машины с неограниченной памятью расширяет, а не ограничивает возможности машины. Существуют ли аспекты в компью­терных системах, которые не могут быть смоделированы на машине с неограниченной памятью?

Мы утверждаем, что нет. Хотя формально мы не мо­жем доказать это высказывание, остановимся на основных моментах такой «расширенной» машины, которая может моделировать все нужные свойства, хотя в качестве аб­страктной модели она применяется редко.

Нас будут интересовать следующие свойства:

а) большой набор операций;

б) более широкий набор внешних типов данных;

в) массивы;

г) стеки;

д) более сильные команды управления;

е) общий механизм управления;

ж) рекурсия.

В пп. 1.1 и 1.2 мы показали, как в случае а) можно добавить арифметические операции к множеству команд, а в случае б), добавляя простые периферийные устрой­ства (для того чтобы иметь возможность работать с сим­волами, которых пет в машине с неограниченной па­мятью), можно расширить диапазон представлений входных и выходных данных над произвольным алфа­витом.

Остановимся па работе с массивами. Предположим, что нам необходим массив с десятью компонентами А [1], ... ,А [10] и что содержимое этих регистров суть a₁, ..., a₁₀. С помощью методики, которая уже использовалась, мы можем сохранить эти значения, вводя величину

Рис. 9.8

которую затем можно запомнить в одном регистре. Мы уже описывали процедуру выделения каждого а₁ из а. Этот метод не зависит от границы массива и поэтому переносится на случай работы со стеками. В стеках мож­но хранить результаты промежуточных вычислений, не требуя существенно больше регистров. С помощью подхо­дящего механизма управления (см. ниже) мы можем так­же поместить в стек адреса возврата из подпрограмм. Любая программа на машине с неограниченной па­мятью конечна, и строки программы могут быть прону­мерованы (помечены) числами от 1 до n, n ∈ N. В контек­сте блок-схемы программы мы можем сконструировать в случав е) «вычисление goto», используя таб­личную технику, дан­ную выше, для того, что­бы получить «goto(R_k)», как указано на рис. 9.8. Используя схему

прямого кодирования для программ Ф (а не Ψ), мы можем закоди­ровать всю программу одним значением, кото­рое запоминается в ре­гистре. Разложение на простые множители за­тем может использо­ваться для выделения кода «следующего ут­верждения». Это моде­лирует свойство ж), а вместе с использованием стеков

Р ис. 9.8

дает возможность ре­курсии з). Следовательно, используя машину с неограниченной памятью, можно произвести «расширение» путем добав­ления этих свойств. Однако в действительности такие расширения носят лишь внешний характер, а результи­рующая система может быть смоделирована с использо­ванием другой машины с неограниченной памятью, у ко­торой блок-схема программы состоит из простых команд увеличения, уменьшения и «равенства пулю».

Упражнение 9.1.

1. Построить на машине с неограниченной памятью блок-схему программы, осуществляющей проверку «R₁ = m».

2. Спроектировать машину с неограниченной памятью, которая, если дана программа, закодированная в До, бу­дет выполнять эту программу. (За основу взять кодирую­щую схему из п. 1.2.)