82. Дядя(X, y)   род(z, y)  брат(X, z).

Добавим в множество предложений отрицание проверяемого утверждения

83.  дядя(cергей, Y)

и будем применять к предложениям множества правило резолюции.

дядя(сергей, Y)   род(Z, Y)  брат(сергей, Z)  род(Z, Y)  брат(сергей, Z) брат(сергей, Z)  род(W, сергей)  род(W, Z)  муж(сергей) брат(сергей, Z)  род(W, сергей)  род(W, Z) род(иван, сергей)  отец(иван, сергей) род(иван, сергей) брат(сергей, Z)  род(иван, сергей)   род(иван, Z) брат(сергей, Z)  род(иван, Z) род(иван, ольга)  отец(иван, ольга) род(иван, ольга) брат(сергей, ольга)  род(иван, ольга) брат(сергей, ольга)  род(ольга, Y)  брат(сергей, ольга)  род(ольга, Y) род(ольга, павел)  мать(ольга,павел) род(ольга, павел)  род(ольга, павел) 

X=сергей (82) R (83, 84) X=сергей, Y=Z, Z=W (80) R (86, 4) X=иван, Y=сергей (76) R (88, 38) W=иван (87) R (89, 90) X=иван, Y=ольга (76) R (92, 37) Z=ольга (91) R (93, 94) Z=ольга (87) R (95, 96) X=ольга, Y=павел (77) R (98, 68) Y=павел (97) R (99, 100)

Таким образом, предложение дядя(cергей, Y) выводимо из заданного множества предложений при Y=павел.

4. Формальные определения алгоритма

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

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

2. читающей/пишущей головки;

3. управляющего устройства с конечным числом состояний.

Программу для ДМТ определяют следующие компоненты:

1.  – конечное множество символов, записываемых на ленте, – множество входных символов,– выделенный пустой символ;

2. Q – конечное множество состояний, в котором выделено начальное состояние и два конечных –;

3. функция переходов .

Т.е. .

Задание 1. Построить ДМТ-программу, которая копирует на ленте заданное натуральное число.

Решение. Как задача распознавания эта задача звучит следующим образом: существует ли копия заданного натурального числа.

Для представления натурального числа будем использовать символ 1, при такой схеме кодирования число n записывается в виде последовательности из n единиц. Для разделения исходного числа и копии используем символ *, в качестве вспомогательного символа выберем 0. Таким образом, ,.

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

Копирование числа n будем выполнять за n проходов с возвратом. На каждом проходе заменим первую нескопированную единицу на вспомогательный символ 0, затем, двигаясь вправо, дойдём до конца записи, повторяя все символы, стоящие перед пустым, и запишем 1 в конец записи. Во время первого прохода перед записью 1 нужно вставить разделительный символ *. Затем будем двигаться влево, также повторяя символы, до тех пор, пока не достигнем 0, после чего действия повторяются. Когда все единицы будут скопированы (после символа 0 стоит *), нужно восстановить исходное число, заменив все 0 на 1, двигаясь влево.

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

Следовательно, .

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

q	s
	0	1	*	b
q0	(qN, b, 1)	(q1, 0, 1)	(qN, b, 1)	(qN, b, 1)
q1	(qN, b, 1)	(q1, 1, 1)	(qN, b, 1)	(q2, *, 1)
q2	–	–	–	(q3, 1, -1)
q3	(q4, 0, 1)	(q3, 1, -1)	(q3, *, -1)	–
q4	–	(q5, 0, 1)	(q6, *, -1)	–
q5	–	(q5, 1, 1)	(q5, *, 1)	(q3, 1, -1)
q6	(q6, 1, -1)	–	–	(qY, b, 1)

Второй подход основан на понятии вычисления и числовой функции, основная теоретическая модель этого вида – рекурсивные функции.

Работу ДМТ-программы можно рассматривать, как вычисление некоторой функции. Если словои программаостанавливается на любом входе из^*, то результатом вычисления будет слово, составленное из символов, записанных на ленте после остановки машины в ячейках с 1-ой по последнюю непустую ячейку.

Классом функций, для которых вычисляющий их алгоритм существует, являются частично-рекурсивные функции.

Функция называется частично рекурсивной, если она может быть построена из 0, функций ис помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и-оператора.

Задание 2. Доказать примитивную рекурсивность следующих функций:

1. ;

2. ;

3. ;

4. ;

5. .

Решение.