Замятин, задачник по матлогике

а А). Следовательно, А = R(g1 ). Аналогично доказывается, что

А/ = R(g2 ).

Итак, доказано, что всякое рекурсивное множество является рекурсивно перечислимым. Естественно поставить вопрос, справедливо ли обратное? Ответ на этот вопрос содержится в теореме 6.9.

Проведем так называемую “арифметизацию” машин Тьюринга, в результате которой каждая машина М получит в соответствие натуральное число – номер машины М. Как и в § 4, будем считать, что внешний алфавит любой машины есть подмножество множества А = {a0 , a1 , ..., an , ...}, а внутренний алфавит

– подмножество множества Q = {q0 , q1 , ..., qn , ...}. Кроме того, индексы в обозначениях элементов внешнего и внутреннего алфавитов будем записывать в двоичном коде. Поставим в соответствие символам 0, 1, q, a, L, R, →, ; десятичные цифры 0, 1, 2, 3, 4, 5, 6, 7 соответственно. Заменим в записи команд все символы указанными цифрами. Полученную последовательность цифр будем воспринимать как десятичный код некоторого натурального числа – номера команды.

Например, команда q2 a1 → q0 a3 R будет иметь номер 210316203115. Номер команды С будем обозначать через n(C). Если программа машины М состоит из команд С1 , С2 , ..., Сt , то номером n(M) машины М будем называть число n(C1 )7n(C2 )7...7n(Ct), т.е. последовательность цифр, воспринимаемую как десятичный код числа n(M). У машины Тьюринга может быть несколько номеров, поскольку команды машины можно упорядочивать по-разному. Отметим, что существуют натуральные числа, которые не являются номером никакой машины Тьюринга. Таковыми являются, например, числа, имеющие в десятичном разложении цифру 9.

Отметим вначале, что существует машина Тьюринга M0 , которая по единичному коду числа x определяет, является ли x номером какой-нибудь машины Тьюринга. Если x является номером некоторой машины, то M0 печатает на ленте программу этой машины (для этого машине M0 надо “уметь” делить с остатком на 10) и останавливается на самой левой непустой ячейке. Если же x не является номером никакой машины, то M0 печатает на ленте 0 и останавливается в заключительном состоянии.

Теорема 6.9. Существует рекурсивно перечислимое множество, которое не является рекурсивным.

220

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

Докажем рекурсивную перечислимость множества A. Если A = , то A является рекурсивно перечислимым по определению. Пусть A ≠ . Зафиксируем в A некоторый элемент c.

Рассмотрим предикат H(k, l), определяемый следующим образом: H(k, l) = 1 число k является номером некоторой машины K и эта машина, проработав на собственной ленте не более, чем l тактов, останавливается. Предикат H(k, l) всюду определен. Убедимся в том, что он вычислим. Вычисляющая его машина T0 может работать следующим образом. Сначала она работает так же, как машина M0 на слове 1k , т. е. на первом аргументе предиката. Если M0 останавливается и печатает 0 (это означает, что k не является номером никакой машины Тьюринга), то T0 также останавливается и печатает 0. Пусть M0 останавливается и печатает на ленте программу машины K, имеющей номер k. Тогда машина T0 работает так же как универсальная машина U, моделируя выполнение машиной K на собственной программе не более l тактов. Если моделируемая машина K при этом останавливается, то T0 печатает 1 и останавливается. Если же машина K, сделав l тактов, не остановилась, то T0 останавливается и печатает 0.

Предикат H(k, l) будем представлять себе в виде бесконечной таблицы

k			l
	0	1		2
0	H(0, 0)	H(0, 1)		H(0, 2)
1	H(1, 0)	H(1, 1)
2	H(2, 0)

Занумеруем клетки таблицы следующим образом: (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), и т. д.

