- •© Михеева е. А., 2016 © Ульяновский государственный университет, 2016 оглавление
- •Раздел 6. Элементы математической логики . . . . . . . . . . . . . . . . . . . . 9
- •Раздел 7. Ограниченно-детерминированные (автоматные) функции
- •Раздел 8. Вычислимые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
- •Раздел 9. Теория кодирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
- •Раздел 6. Элементы математической логики Предисловие
- •Исчисление высказываний
- •Язык ив
- •Аксиомы ив
- •Формулы алгебры высказываний
- •Соответствие между формулами ав и ив
- •Непротиворечивость ив
- •Полнота ив
- •Логические операции над предикатами
- •Теорема о полноте системы одноместных предикатов, заданных на конечном множестве
- •Исчисление предикатов (ип)
- •Формулы исчисления предикатов
- •Определение формул
- •Замена переменных в формулах
- •Правила образования выводимых формул
- •Замена переменного предиката
- •Задания для самостоятельной работы
- •Раздел 7. Ограниченно-детерминированные (автоматные) функции
- •Детерминированные функции
- •Свойство детерминированной функции
- •Примеры детерминированных и недетерминированных функций
- •Способ задания д.Функций
- •Вес детерминированной функции
- •Ограниченно-детерминированные функции
- •Способы задания о.Д.Функций
- •Конечные автоматы
- •Задания для самостоятельной работы
- •Раздел 8. Вычислимые функции Машины Тьюринга
- •Пусть в некоторый момент головка машины обозревает символ , находясь в состоянии , тогда:
- •Методы построения машин Тьюринга
- •1. Принцип двойственности для программ (машин).
- •2. Последовательное подключение одной машины к другой.
- •3. Итерация машины.
- •4. Специальный операторный язык для записи алгоритмов.
- •Описание технологии программирования для машин Тьюринга
- •Вычислимые функции
- •Операции с, Пр и
- •Классы вычислимых и рекурсивных функций
- •Эквивалентность класса рекурсивных функций и функций, вычислимых на машинах Тьюринга
- •Задания для самостоятельной работы
- •Раздел 9. Теория кодирования Алфавитное кодирование
- •Критерий однозначности декодирования
- •Задания для самостоятельной работы
Пусть в некоторый момент головка машины обозревает символ , находясь в состоянии , тогда:
Если в клетке команда cDq, то машина заменит в ячейке символ на с, перейдет в состояние q, осуществит движение D и приступит к выполнению следующей команды;
Если в клетке стоит пустая команда, то машина останавливается.
Итак, машина, начиная из исходной ситуации, осуществляет переработку исходной записи на ленте. При этом имеются две возможности:
При работе машины появится пустая команда – машина останавливается и на ленте получается заключительная запись. Состояния, в которых машина останавливается, называются заключительными.
При работе машины пустая команда не появится – машина никогда не остановится.
Введенные нами машины называются машинами Тьюринга.
|
|
0 |
|
1 |
1R |
-
0
1
1R
Машина, которая в произвольной записи, начиная из любой ячейки, двигаясь вправо, находит первый нуль.
Итак, машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки.
Методы построения машин Тьюринга
1. Принцип двойственности для программ (машин).
Пусть
Т
– любая программа. Обозначим через
программу, которую получаем из Т,
если в Т
заменить в командах R
на L,
L
на R.
Программа
называется двойственной
к T.
Пример.
Т: :
|
|
|
||||
|---|---|---|---|---|---|---|
|
0 |
|
||||
|
1 |
1R |
||||
|
|
|
||||
|
|
|
||||
|
|
|
||||
|
|
0 |
|
1 |
1L |
Очевидно,
что
= Т,
т.е. понятие двойственности программ
является взаимным.
Машины M и M* , соответствующие программам Т и , называются двойственными. Двойственные машины M и M* функционируют симметричным образом.
2. Последовательное подключение одной машины к другой.
Пусть M0 и M1 – две произвольные машины Тьюринга над одним и тем же входным алфавитом {0, 1, …, k-1}, множества состояний которых не пересекаются. Пронумеруем числами 0, 1, …, l-1 все пустые клетки (команды) программы Т0 машины M0. Пусть p(x) – произвольный предикат на множестве {0,1, …, l-1}. Построим машину M, которую и будем называть последовательным подключением машины M1 к M0 (относительно предиката p(x)). Для этого из таблиц Т0 и Т1 машин M0 и M1 построим новую таблицу Т.
-
… …
’ …
’
…
’0
Т0’
Т1
…
…
k-1
В ней первая половина совпадает с таблицей Т0 для тех клеток из Т0 , в которых стоит не пустая команда. В тех клетках , ({0,1,…, l -1}), для которых р()=1, в таблице Т стоит команда S ’ (где номер строки, в которой находится эта клетка ’ - начальное состояние M1). В тех клетках , для которых р()=0, в таблице Т стоит пустая команда. Вторая половина таблицы Т полностью совпадает с таблицей Т1.
Итак, работа машины M состоит в следующем: исходная запись ленты сначала перерабатывается машиной M0, и если машина M0 заканчивает работу по команде такой, что р()=1, то содержимое ленты перерабатывается машиной M1. При этом начальной ячейкой для M1 будет ячейка, в которой остановилась M0. Действительно, машина M в некотором смысле осуществляет последовательную работу машин M0 и M1.
