- •1.Основные понятия теории алгоритмов.
- •2.Примитивно рекурсивные функции. Базис элементарных функций. Операции подстановки и примитивной рекурсии.
- •3.Примитивно рекурсивные функции. Основные свойства операций подстановки и примитивной рекурсии.
- •4.Примитивно рекурсивные функции относительно совокупности функций. Основные свойства.
- •5.Производные операции над функциями.
- •6.Операции конечного суммирования и конечного произведения.
- •7.Предикат, логическая функция. Логические операции с предикатами.
- •8.Операции навешивания кванторов. Операции навешивания кванторов относительно двуместных предикатов
- •9.Примитивно рекурсивный предикат.
- •10. Операция навешивания ограниченного квантора над предикатами
- •11. Кусочное задание функции.
- •12 Операция ограниченной минимизации.
- •13.Частично рекурсивные функции.
- •14. Машина Тьюринга (мт). Применение мт к словам
- •16. Вычислимые по Тьюрингу функции.
- •17. Правильная вычислимость функций на машине Тьюринга.
- •18. Вычислимость по Тьюрингу примитивно рекурсивных функций. Суперпозиция.
- •19. Вычислимость по Тьюрингу примитивно рекурсивных функций. Примитивная рекурсия.
- •20. Вычислимость по Тьюрингу частично рекурсивных функций.
- •22. Нормальные алгоритмы Маркова и их применение к словам.
- •23. Нормально вычислимые функции и принцип нормализации Маркова.
- •15.Конструирование мт. Операции над машинами Тьюринга.
16. Вычислимые по Тьюрингу функции.
Определение 1. Ф-я наз-ся вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т.е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена.
Остается договориться о некоторых условностях для того, чтобы это определение стало до конца точным. Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения. Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения х1,, х2, ..., хп аргументов функции f(x1, x2, ..., хп), из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения х1,, х2, ..., хп аргументов будем располагать на ленте в виде следующего слова:
Здесь полезно ввести следующие обозначения. Для натурального х обозначаем:
Iх = , 0х =.
Дополнительно полагаем 0° = 1° = — пустое слово. Так что на слова 1° = , I1 = 1, I2 = 11, I3 = 111, ... будем смотреть как на «изображения» натуральных чисел 0, 1, 2, 3, ... соответственно.
Таким образом, предыдущее слово можно представить следующим образом: . Далее, начинать переработку данного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии q1 обозревается крайняя правая единица записанного слова. Если ф-я f(x1, x2,..., хп) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f(x1, x2, ..., хп) единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное определение 1 становится абсолютно строгим.
Сконструировать машину Тьюринга — значит написать (составить) ее программу. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется).
17. Правильная вычислимость функций на машине Тьюринга.
Определение 1. Будем говорить, что машина Тьюринга правильно вычисляет функцию f(x1, x2, ..., хп),, если начальное слово она переводит в словои приэтом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева.
Пример 1. Приведем программы машин Тьюринга, правильно вычисляющих функции S(x) = х+ 1 и 0(х) = 0. Функция S(x) =х+ 1 осуществляет перевод: q101x0 => q001x+1. Ее программа:
q10→ q2 П; q21→ q21 П; q20→ q31; q31→ q31 Л; q30→ q00. Функция O(x) = 0 осуществляет перевод: q101x0 => q000x+1. Ее программа: q10→ q2 0П; q21→ q21 П; q20→ q30Л; q31→ q40; q40→ q30Л, q30→ q00. Соответствующую машину Тьюринга обозначили О.