Рассмотрим теперь еще одну машину Тьюринга, которую будем обозначать буквой T. Машина T начинает работу, имея на ленте слово 1x . Вначале она по данному числу x находит клетку таблицы с номером x. Пусть это будет (k, l). Тогда машина T работает так же, как машина T0 , вычисляющая предикат H(k, l). Если T0 останавливается и печатает 0, то T также останавливается и печатает число c. Если же T0 завершает работу и печатает 1, то T также завершает работу и печатает число x. Из описания машины T видно, что она вычисляет некоторую одноместную

221

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

§7. Многоленточные машины

В многих приложениях часто удобно считать, что машина Тьюринга содержит не одну ленту, а несколько лент, разбитых на ячейки и бесконечных в обе стороны. Как и обычная (одноленточная) машина, многоленточная машина имеет внешний алфавит, в котором выделен пустой символ, и внутренний алфавит (алфавит внутренних состояний). В этом алфавите выделено начальное и заключительное состояния. В ячейках всех лент записаны символы внешнего алфавита (по одному в ячейке), причем в любой момент времени на любой ленте только конечное число ячеек занято непустыми символами. Команда m- ленточной машины есть выражение вида

(q, a1 , a2 , …, am) → (q′, (a1 ′, d1 ), (a2 ′, d2 ), … , (am′, dm)),

где q и q′ – элементы внутреннего алфавита, буквы a с индесами и штрихами – элементы внешнего алфавита, di {L, R, H} для 1 ≤ i ≤ m. Команда выполняется следующим образом. Пусть на начало очередного такта машина находится в состоянии q, на i-той ленте обозревается символ ai . Тогда в результате выполнения команды машина перейдет в состояние q′, в обозреваемую ячейку запишется символ ai ′ и по i-той ленте произойдет сдвиг влево, если di = L, вправо, если di = R, и машина будет обозревать прежнюю ячейку, если di = H. Как и в одноленточном случае, программа – это множество команд с различными левыми частями (левая часть команды – выражение до «стрелки»). Многоленточная машина начинает работу и заканчивает ее так же, как и одноленточная машина.

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

машина

(q, a1, a2, a3) → (r, (b1 , H), (b2 , R), (b3 , L))

будет находиться

в ситуации, изображенной на рис.

6.22.

r

q

b1

a1

b2

a1

a2

b3

a3

Рис. 6.22

Рис. 6.21

222

Для многоленточных машин естественным образом определяется правильная вычислимость функции. Мы не будем полностью приводить это определение. Отметим только, что для вычисления k-местной функции на m-ленточной машине Тьюринга первый аргумент записывается на первой ленте, второй – на второй и т. д. Лента с номером k+1 отводится под значение функции. Машина может содержать еще ленты, т. е. m может быть больше, чем k+1. Эти ленты часто называют рабочими лентами.

Пример. Напишем программу двухленочной машины Тьюринга, вычисляющей функцию y = 2x. Аргумент будет записан на первой ленте в единичном коде, вторая лента пуста. Машина начинает работу, обозревая на первой ленте самую левую единицу (если x ≠ 0; если же x = 0 машина сразу переходит в заключительное состояние). Машина будет считывать аргумент, двигаясь вправо и дублировать его на второй ленте. Найдя на первой ленте первую (справа от аргумента) пустую ячейку, машина по первой ленте будет двигаться влево, затирая единицы и дублируя их на второй ленте. По второй ленте машина, попрежнему, двигается вправо. Найдя на первой ленте первую (слева от аргумента) пустую ячейку, машина остановится в заключительном состоянии q. Приведем список команд такой машины:

(q0 , 1, λ) → (q1 , 1R, 1R), (q0 , λ, λ) → (q, λ, λ),

(q1 , 1, λ) → (q1 , 1R, 1R), (q1 , λ, λ) → (q2 , λL, λ), (q2 , 1, λ) → (q2 , λL, 1R),

(q2 , λ, λ) → (q, λ, λ).

