- •Исчисления высказываний
- •Определение формального исчисления
- •Исчисление высказываний генценовского типа
- •Эквивалентность формул
- •Нормальные формы
- •Семантика исчисления секвенций
- •Исчисление высказываний гильбертовского типа
- •Алгоритмы проверки общезначимости и противоречивости в ив
- •Логика и исчисления предикатов
- •Алгебраические системы. Формулы сигнатуры σ. Истинность формулы на алгебраической системе
- •Секвенциальное исчисление предикатов
- •Эквивалентность формул в
- •Нормальные формы
- •Теорема о существовании модели
- •Исчисление предикатов гильбертовского типа
- •Скулемизация алгебраических систем
- •Метод резолюций в исчислении предикатов
- •Некоторые проблемы аксиоматического исчисления предикатов
- •Разрешимость
- •Непротиворечивость и независимость
- •Полнота в узком смысле
- •Полнота в широком смысле
- •Элементы теории алгоритмов
- •Машины Тьюринга
- •Функции, вычислимые на машинах Тьюринга.
- •Рекурсивные функции и отношения
- •Примитивно рекурсивные функции.
- •Примитивно рекурсивные отношения.
- •Частично рекурсивные функции.
- •Рекурсивно перечислимые отношения
- •Неразрешимость исчисления предикатов. Теорема Геделя о неполноте. Разрешимые и неразрешимые теории.
Машины Тьюринга
Определение и примеры. Машина Тьюринга Τ представляет собой систему, работающую в дискретные моменты времени t = 0,1,2,... и состоящую из следующих частей:
Конечная лента, разбитая на конечное число ячеек. При этом в каждый момент времени t в ячейках записаны буквы из некоторого алфавита А = { } (где а0= 0, а1= 1, m > 1), называемого внешними алфавитом машины. Ячейка, в которой записан символ 0, называется пустой. В процессе работы машины каждая ячейка может менять свое состояние путем замены приписанного к ней символа аi на другой символ . К существующим ячейкам можно пристраивать неограниченное число дополнительных ячеек, которые изначально считаются пустыми. Лента считается направленной, и ее ячейки будут просматриваться слева направо. Таким образом, если в какой-то момент времени лента имеет r ячеек, то состояние ленты полностью описывается словом , где — состояние первой (слева) ячейки, — состояние второй ячейки и т.д.
Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние qj из конечного множества внутренних состоянии Q = {q0, q1,... ,qn} или внутренний алфавит, . Состояние q0 называется заключительным и означает завершение работы машины, а состояние q1 — начальным и означает начало работы машины.
Программа П, т.е. совокупность выражений T(i,j) (где i = 0,...,т, j = 1,...,n), каждое из которых имеет один из следующих видов:
(сдвиг головки, находящейся в состоянии qj напротив ячейки с буквой ai, на одну ячейку влево с заменой состояния qj на qk);
(сдвиг головки, находящейся в состоянии qj напротив ячейки с буквой ai,, на одну ячейку вправо с заменой состояния qj на qk);
(замена буквы ai в текущей ячейке на букву al, также замена состояния qj головки на состояние qk ).
Выражения T(i,j) называются командами. При этом команды не могут начинаться со слов aiq0. Символы L и R не принадлежат множеству AUQ.
Таким образом, машина Тьюринга Τ есть пятерка <A, Q, П, q0, q1>, а работа машины Τ состоит в изменении ее конфигурации К, состоящей из состояния ленты, состояния головки и положения текущей ячейки. Дискретным моментам времени t = 0,1,2,... соответствуют конфигурации К0,К1,К2,--- Конфигурация К0 называется начальной, а конфигурация Kt, содержащая q0, ~ заключительной. Конфигурации будут задаваться в виде машинных слов Μ = , где — состояние ленты, qj — состояние головки, находящейся напротив ячейки с состоянием ai, занимающей то же положение среди других ячеек, что и буква ai в слове .
Опишем преобразование Μ М' машинного слова Μ в машинное слово М' за один шаг работы машины Т.
Пусть команда T(i,j) равна . Если — пустое слово , то М2 = . Если же , то М2 = .
Если T(i,j) — - аналогично.
Если T(i,j) = aiqj —> alqк, полагаем М2 = .
Будем говорить, что машинное слово М' получается из машинного слова Μ с помощью машины Т, и писать Μ =>Т Μ', если существует последовательность преобразований Mi —>Т Mi+1, i = 0,..., к — 1, для которой М0 = М, Мк = М'.
Преобразование Μ =>Т Μ', при котором на каждом переходе Mi —>T Mi+1 не достраиваются ячейки слева, обозначается через Μ Μ'.
Преобразование Μ =>Т Μ', при котором на каждом переходе Mi —>T Mi+1 не достраиваются ячейки ни слева, ни справа, обозначается через Μ | М'. (индекс Т можем опустить).
Зафиксируем алфавит А = {а0, а1 а2, · , аm}· Через будем обозначать слово ai ai ai ...ai алфавита A, состоящее из x букв ai. Приведем список машин, которые будут использоваться в дальнейшем в качестве составляющих для других машин.
А (перенос нуля):
Б+ (сдвиг вправо):
Б- (сдвиг влево):
В (транспозиция):
К (копирование):
Л (стирающая машина):
R (удаление 1): .
S (добавление 1): .
Сложение: . 10. Умножение: .
Приведем примеры программ для машины Сложение
Программу, соответствующую указанной схеме, представим виде следующей таблицы команд, в которой на пересечении строки с символом и столбца с символом , имеется запись команды перехода(для машин Тьюринга данные или транспанированные таблицы часто описывают программы):
|
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
q7 |
q8 |
q9 |
0 |
R q2 |
R q3 |
Lq4 |
Lq5 |
Lq6 (где y=0) |
0q0 |
Lq8 |
1q9 |
0q0 |
1 |
|
Rq2 |
R q3 |
0q4 |
0q7 (где y 0) |
Lq6 |
|
Lq8 |
Lq9 |