ВАРИАНТЫ МАШИН И АЛГОРИТМОВ ТЬЮРИНГА - ПОСТА

В этой главе будет изучено несколько классов алгоритмов, ОТЛИЧНЫХ от класса алгоритмов, выполняемых машинами Тьюринга, по довольно близких к последнему. В § 14 рассматриваются нормальные алгоритмы, операторные алгоритмы и так называемые продукции Поста, а в § 15 - многоленточные машины Тьюринга, двухлен-точные машины с неизменяющимися состояниями ячеек (машины Минского) и продукции Поста специального вида, известные под именем ТАГ-систем. Указанные классы алгоритмов наиболее часто встречаются в теоретических приложениях, если не считать алгоритмов, осуществляемых конечными автоматами, которые в данной книге не рассматриваются и составляют предмет особой области - теории конечных автоматов.

§ 14. Нормальные н операторные алгоритмы

Каждое мгновенное состояние машины Тьюринга естественно описывается либо машинным словом, либо натуральным числом - номером машинного слова. В силу этих описаний переходу машины Тьюринга из одного состояния в другое отвечает либо определенное преобразование машинного слова, либо соответствующая операция над числом. Анализ преобразований слов непосредственно приводит к понятию алгоритма, заданного программой подстановок, описанному выше вн. 12.1, и к понятию нормального алгоритма, введенному А. А. Марко-в ы м [2]. Анализ операций над номерами машинных слов непосредственно приводит к понятию операторного алгоритма Ван X а о [1]. Изложению всех этих понятий мы предпошлем несколько замечаний о еще более общем по-нятпи формальной системы или формального исчисления, играющем важную роль в логике и других разделах математики.