Теорема 6.10. Функция вычислима на одноленточной машине Тьюринга тогда и только тогда, когда она вычислима на многоленточной машине.

Доказательство этого утверждения предоставляется читате-

лю.

§8. Рекурсивные функции

Вернемся к обсуждению понятия алгоритма, проведенному в §1. Там в качестве формального аналога понятия алгоритма было предложено понятие машины Тьюринга. Если дана машина Тьюринга М, на ленте которой записано входное слово w, М находится в начальном внутреннем состоянии и обозревает первую ячейку ленты, то машина М начинает работать или, как еще

223

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

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

Определение. Функции О(x) = 0, s(x) = x+1, In m(x1 , ..., xn ) = xm, где 1≤m≤n, назовем простейшими.

	Введем на F три оператора: суперпозиции, примитивной
рекурсии и минимизации.
	Определение. Функция f(x1 , ..., xn ) называется суперпозици-
ей функций g(x1 ,			..., xk ), h1 (x1 , ..., xn ), ..., hк(x1 , ..., xn ),					если
		f(x1 , ..., xn ) = g(h(x1 , ..., xn ), ..., hk(x1 , ..., xn )).
	Например, функция f(x1 , x2 ) = x1				2	+x1 x2 – суперпозиция функ-
ций g(x1 ,		x2 ) = x1	+x2 , h1 (x1 , x2 ) = x1	2 ,		h2 (x1 ,	x2 ) = x1 x2 ,	поскольку
f(x1 , x2 ) =		g(h1 (x1	, x2 ), h2 (x1 , x2 )). Заметим,				что h1 (x1 ,	x2 ) = h2 (x1 ,
I2	1 (x1 , x2 )). Функция Imn , как мы видим, позволяет вводить фик-

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

Определение. Функция f(x1 , ..., xn , y) получается примитив-

ной рекурсией из g(x1 , ..., xn ) и h(x1 , ..., xn , y, z), если выполня-

ются следующие условия:

1)f(x1 , ..., xn , 0) = g(x1 , ..., xn ),

2)f(x1 , ..., xn , y+1) = h(x1 , ..., xn , y, f(x1 , ..., xn , y)).

Например, функция f(x, y) = x+y получается из функций g(x) = x, h(x, y, z) = z+1 примитивной рекурсией. Действительно, f(x, 0) = x+0 = x = g(x), f(x, y+1) = x+(y+1) = (x+y)+1 = f(x, y)+1 = h(x, y, f(x, y)). Нетрудно показать, что примитивная рекурсия всюду определенных функций будет всюду определена.

Определение. Функция f(x1 , ..., xn ) получается из функций g(x1 , ..., xn ) минимизацией, если f(x1 , ..., xn ) равна наименьшему значению u такому, что

g(x1 , ..., xn - 1 , u) = xn .

Пусть g(x1 , x2 ) = x1 +x2 . Тогда если f(x1 , x2 ) получается из

g(x1 , x2 ) минимизацией, т.е. f(x1 , x2 ) = min{u x1 +u = x2 }, то f(x1 , x2 ) = u = x2 −x1 . Этот пример, в частности показывает, что минимизацией из всюду определенной функции можно получить не всюду определенную.

224

Введем три класса функций.

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

Функция f(x, y) = x+y является примитивно-рекурсивной.

Действительно, f(x, 0) = x = I1 1 (x), f(x, y+1) = f(x, y)+1 = s(f(x, y)). Приведем еще в качестве примеров умножение g(x, y) = xy и

возведение в степень h(x, y) = xy :

