Всякая функция, допускающая вычисление с помощью алгоритма в интуитивном смысле, вычисляется на подходящей машине Тьюринга. Функции, допускающие вычисление на машинах Тьюринга, называют Т-вычислимыми.
f(n)=2n
1q0®aq1п
Lq1®Lq1л аq1®1q2.
1q1®aq3л аq3®aq3л
Lq3®aq4п аq4®aq4п
1q4®aq3л
Lq4®Lq5л аq5®1q5л
Lq5®стоп
Пусть К – некоторый класс функций типа N®N. Функция Ф(n,x) называется универсальной для класса К, если:
1. "n0ÎN Ф(n0,x)ÎK;
2. "fÎK $n0ÎN "x f(x)=Ф(n0,x).
Теорема
Класс функций К имеет универсальную функцию тогда и только тогда, когда он не пуст и не более чем счетен.
Доказательство (в одну сторону)
Пусть $ универсальная функция Ф(n,x). Тогда Ф(0,х), Ф(1,х), Ф(2,х), … - нумерация всех функций класса. Но эта нумерация не безповторна (некоторые функции могут встречаться несколько раз). Удалим все, кроме первого, вхождения каждой функции (т.е. каждая функция останется лишь в одном экземпляре). Хотя бы одна функция останется в любом случае. Оставшиеся функции можно занумеровать => класс счетен.
Тезис Черча: всякая функция, допускающая вычисление с помощью алгоритма в интуитивном смысле, вычисляется на подходящей машине Тьюринга. Иными словами всякая вычислимая функция является Т-вычислимой.
Аргументы:
1. Огромное количество интуитивно вычислимых функций допускают вычисление на машинах Тьюринга. Не было найдено примеров противоположной ситуации.
2. Имеется много операций, сохраняющих (в естественном смысле) вычислимость. f,g – вычислимы. g(f(x)) – вычислима. Для всех таких операций были доказаны утверждения о Т-вычислимости результата, при условии Т-вычислимости тех функций, над которыми операция выполняется.
3. Было построено много других формализаций общего понятия алгоритма, причем доказано, что все они оказываются эквивалентными машинам Тьюринга. Одна из таких формализаций – т.н. «нормальные алгорифмы» А.А. Маркова.
Класс всех вычислимых функций одного переменного обладает вычислимой универсальной функцией.
Доказательство. Рассмотрим все машины Тьюринга, вычисляющие функции типа N®N. Будем рассматривать такие машины лишь с точность до изоморфизма. При этом ограничении можно считать, что состояния такой машины занумерованы стандартным образом: Q={q0, …, qn}, а алфавитом служит А={L, 1, 2, …, k}. Если числа n и k фиксированы, то существует лишь конечное множество программ, с соответствующими Q и А.
В фиксированной программе порядок команд не имеет значения. Поэтому в каждой программе занумеруем ее команды лексикографическим образом. После этого занумеруем все программы с фиксированными n и k также лексикографически. Наконец, занумеруем привычным образом все пары натуральных чисел n и k. Номер программы определяется так: вычисляется номер пары (n.k), нумеруются подряд все программы, соответствующие парам с меньшими номерами, а также, все программы для этой пары (n,k).
Алгоритм для вычисления универсальной функции Ф(n,x) таков:
Возьми значение первого аргумента n, найди программу машины Тьюринга с номером n и запусти машину с этим номером вычислять соответствующую ей функцию для значения аргумента х. Вычислимость функции Ф(n,k) очевидна. Эта функция является универсальной для класса всех вычислимых функций. Действительно, условие 1 определения универсальной функции выполняется, т.к. Ф(n,k) вычислима и потому, зафиксировав каким угодно образом значение ее первого аргумента, мы всегда получим вычислимую функцию. Условие 2 выполняется, т.к. при подходящем значении аргумента n, описанный выше алгоритм (после реконструкции программы, имеющей данный номер) имитирует работу любой машины Тьюринга.
Вычислимая универсальная функция Ф (класса всех вычислимых функций) не продолжается до вычислимой всюду определенной функции.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.