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

g2 ( x, y) . Отсюда следует, что g1 (0, 0) = g1 (1, 0) = g1 (0, 1) =

0 и g2 (0, 0)			= g2 (1, 0) =	g2 (0,		1) = 0, поскольку 0 0 = 1 0 =
0 1 =	0	. Далее, так как		1	=	1 1 = g1 (1, 1) g2 (1, 1), имеем
g1 (1,	1)	= 1	или g2 (1, 1)	=	1 .	Это означает, что в качестве

g( x, y) можно взять g1 ( x, y) или g2 ( x, y), что противоречит выбору функции g( x, y) . Следовательно, x y не принадлежит замыканию класса C\ { x y} . Аналогично доказывается, что x y [ C\{ x y}] .

Мы доказали, что { θ( x), ι( x), x y, x y} – базис класса монотонных функций.

1 2 . Указание. См. решение аналогичной задачи в начале §4 . Линейными являются все функции, кроме первой.

1 4 . Приведем решение задачи 14 г. Пусть K = { x+y, x↔( yz)} . В силу теоремы Поста, надо в классе K найти функцию, не сохраняющую 0, функцию, не сохраняющую 1, несамодвойственную, немонотонную, нелинейную функции. Функция x↔( yz) не сохраняет 0, поскольку 0 ↔(0 0) = 1 .

Функция x+y		не	сохраняет 1 . Она			же несамодвойственна
( см. таблицу 5 . 8) и, как уже отмечалось, немонотонна.
						Таблица 5 . 8
	x	y	x +y	¬x +¬y		¬( ¬x +¬y )
	0	0	0	0		1
	0	1	1	1		0
	1	0	1	1		0
	1	1	0	0		1

Докажем, что функция x↔( y z) не линейна. Предполо-

жим, что x↔( y z) = a0 +a1 x+a2 y+a3 z. Составим таблицу, задающую функции из левой и правой части равенства ( см.

таблицу 5 . 9) .

Полученное противоречие показывает, что x↔( y z) – нелинейная функция. ( Разумеется, таблицу можно было бы ограничить первыми четырьмя строками) .

Таблица 5 . 9

x	y	z	a 0 +a 1 x +a 2 y +a 3 z	Следствие
0	0	0	a 0	a 0	= 1
0	0	1	1 +a 3	а3	= 0
0	1	0	1 +a 2	а2	= 0
0	1	1	1	Противоречие
1	0	0
1	0	1
1	1	0

190

1

1

1

1 5 . Указание. Применить теорему Поста. В случаях г), ж), и з) классы будут полными. В остальных случаях – нет.

2 1 . Тупиковыми являются следующие ДНФ:

		f1 = x3 x4 x2 x4 x1 x2 x3 ,
f1		f2 = x3 x4 x2 x4 x1 x3 x4 x1 x2 x4 ,
	− минимальная ДНФ.
	23	. Тупиковыми являются следующие ДНФ:
		f1 = x2 x3 x2 x3 x4 x2 x3 x4 x1x2 x3 ,
		f2 = x2 x3 x2 x3 x4 x2 x3 x4 x1x2 ,
f2	− минимальная ДНФ.
	24	. Тупиковых ДНФ пять, минимальная – одна.
	26	. Указание. В задачах 26.1 – 26.4 воспользоваться тем,

что x ÷ (x ÷ y) = min(x, y).

27. Указание. В задачах 26.1 – 26.4 использовать пример 2 из § 13, в задачах 26.5 – 26.6 – пример 3 из того же параграфа.

191

(a0 x0

Глава 6. Алгоритмы и машины Тьюринга

Основной вопрос, который будет обсуждаться в этой главе

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

a0 xn + a1 xn - 1 + … + an - 1 x + an = 0.

(1)

Число an называется свободным членом уравнения. Нетрудно убедиться в том, что если an ≠ 0 и уравнение (1) имеет целочисленное решение, то решение является делителем свободного члена. Действительно, если x0 – решение уравнения (1), то вы-

полняется числовое равенство

a0 x0 n + a1 x0 n -1 + … + an - 1x0 + an = 0,

которое можно записать так:

n -1 + a1 x0 n- 2 + … + an - 1)x0 = –an.

Мы видим, что левая часть последнего равенства нацело делится на x0 . Следовательно, и правая часть тоже нацело делится на x0 . Очевидно, что если x0 является делителем числа –an , то x0 является делителем числа an . Следовательно, x0 – делитель свободного члена уравнения (1). Решить поставленную выше задачу можно следующим образом. Если an = 0, то уравнение имеет целое решение – число 0. Если an ≠ 0, то надо выписать все делители свободного члена (не забывая и отрицательные) и подстановкой в уравнения убедиться, не являются ли они решениями.

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

