2.1. Вычисления на цепочках

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

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

опознать „предложения" на формальном языке. Мы покажем, что это осуществимо и что, вводя ограничения на понимание языка, мы устанавливаем ограничения на вычислимость функции. Подход, которым мы будем пользоваться, следует подходу Хопкрофта и Ульмана (1969) за исключением того, что их формальные доказательства будут здесь обычно заменяться иллюстрациями и эвристическими соображениями.

Вычислительные машины обычно представляются как совокупность операторов, но их также можно считать устройствами для переписывания цепочек (или строк) символов с одного языка на другой. ЭВМ может читать и печатать только конечные множества знаков. Назовем их соответственно входным алфавитом I и выходным алфавитом и пусть будут множествами всех цепочек конечной длины, составленных из элементов множеств . Любое множество допустимых входов программы и любое множество возможных выходов будут подмножествами в соответственно. Программа вычисляет функцию если она отображает любую цепочку в цепочку

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

Ясно, что Допустим, что в ЭВМ введена программа для счета наибольшего целого, содержащегося в квадрате вещественного числа. Входным языком является символьное представление вещественных чисел, а выходным — символьное представление положительных целых чисел. В более традиционных терминах это означает, что программа реализует функцию, область определения которой — вещественные числа, а множество значений — положительные целые. Эти два описания эквивалентны.

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

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

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

На рис. 2.3 изображена элементарная блок-схемы работы любой мыслимой программы. Программа начинает работать при в состоянии т. е. в своем обычном начальном состоянии. На шаге (1) любое сообщение для выдачи на печать, связанное с поступает на вывод. На шаге (2) ЭВМ останавливается, если ее состояние — состояние останова. Если этого не случилось, то на шаге (3) из входного потока считывается следующий символ х. Шаги (4а) и (4б) отражают работу с динамической памятью. На рисунке показано, во-первых, извлечение цепочки у символов из ячеек в динамической, памяти. Это уже сложнее. Множество ячеек, содержимое которых нужно прочесть в момент определяется как совместная функция от и только что считанного символа х. Пусть у — информация, полученная таким путем. На шаге (46) информация у записывается в ячейки динамической памяти. И у, и — функции от Хотя на рисунке показано, что шаги (4а) и (4б) осуществляются последовательно, на практике операции чтения и записи обычно перемежаются. Заметим, однако, что их можно без потери общности логически разделить. Мы также допускаем ситуацию, в которой — пустые множества; в этом случае не происходит ни чтения, ни записи. И наконец, на шаге (5) состояние

Рис. 2.3. (см. скан) Этапы вычисления функции цепочки символов.

конечной памяти меняется на (функция от увеличивается на 1. Затем цикл начинается снова с шага (1).

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

она проходит, в печатающую машину. Пусть эта запись будет цепочкой

цепочка из Устройство печати может узнать, является ли состояние состоянием печати; в этом случае оно печатает соответствующие выходные символы. Таким образом, это — устройство для отображения цепочек из в цепочки из Ясно, что если ЭВМ отображает входную цепочку в то ЭВМ и устройство печати отображают в Можно сделать и нетривиальное упрощение — объединить шаги (4) и (5), на которых в результате обработки содержимого ячеек и меняется состояние динамической памяти от затем статической памяти от

Рис. 2.4. Упрощение работы программы для того, чтобы печать осуществлялась после вычислений.

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

Это соотношение можно интуитивно интерпретировать так:

Программа, статическая память которой находится в состоянии а динамическая — в состоянии считывает входной символ х и переводит статическую память в состояние и динамическую — в состояние

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

Что можно сказать об этих командах, входящих в процедурную часть? Во-первых, их число должно быть конечным, поскольку сама процедурная часть занимает конечную область в цифровой машине. Во-вторых, они должны производить специфические операции при выполнении некоторого условия, которое цифровое устройство может выявить в течение одного шага. Такое условие должно принадлежать конечному множеству допустимых условий. Этапы работы программы, следовательно, можно записать в форме

однако форма типа левой части в (3) не годится в качестве описания условия А в (4), так как в используется состояние одно из бесконечного множества состояний динамической памяти. Чтобы обойти эту трудность, поставим в соответствие каждому состоянию статической памяти функцию чтения и функцию записи динамической памяти. Функция чтения отображает бесконечное множество комбинаций состояний динамической памяти и входных символов (т. е. множество в конечное множество возможных процессов извлечения информации из динамической памяти. В терминах, использованных при описании рис. 2.3, функция чтения определяет ячейки содержимое которых нужно считать из динамической памяти, а затем после их чтения порождает одну из конечного множества допустимых цепочек у символов. Функция записи берет в качестве своих аргументов входной символ, извлеченную информацию у и текущее состояние динамической памяти и создает новое состояние динамической памяти, определяя ячейки и записывая в них некоторую функцию х и у. Таким образом, каждый шаг программы можно записать в виде

где у — цепочка в (конечном) множестве значений функции — состояние динамической памяти, реализующееся при активации Программа эквивалентна конечному множеству правил в форме (5). Программа выполняется по следующим этапам.

1. Определить, что Если остановиться. В противном случае перейти к шагу 2.

2. Прочесть х и выполнить определяя тем самым у.

3. Просмотреть процедурную часть, чтобы найти правило, левой частью которого является Если такое правило

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

4. Изменить состояние статической памяти на S. Выполнить . Заменить на и вернуться к шагу 1.

Здесь может показаться, что это описание получилось слишком далеким от представлений программиста о программе. На самом же деле функции чтения и записи могут и не быть чем-то необычным. Типичный пример функции реально отображающей бесконечное множество в конечное множество это просто

Аналогично функцией записи может быть

Обычно правила перехода типа (5) программист в явном виде не выписывает 1). Они скорее определяются в результате вывода. Рассмотрим программу на Фортране, выполняемую на машине со словами длиной 32 бита, которая использует логическую ленту 5 для ввода и логическую ленту 10 в качестве участка динамической памяти. Фрагмент программы

вместе со связанным с ним программным счетчиком (который составляет часть статической памяти) определяет возможных правил перехода. Многие из них в конце фрагмента программы дадут один и тот же результат.

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

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

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

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