- •1. Исчисление высказываний
- •1.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2. Метод резолюций в исчислении высказываний
- •1.3. Метод резолюций для хорновских дизъюнктов
- •Задачи и упражнения
- •2. Логика и исчисление предикатов
- •2.1. Логика предикатов
- •2.2. Алгебра предикатов
- •2.2.1. Логические операции
- •2.2.2. Правила записи сложных формул
- •2.2.3. Законы алгебры предикатов
- •2.2.4. Предваренная нормальная форма
- •2.2.4.1. Алгоритм приведения формулы к виду пнф
- •2.2.5. Сколемовская стандартная форма
- •2.2.5.1. Алгоритм Сколема
- •2.3. Исчисление предикатов
- •2.3.1. Интерпретация формул
- •2.3.2. Правила вывода
- •2.3.3. Метод дедуктивного вывода
- •2.3.4. Метод резолюций в исчислении предикатов
- •2.4. Проблемы в исчислении предикатов
- •2.5. Логическое программирование
- •Задачи и упражнения
- •3. Элементы теории алгоритмов
- •3.1. Рекурсивные функции
- •3.1.1. Базовые функции
- •3.1.2. Элементарные операции
- •3.2. Машина Тьюринга
- •3.2.1. Описание машины Тьюринга
- •3.2.2. Примеры машин Тьюринга
- •3.2.3. Условные обозначения и схемные соединения машин Тьюринга
- •3.2.4. Рекурсивные функции и вычисления на машинах Тьюринга
- •3.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
3.2.2. Примеры машин Тьюринга
Рассмотрим машины Тьюринга, реализующие и обеспечивающие формирование рекурсивных функций.
Пример 1. Машина Тьюринга, реализующая базовую функцию константа Сn = 0 на правой полуленте (табл. 5)
T1 : qí | x + 1 qk |
Протокол T1:
1) qí | q1 # Ï;
2) q1 | q1 # Ï;
3) q1 # q2 # Ë;
4) q2 # qk # Ñ.
dk
Таблица 5
Текущее |
Символы vt |
|
состояние |
1 |
# |
qí |
q1 # Ï |
— |
q1 |
q1 # Ï |
q1 # Ë |
q2 |
— |
q1 # C |
Пусть х = 3. Тогда f (3) = C1 (3) = 0 будет получена на машине Тьюринга следующим образом:
x+1
# | | | | # # # | | | # # # # | |# # # # # | #
q2 q1 q1 q1
# # # # # # # # # # | #
q2 qk
Пример 2. Машина Тьюринга, реализующая базовую функцию константа Сn = 1 на правой полуленте (табл. 6):
T2 : qí | x+1 qk |2
Протокол T2:
1) qí | q1 # Ï;
2) q1 | q1 # Ï;
3) q1 # q2 | Л;
4) q2 # qk | C.
Таблица 6
Текущее |
Символы vt |
|
состояние |
| |
# |
qí |
q1 # Ï |
qí # Ï |
q1 |
q1 # Ï |
q2 # Ë |
q2 |
— |
q1 | C |
Пусть х = 3. Тогда f (3) = C1 (3) = 1 будет получена на машине Тьюринга следующим образом:
x+1
# | | | | # # # | | | # # # # | |# # # # # | #
qí q1 q1 q1
# # # # # # # # # # | # # # # # | |
q1 q2 qk
Пример 3. Машина Тьюринга, реализующая базовую функцию следования (х) = х + 1 на правой полуленте (табл. 7):
T3 : qí | x+1 qk |(õ+1)+1
Протокол T3:
1) qí | q1 | Ï;
2) q1 | q1 | Ï;
3) q1 # q2 | Л;
4) q2 # q2 | Ë.
5) q2 # q3 # Ï;
6) q3 | qk | C;
Таблица 7
Текущее |
Символы vt |
|
состояние |
| |
# |
qí |
q1 | Ï |
- |
q1 |
q1 | Ï |
q2 | Ë |
q2 |
q2 | Ë |
q3 # Ï |
q3 |
qk | C |
- |
Пусть х = 3. Тогда f (3) = (3) = 3+1 будет получена на машине Тьюринга следующим образом:
x+1
# | | | | # # | | | | # # | | | |# # | | | | #
qí q1 q1 q1
# | | | | # # | | | | | # # | | | | | # # | | | | |
q1 q2q q2 q2
x + 1
# | | | | | # # | | | | | # | | | | | # # | | | | | #
q2 q2 q3 qk