относительно h, . . fs, принадлежит тому же классу (К л п н и

29. Характеристическая функция любого предиката класса В, рекурсивна относительно характеристических функции подходящих предикатов, имеюпщх классы Pj и соответственно Qs-

30 Пусть 21 - замкнутая формула исчисления предикатов 1-й ступени, истинная на некоторой модели с бесконечным числом элементов и содержащая помимо логических знаков (включая знак равенства) еще лишь предикатные символы Ау, Ащ. 1огда на натуральном ряде N существуют такие предикаты А, . . ., А° класса Ва, что формула 21 истинна на модели <2V; 4?, . . ., АУ (Клини [3] с. 349).

31. Существуют удовлетворяюшде условиям предыдущей задачи формулы 21, которые ложны на любой модели <N; Л, . . . : . ., а1>, предикаты которой А, . . ., принадлежат классу PjU □ Q, (Мостовский [1]).

14.1. Формальные системы. Продукции Поста. Формальная система задается своим алфавитом С = /{с, Са,. . . , Ср} и конелной совокупностью «правил вывода» Рх, Ра, • • , Ps- При этом правилом вывода Р (;г-местным) в алфавите С называется просто произвольная рекурсивная совокупность ;г-ок (у, слов в алфавите С Совокупность Р обычно задают каким-нибудь «простым» правилом, нозволяюш;им узнать, обладает произвольно взятая гг-ка слов заданным признаком Р или нет.

Слово 5 называется непосредственным следствием из некоторой совокупности слов 31, символически 51 = 5, если возможно указать такое правило вывода Р; и такие слова «1, . . ., am в совокупности 3t, что последовательность <ai, . . ., йт, 5> принадлежит Р.

Слово J называется следствием из совокупности слов 9(, символически 3( - f, если можно указать такую конечную последовательность слов 5, . . ., 5, что

5t \= ?1, {%, 11} \=2.....{% ?1, ..h) \= f.

Дополнительно полагают, что каждое слово есть непосредственное следствие самого себя. Таким образом, если 5 е 3t, то 5( з 5.

Вместо «j есть следствие из совокупности %> говорят также, что f выводимо изЗ( (в данной формальной системе).

Из определения формальной выводимости непосредственно вытекают следующие ее свойства:

а) Если 5f 5 U 91 аз, то 58 [-

б) Если % [- ;е и {%, } [- t), то % \~ Г>.

в) Если слово 5 выводимо из некоторой бесконечной совокупности Ш слов, то 5 выводимо из некоторой конечной подсовокупности совокупности 2f.

Примерами формальных систем могут служить ассоциативные исчисления, рассмотренные в п. 13.1. Пусть - ассоциативное исчисление с алфавитом С и определяющими соотношениями йг Ь; (г = 1, 2, . . ., I). Каждому соотношению йг = Ьг ставим в соответствие два бинарных правила вывода Pi и Pi, полагая Pj (у, f) истинным, если слово t) может быть полено из f подстановкой в f слова bi вместо какого-нибудь вхождения й, и определяя аналогично Р\ Xj). Ясно, что в формальной системе % с алфавитом С и правилами вывода Р, Pi (i = 1, 2, . . . . . , Z) 5 - 9 тогда и только тогда, когда f = 5 в заданном ассоциативном исчислении.

Пусть % - некоторая совокупность слов формальной системы %. Формальным доказательством на основе % называется каждая конечная цепочка <го, fi, . . ., 5<> слов из 5", обладающая следующим свойством:

для каждого f, О < i.< или ?г б 3t или

{?0, 11, . . . , li-i}

Последнее слово Xt формального доказательства называется его утверждением, а все формальное доказательство <Го, 11, . . ., j> называется формальным- выводом t из о на основе Ч.

Теорема 1. Пусть % - какая-нибудь формальная система и % - некоторое рекурсивно перечислимое множество слов в Тогда совокупность всех формальных доказательств в на основе 9( также рекурсивно перечислима.

Номером произвольной п-ки слов <i, . . ., назовем канторовский номер числовой последовательности <с (fl), . . ., с („), п - 1>, где с (li) - алфавитный номер слова li. Пусть а (тп) - последовательность слов, имеющая номер т. По условию, существует примитивно рекурсивная функция ф {х) такая, что ф (0), ф (1), . . . суть алфавитные номера всех слов из 31. Для каждой конечной последовательности слов <о, ii, . . t> мы можем решить вопрос о том, является ли она доказательством на основе совокупности % слов с номерами ф (0), ф (1), . . . . . . ., ф(и). Теперь строим последовательность доказательств а (uoo), ос (uio), . . . посредством следующего процесса.

а) Полагаем uoo равным номеру доказательства <й, а>, где й - слово с номером ф (0).

б) Пусть доказательства

ос(г/оо),ос (uio), . . ., а{щр), . . ., а {щ),. . . , а (Щр) (1)

построены. Из последовательности цепочек слов а (0), а (1), . . ., а {t -г 1) выбираем те, которые являются доказательствами на основе совокупностц 3( слов с номерами ф (0), ф (1), . . ., ф (i -Ь 1). Пусть это будут доказательства а (uui о), • • •> сб {ui+i р). Их мы и присоединяем к доказательствам (1).

Ясно, что так построенная последовате.чьность доказательств содержит все доказательства на основе 3(. Члены этой последовательности строятся на основе ясно-

ГО алгоритма и потому совокупность всех ее членов рекурсивно перечислима.

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

Действительно, согласно теореме 1 совокупность всех доказательств на основе % рекурсивно перечислима. Но тогда рекурсивно перечислимыми являются совокупность всех доказательств, начальные слова которых находятся в 9{, и нужная иам совокупность всех последних слов доказательств, начинающихся словом из %.

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

Система тдстиновок (= подстановочная система) задается некоторым алфавитом С = {су,С2, , Ср} и базисными подстановками

abiii = 1, . . .,1), (2)

где aj, Ь; - некоторые (возможно и пустые) слова в алфавите С. Каждую подстановку «j -v bi из (2) будем понимать как правило вывода Р, считая, что (р, t)) истинно, если слово 9 получаются из слова у посредством подстановки в 5 слова bi вместо какого-нибудь вхождения слова й;.

Отсюда непосредственно видно, что ассоциатпвное исчисление с алфавитом С и определяющими соотношениями

«г = Ьг (i = 1, . . ., I)

можно рассматривать как спстему подстановок с базисными подстановками

Таким образом, система подстановок (2) содержит как бы лишь «половину» подстановок, содержащихся в ассоциативном исчислении с соответствующими определяющими соотношениями.

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

ных исчислениях. Это и дало повод системы подстановок называть полусистемами Туэ или даже «системами полу-Туэ».

Пусть © - система подстановок с алфавитом С и базисными подстановками (2). Слово ав алфавитеС называется заключительным в системе ©, если ни одно из левых слов Й1, . . ., й; подстановок (2) не входит в а. Говорят, что система (2) перерабатывает слово р в слово tj, если f j- J) и слово J) заключительное. Может случиться, что для каждого слова f из некоторого, рекурсивного множества ?9J существует не более одного заключительного слова Г), удовлетворяющего соотношению 5 [- t). Тогда, ставя слову 5 в соответствие слово t), получим частичную функцию на Ш, которая называется функцией, вычисляемой системой @. Поскольку множество пар слов i)>, удовлетворяющих соотношению р - t), рекурсивно перечислимо, а множество всех заключительных слов рекурсивно, то упомянутая функция заведомо частично рекурсивна. Программа подстановок, отвечающая машине Тьюринга, показывает, что при надлежащем кодировании чисел при помощи систем подстановок можно вычислить любую частично рекурсивную функцию.

Система продукций Поста задается своим алфавитом С = {су, . . ., Ср} и системой базисных продукций

aiWWbi{i = i, . . .,1), (3)

где а,, bi - какие-то слова в алфавите С. Пусть некоторое слово 5 начинается словом й;. Произвести над 5 продукцию atWWbi - это значит вычеркнуть из f начальный отрезок й; и затем к оставщемуся слову ирипи-сать справа слово bj. Например, произведя над словом aba продукцию abW Wc, получим слово ас.

Каждая система продукций (3) обычно понимается как формальная система с правилами вывода (i = 1, . . . . . . , I), где Pi (5, t)) считается истинным, если слово t) получается из f прп помощп продукции uiW Wbi-

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

Теорема 2. Пусть задана система подстановок © с базисными подстановками (2) и алфавитом С = {су, . . . . . ., Ср}. Рассмотрим новый алфавит D = {су, . . ., Ср, Ci, . . ., Ср}. Пусть а обозначает слово, получающееся из слова ц в С за,ченой всех его букв соответствующи.ми