- •Вопросы для подготовки к экзамену
- •Интуитивное определение алгоритма и вычислимой функции
- •Частично и примитивно рекурсивные функции
- •Вычислимость рекурсивных функций. Тезис Черча
- •Определение оператора подстановки, примеры применения
- •Определение оператора примитивной рекурсии, примеры применения
- •Определение оператора минимизации, примеры применения
- •Построение одноместных рекурсивных функций
- •Построение двухместных рекурсивных функций
- •Машины Тьюринга. Команды в виде четверок и в виде пятерок
- •Функции, вычислимые по Тьюрингу. Тезис Тьюринга
- •Одноместные функции, вычислимые по Тьюрингу
- •Двухместные функции, вычислимые по Тьюрингу
- •Машины с неограниченными регистрами
- •Нормальные алгоритмы Маркова
- •Машины Поста. Функции, вычислимые по Посту
- •Нумерация множества упорядоченных пар натуральных чисел
- •Нумерация машин Тьюринга и вычислимых функций
- •Существование функции, невычислимой по Тьюрингу
- •Разрешимые отношения: определение и примеры
- •Свойства дополнения, объединения и пересечения разрешимых функций
- •Неразрешимость проблемы остановки
- •Универсальные функции
- •Теорема о параметризации
- •Меры сложности алгоритмов
-
Функции, вычислимые по Тьюрингу. Тезис Тьюринга
Рассмотрим следующий двухэлементный список внешних символов: . Представим натуральное число как слово, состоящее из единиц: . Числовая -местная функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая конфигурацию преобразует в конфигурацию с машинным словом , если функция определена и равна , и останавливается не в заключительном состоянии (нет команды для очередной конфигурации!) или не останавливается, если функция не определена.
Приведем примеры вычисления функций на машинах Тьюринга.
1) Функция следования вычислима по Тьюрингу. Действительно, эта функция вычисляется следующей программой машины Тьюринга: . Если на входе дано , то изменения конфигурации следующие: .
2) Нулевая функция вычислима по Тьюрингу. Пишем программу: . Изменения конфигурации ():
.
-
Одноместные функции, вычислимые по Тьюрингу
Одноместная функция f:N0N0 с областью определения DN0 называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел xN0
начальную конфигурацию преобразует в заключительную конфигурациюq01y1, если xD и y=f(x),
и не выдает никакого результата, если xD.
Примеры. 1) Функция f(x)=x+2 вычислима по Тьюрингу.
Программа Тьюринга для функции f:
|
_ |
1 |
1 |
1 Л 0 |
1 Л 1 |
2 |
1 Н 0 |
|
Преобразования конфигурации при x=2 (и y=4):
q1111, q1_111, q2_1111, q011111.
2) Функция g(x)=1 вычислима по Тьюрингу.
Программа Тьюринга для функции g:
|
_ |
1 |
1 |
1 Л 2 |
_ П 1 |
2 |
1 Н 0 |
|
Преобразования конфигурации при x=2 (и y=1):
q1111, _ _ _q1_, _ _ _q2_1, q011.
-
Двухместные функции, вычислимые по Тьюрингу
Двухместная функция f:N0N0N0 с областью определения DN0N0 называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел x,yN0
начальную конфигурацию преобразует в заключительную конфигурациюq01z1, если (x,y)D и z=f(x,y),
и не выдает никакого результата, если (x,y)D.
Примеры. 1) Функция f(x,y)=x1 вычислима по Тьюрингу.
Программа машины Тьюринга для функции f(x,y)=x1:
x1 |
_ |
1 |
1 |
_ П 2 |
1 П 1 |
2 |
_ Н 3 |
_ П 2 |
3 |
_ Л 3 |
1 П 4 |
4 |
1 П 0 |
|
Преобразования конфигурации для f(x,y)=x1 при x=2, y=1, z=3:
q1111_11, 111q1_11, 111_q211, 111_ _ _q2, 111_ _ _q3,
11q31_ _ _, 11q31_ _ _, 111q4, 111q4, 1111q0.
2) Функция z=xy вычислима по Тьюрингу.
Программа машины Тьюринга для функции z=xy:
xy |
_ |
1 |
1 |
1 П 2 |
1 П 1 |
2 |
_ Л 3 |
1 П 2 |
3 |
|
_ Л 4 |
4 |
|
_ Л 0 |
Преобразования конфигурации для z=xy при x=2, y=1, z=3:
q1111_11, 111q1_11, 1111q211, 111111q2, 11111q31, 1111q41_, 111q01_ _.