Курсовая работа: Неразрешимость логики первого порядка
Словом в алфавите А или в алфавите Q, или в алфавите A 
Q называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-того шага (или слово в алфавите А, записанное на ленту к началу k-того шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной , если состояние, в котором при этом находится машина, заключительное.
Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.
Будем говорить, что непустое слово б в алфавите А\ {а 0 } = {a 1 , …, a n } воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справа ячейку из тех, в которых записано слово б. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (соответственно в состоянии остановки q 0 ).
Если обработка слова б переводит машину Тьюринга в заключительное состояние, то говорят, что она применима к б , в противном случае – не применима к б (машина работает бесконечно)
Рассмотрим пример:
Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 – символ пустой ячейки), алфавитом внутренних состояний Q = {q 0 , q 1 , q 2 } и со следующей функциональной схемой (программой):
q 1 0 → 1 Л q 2 ;
q 1 1 → 0 Сq 2 ;
q 2 0 → 0 П q 0 ;
q 2 1 → 1 Сq 1 ;
Данную программу можно записать с помощью таблицы
| 0 | 1 | |
| q 1 | 1 Л q 2 | 0 С q 2 |
| q 2 | 0 П q 0 | 1 С q 1 |
Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:
q 1
| … | 1 | 1 | 0 | … |
На первом шаге действует команда: q 1 0 → 1 Л q 2 (управляющее устройство находится в состоянии q 1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q 2), в результате на машине создается следующая конфигурация:
q 2
| … | 1 | 1 | 1 | … |
На втором шаге действует команда: q 2 1 → 1Сq 1 и на машине создается конфигурация:
q 1
| … | 1 | 1 | 1 | … |
Третий шаг обусловлен командой: q 1 1 → 0 Сq 2 . В результате нее создается конфигурация:
q 2
| … | 1 | 0 | 1 | … |
Наконец, после выполнения команды q 2 0 → 0 П q 0 создается конфигурация
q 0
| … | 1 | 0 | 1 | … |
Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q 0 .
Таким образом, исходное слово 110 переработано машиной в слово 101.
Полученную последовательность конфигураций можно записать более коротким способом (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина):
11q 1 0 => 1q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1
Машина Тьюринга – не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита AQ, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.
4. Доказательство неразрешимости проблемы остановки
Проблема остановки машины Тьюринга – это проблема построения такого алгоритма, который мог бы определить закончится или нет вычисление по некоторой задаче. Оказывается, что в общем случае такой алгоритм нельзя построить в принципе, то есть невозможно найти алгоритм, позволяющий по произвольной машине Тьюринга Т и произвольной ее начальной конфигурации q i a j определить придет ли машина Т в заключительное состояние q 0 , если начнет работу в этой конфигурации.
Если машина Т, запущенная в начальной конфигурации q i a j , останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой.
Теорема.