192

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

В этой главе нам будет удобно считать, что множество натуральных чисел N содержит 0, т.е. N = {0, 1, 2, …, n, …}.

§1. Понятие машины Тьюринга

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

Развернем понятие алгоритма более подробно, зафиксировав основные требования, предъявляемые к понятию алгоритма.

1. Отметим, прежде всего, что алгоритм применяется к некоторым исходным данным (или входным данным) и служит для получения определенных результатов (или выходных данных).

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

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

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

193

3. Алгоритм состоит из конечного числа элементарных шагов (или правил, или инструкций). Элементарный шаг при формализации “превратится” в команду. Определение команды будет дано ниже.

4. Алгоритм работает детерминировано, тактами. Каждый такт состоит в выполнении элементарного шага (или команды). После выполнения очередного элементарного шага должно быть ясно, какой очередной шаг выполнять (причем только один) или остановиться.

5. К алгоритмам обычно предъявляют требование результативности, т.е. остановки после конечного числа тактов с указанием, что считать результатом алгоритма. Это означает, что если предлагается алгоритм вычисления функции f(x), то желательно убедиться в сходимости этого алгоритма для любого х из области определения f(x). Требование результативности имеет существенное отличие от требований, изложенных в предыдущих пунктах. Дело в том, что выполнимость этого требования в отличие от предыдущих нельзя проверить просмотром описания алгоритма. Метода проверки того, что алгоритм закончит работу на входных данных, как мы увидим ниже, не существует.

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

1)управляющего устройства, которое может находиться в одном из фиксированного множества внутренних состояний Q =

{q1 , q2 , ..., qn };

2)ленты, разбитой на ячейки; в каждой ячейке может быть

записан один символ внешнего алфавита A = {a1 , ..., am}; лента бесконечна в обе стороны; один из символов внешнего алфавита называется пустым; в каждый момент на ленте записано конечное число непустых символов;

3) считывающей и записывающей головки, которая обозре-

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

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

194

Управляющее устройство будем обозначать прямоугольником, в котором записано внутреннее состояние, а обозреваемую ячейку стрелкой так, как это указано на рис. 6.1

			Машина Тьюринга работа-
	q2
			ет, детерминировано, тактами.
			Такт	состоит	в	выполнении
			одной	команды	–	выражения
			вида qiaj → qkaldm,			где dm {L,
a1 a2 a1 a3
			R, H}. Эта команда содержит
Рис. 6.1			условие (левая		часть команды
			до стрелки) и действие (правая

часть команды после стрелки). Команда выполняется следующим образом. Если на начало очередного такта внутреннее состояние машины равно qi , обозреваемый символ есть аj , то после выполнения команды qiaj → qk aldm, т.е. к концу такта, внутреннее состояние становится равным qk , в обозреваемую ячейку записывается символ al , и головка сдвигается на одну ячейку вправо, если dm = R, сдвигается влево, если dm = L, остается на

месте, если dm = H.

Рисунки 6.2 и 6.3 иллюстрируют выполнение двух команд

q2

q2a1 → q3a4R

q3

a1 a2 a1 a3

a1 a2 a4 a3

Рис. 6. 2

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

q2	q2 a2	→ q4 a2 L	q4

a1 a2 a1 a3

a1 a2 a4 a3

Рис.6. 3

Осталось уточнить, как машина начинает работу и как ее заканчивает. Будем считать, что машина начинает работу, обозревая самую левую непустую ячейку и находясь в начальном внутреннем состоянии. С определением того, как машина за-

195

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

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

q1 a→q2 aR, q2 b→q1 bL, q3 λ→q3 λR.

Если машина на начало очередного такта находится в состоянии q1 обозревает ячейку, в которой записан символ а, а в следующей записан символ b, то произойдет зацикливание на участке ленты, содержащем эти символы, и машина будет работать бесконечно. Зацикливание работы машины может произойти еще в одном случае, если машина находится в состоянии q3 , обозревает пустую ячейку (с символом λ) и все следующие ячейки так же пусты, то машина также зацикливается, но уже на бесконечном участке ленты.

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

196

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

Пусть внешний алфавит машины Тьюринга состоит из символов а1 , …, аm, λ, где λ – пустой символ. Предположим, далее,

						что на	начало		некоторого
			qi			такта	возникла		ситуация,
						изображенная на рис.5.4.
						Обратим		внимание, что
						все пусты все ячейки, до
	λ	a1 a2 a4 λ			a3 λ	той, в которой записан
		Рис. 6.		4		символ а1 , и после той, в
						которой		записан символ

