7.Распознающие машины Тьюринга и языки. Проблема распознавания языков

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

a+b

c-d*e

-f

и пр.

Некорректными выражениями, очевидно, являютcя a++b c- или c--- и др. Построим простую машину, которая получая на вход такие выражения, за конечное время определит, является ли выражение корректным или нет. В первом случае машина закончит свою работу в состоянии YES, а во втором – в состоянии NO. Подобные машины называют распознающими. Распознать некоторый объект – значит определить, удовлетворяет ли он определенным условиям или нет. Задача распознавания в общем может быть неразрешимой. Например, нельзя построить распознаватель для выяснения вопроса о существовании рациональных корней произвольного диофантова уравнения, о чем говорилось во введении. Удобно представить правила распознающей машины в форме таблицы.

	буква	Знак + или -	Знак *	Пустой символ
Q0	Q1	Q2	NO	NO
Q1	NO	Q3	Q3	YES
Q2	Q1	NO	NO	NO
Q3	Q1	NO	NO

Рассмотрим пример разбора c-d*e. Первая идет буква, поэтому выполняем переход из Q0 в Q1. Далее переходим в Q3. Затем (для буквы d) переходим в Q1. Затем снова в Q3. Затем в Q1 и YES.

проблема самораспознавания :

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

8.Неразрешимость проблемы самоприменимости

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

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

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

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

Следовательно, Х нельзя сертифицировать, хотя Х способен пройти через лабиринт.

9. Неразрешимость проблемы остановки

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

Нам потребуется следующий простой результат.

УТВЕРЖДЕНИЕ. Ели функция f(x) вычислима, то вычислима и обратная ей функция.

Доказательство. Пусть M_y - правила машины Тьюринга, которая вычисляет f_y(x).

Возьмем какое-нибудь одно из ее правил, например,

Qi   Qj  L

Читаем: если машина находится в состоянии Qi и читает символ , то она переходит в состояние Qj, записывает вместо  символ  и сдвигает ленту влево.

Перепишем это правило 'в обратную сторону"

Qj   Qi  R

Это правило показывает, как работает машина Тьюринга, вычисляющая обратную функцию для данной вычислимой функции. Таким же образом прямо показывается, что любое правило машины Тьюринга можно заменить "обратным", что доказывает УТВЕРЖДЕНИЕ.