g(x, 0) = 0 = 0(x), g(x, y+1) = x(y+1) = x+xy = f(x, g((x, y)) и h(x, 0) = 1 = s(0), h(x, y+1) = xy +1 = xxy = g(x, h(x, y)).

Примитивно-рекурсивными являются также функции m(x, y) = x−y , g(x, y) – частное от деления y на x, r(x, y) – остаток от деления y на x (см., например, упоминавшуюся книгу А.И.Мальцева из списка литературы).

Определение. Функция называется рекурсивной (в другой терминологии частично-рекурсивной), если она получается из простейших с помощью суперпозиции, примитивной рекурсии и минимизации.

Всякая примитивно-рекурсивная функция является рекурсивной. Выше было показано, что разность d(x, y) = y−x получается минимизацией из суммы f(x, y) = x+y. Следовательно, d(x, y) – рекурсивная функция, которая не является примитивнорекурсивной (поскольку не всюду определена).

Определение. Всюду определенные рекурсивные функции называются общерекурсивными.

Поскольку примитивно-рекурсивные функции всюду определены, всякая примитивно-рекурсивная функция является общерекурсивной. Обратное утверждение несправедливо, т.е. существует общерекурсивная функция, которая не является при- митивно-рекурсивной. С доказательством этого утверждения можно познакомиться по книге А.И.Мальцева.

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

225

Теорема 6.11. Класс функций, вычислимых на машинах Тьюринга совпадает с классом рекурсивных функций.

Доказательство теоремы здесь не приводится. Его можно найти в книгах А.И.Мальцева или О.П.Кузнецова и Г.М.Адельсона-Вельского, приведенных в списке литературы.

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

Этот параграф посвящен изложению еще одного варианта формализации понятия алгоритм, который был предложен отечественным математиком А. А. Марковым в конце 1940-х – начале 1950-х годов. Нормальные алгоритмы (или алгорифмы, как называл их автор) являются определенными правилами преобразования слов в некотором алфавите. Дадим необходимые определения.

Определение. Пусть A – некоторый алфавит, α и β – слова над A. Выражения вида

α → β и α → β

называются продукциями. Первая продукция называется про-

стой, вторая – заключительной. Слово α называется левой частью продукции, слово β – правой частью.

Условимся, что запись {x} означает символ x или его отсутствие.

Пусть γ – слово над A. Действие продукции α → { }β на слово γ состоит в следующем. Находится первое вхождение слова α в γ (если такое вхождение имеется) и это вхождение слова α заменяется на слово β. Полученное в результате замены слово называется результатом применения продукции α → { }β

на слово γ. Если γ не содержит подслова α, то говорят, что продукция α → { }β неприменима к слову γ.

Пример 1. В следующей таблице приведены примеры действия продукций на слова.

Исходное слово	Продукция	Результат
таблица	блиц → релк	тарелка
ааваава	ава → с	асава
парта	арт → р	пара
парта	т → ε	пара
та	ε → пар	парта

Определение. Схемой нормального алгоритма называется упорядоченная последовательность продукций.

Определение. Пусть Σ – схема нормального алгоритма.

Нормальным алгоритмом (алгоритмом Маркова) в алфавите A

226

называется следующее правило построения последовательности слов. Пусть γ – слово над A. Полагаем γ0 = γ. Пусть для некоторого i ≥ 0 слово γi уже построено и процесс построения последовательности слов еще не завершился. Рассмотрим два случая:

1)в схеме нет продукций, левые части которых являются

подсловами слова γ. Тогда γi + 1 полагаем равным γi и процесс построения считаем завершившимся.

2)в схеме существуют продукции, левые части которых яв-

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

Если процесс построения завершается, то говорят, что алгоритм применим к слову γ. В этом случае последний член последовательности называется результатом применения алгоритма к слову γ.

Пример 2. Пусть A = {a, b}. Рассмотрим схему

Σ = (ab → ba, b → ε, a → a).

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

Пример 3. Пусть A = {1}. Рассмотрим нормальный алгоритм в алфавите A со следующей схемой:

(11 → ε, 1 → ε, ε → 1).

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

1, если n четно,

f(n) =

ε, если n нечетно.

Здесь натуральное число n представлено в единичном коде.

227