а3 . Тогда цепочка с = а1 а2 qi а4 λа3 называется конфигурацией (соответствующей, изобра-женной на рис. 6.4 ситуации). Используя конфигурации, довольно естественно описывать действия команд.

Так если в обсуждаемом случае машина содержит команду qia4 → qj a3 L, то ее выполнение означает переход от конфигурации c к конфигурации c' = a1 qja2 a3 λa3 .

§2. Примеры машин Тьюринга

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

Внутренние состояния машин будем, как правило, нумеровать натуральными числами. Начальное состояние в этом случае будет состоянием с наименьшим номером, заключительное – с

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

Пример 1. Рассмотрим вначале машину Тьюринга, которая складывает два ненулевых натуральных числа, записанных в единичном коде. Эта машина, имея в начальный момент ленту

λ 1 1		1	1	1		1 λ
х единиц				y единиц

перерабатывает ее в ленту

λ	1	1 1 λ
	x+y единиц

и останавливается. Внешний алфавит машины, таким образом, состоит из символов 1, , λ, причем λ – пустой символ.

197

Как будет работать машина? Она, двигаясь вправо, проходит аргумент х, символ заменяет на 1, далее проходит аргумент y до первой пустой ячейки и, возвратившись на ячейку назад “стирает” у аргумента у одну единицу.

Легко понять, что это можно осуществить следующей программой:

q1 1→q1 1R, q1 →q1 1R, q1 λ→q2 λL, q2 1→q3 λ.

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

цей 6.1.

			Таблица 6.1
	1			λ
q1	q1 1R	q1 1R		q2 λL
q2	q3 λ
q3

Таблица читается следующим образом. Если взять строку, обозначенную символом q, и столбец, обозначенный символом а, то в соответствующей клетке записана команда с условием qa. Например, в клетке, расположенной во второй строке и первом столбце таблицы, записано q3 λ. Это означает, что машина Тьюринга содержит команду q2 1 → q3 λ. А команды с условием q2 машина не содержит.

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

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

С учетом этих соглашений таблица 6.1 «превратится» в таблицу

6.2.

			Таблица 6.2
	1			λ
q1	R	R		q2 λL
q2	q3 λ

Рассмотрим на этом же примере еще один способ описания программы машины – описание с помощью диаграмм. Диаграмма представляет собой ориентированный граф с помеченными вершинами и дугами и имеет вид, изображенный на рис. 6.5.

198

	Вершины	диаграммы представляют собой внутренние со-
1→R						стояния. Если машина имеет ко-
						манду qiaj → qkaldm, то от вер-
	q1 →1R
						шины qi к вершине qk проводит-
	λ→L	q2	1→λ		q3	ся дуга, которая помечается вы-
						ражением aj → al dm, если aj ≠ al,
	Рис. 6 . 5					и выражением aj → dm, если aj =
						al . Условимся несколько команд
вида qia1 → qka1			/ d, ..., qiap → qkap/ d изображать одной дугой с
пометкой a1 , ...,ap → a1				/ ,	...,	ap / d (или a1 , ..., ap → d, когда a1 =
a1	/ , ..., ap = ap/ ). Начальное состояние на диаграмме обозначает-

ся “двойным” кружком, а заключительное – “жирным” кружком.

Пример 2. Напишем программу еще одной простой машины Тьюринга – машины, осуществляющей проверку на четность. Перед началом работы на входной ленте записано x единиц (остальные ячейки пусты). Если x четно, то «просмотрев» x, машина должна записать 1, если x нечетно, то записать 0. На стадии просмотра машина будет затирать аргумент, поочередно переходя из состояния q0 (x четно) и q1 (x нечетно). Заключительное состояние – q2 . Программа машины приведена в таблице 6. 2.

		Таблица 6. 2
	1		λ
q0	q1 λR		q2 1
q1	q0 λR		q2 0

Пример 3. Составим диаграмму машины Тьюринга, которая обращает непустое входное слово алфавите {a, b}. Более точно, машина должна начальную конфигурацию q0 w переводить в конфигурацию qwr, где q – заключительное состояние, w – непустое слово в алфавите {a, b}, wr – слово w, записанное в обратном порядке. Назовем такую машину «конвертором». Основная идея работы машины состоит в том, что обращение слова w надо начинать с конца этого слова. Машина будет считывать очередную букву x {a, b}, ставить на ее месте маркер x1 , уходить вправо и в первую пустую ячейку записывать x. Диаграмма машины приведена на рис. 6. 6.

199