Определение. Пусть A – некоторый алфавит и f: A* → A*. Функция f называется нормально вычислимой, если существует расширение B алфавита и нормальный алгоритм в алфавите B, который каждое слово v из области определения функции f перерабатывает в слово f(v).

Пример 4. Пусть A = {0, 1} и f(x) = x + 1, где аргумент x представлен в двоичном коде. В качестве алфавита B возьмем {0, 1, a, b}. Рассмотрим следующую схему

Σ = (0b → 1, 1b → b0, b → 1,

a0→ 0a, a1 → 1a, 0a → 0b, 1a → 1b, ε → a).

Применим алгоритм с данной схемой к слову x = 10011. Все продукции, кроме последней, к слову x неприменимы, поэтому применяется эта продукция и получается слово a10011. Применение четвертой и пятой продукций приведет к слову 10011a. Теперь применима только предпоследняя продукция, получается слово 10011b. Затем с помощью второй продукции «осуществляется поиск» самого правого нуля. К слову 100b11 применяется первая продукция и алгоритм работу завершает. В итоге имеем равенство f(10011) = 10111.

Пример 5. Составим схему нормального алгоритма, вычисляющего сложение ненулевых чисел в единичном коде. Пусть A

= {1, , a} и

Σ = (a1 → 1a, a → 1a, 1a → ε, ε → a).

Убедимся в том, что нормальный алгоритм с такой схемой слово 1x 1y перерабатывает в слово 1x+ y . Первой применяется последняя продукция схемы, так как к исходному слову первые три продукции неприменимы. Эта продукция в начале слова записывает букву a. Многократное применение первой продукции дает слово 1xa 1y . Затем применяется вторая продукция (поскольку первая неприменима), которая символ заменяет на 1. Применение третьей продукции завершает работу алгоритма.

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

Теорема 6. 12. Функция нормально вычислима тогда и только тогда, когда она вычислима на машине Тьюринга.

Доказывать эту теорему здесь не будем. С доказательством можно ознакомиться по книге [МН].

Кроме машин Тьюринга и Минского, рекурсивных функций и нормальных алгоритмов в литературе описаны и другие модели вычислений: операторные алгоритмы, машины Поста, машины с неограниченными регистрами и т.д. С этими моделями

228

можно познакомиться по книгам А.И.Мальцева или Н. Катленда.

Задачи

1. Программа машины Тьюринга состоит из следующих команд:

q0a→q1 mR, q0 λ→q3 λ, q0b→q2bR,

q1b→q0 bR, q2 m→q1 mL, q2a→q1 bR,

где q0 – начальное, q3 – заключительное состояния, λ – пустой символ;

а) написать четыре последовательных конфигурации, если начальной является конфигурация q0abba;

б) определить, остановится ли машина, начиная работу в конфигурации q0abba;

в) определить, сколько тактов сделает машина до остановки, начиная работу в конфигурации q0baba.

2. По заданной машине Тьюринга М и начальной конфигурации С найти заключительную конфигурацию, если она существует (q0 – начальное, q3 – заключительное состояния):

1)		а	b	λ	m
	q0	q1 mR	q1 mR
	q1	R	λR	q2 L
	q2	L		aL	q3 a

а) C1	= q0 a2baba, б) C2 = q0baλb, в) C3 =q0baλ2 .
2)
			a		b	λ
		q0	q1 λR		q1 λR	R
		q1	q2 λR		q3
		q2	q3		q0 R
а) C1	= q0 a2 ba, б) C2 = q0 ba2 b, в) C3 = a3 b.
3. Написать программу машины Тьюринга, переводящей
конфигурацию С0 в конфигурацию С1 :
а) С0	= q0 anb, C1 = q1 an ban (n≥1);

б) С0 = q0 anbn , C1 = q1 (ab)n (n≥1);

в) C0 = λanq0 bm, C1 = λbmq1 an (m, n≥1), где λ – пустой символ. 4. Нарисовать диаграммы машин Тьюринга из задач 1 и 2.

229