![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В этом разделе мы докажем несколько неожиданный результат, состоящий в том, что существуют универсальные программы, то есть программы, которые в некотором смысле реализуют все другие программы. Этот результат является одним из основных результатов теории вычислимости.
Определение 6.1. Универсальной функцией для n -местных вычислимых функцийназывается (n+ 1)-местная функция
.
Для примера рассмотрим функцию . Эта функция реализует все одноместные вычислимые функции
. Действительно, для произвольного неотрицательного целого числа т функция
совпадает с функцией
. Таким образом, название функции
вполне соответствует классу вычисляемых ею одноместных функций.
Ниже для простоты вместо будем писать
.
Теорема 6.1.Для каждого натурального числа n универсальная функция вычислима.
Доказательство. Покажем, как можно вычислить значение функции для заданного числа m и фиксированного набора (x1,..., xn). Неформальная процедура вычисления значения
состоит в следующем: «Декодируйте число m и восстановите программу Рm. Затем имитируйте вычисление по этой программе. Если вычисление по программе заканчивается, требуемое значение
содержится в регистре R1». По тезису Черча заключаем, что функция
вычислима.
Определение 6.2. Любая программа Р(n), вычисляющая функцию , называется универсальной программой.
Универсальные программы полностью соответствуют своему названию. Действительно, так как универсальная программа Р(n) позволяет вычислить любую n- местную вычислимую функцию, то, по сути дела, программа Р(n) заменяет абсолютно все программы для вычисления n- местных функций.
Проиллюстрируем теперь, как использовать вычислимость универсальных функций в диагональных построениях.
Дата публикования: 2015-03-26; Прочитано: 471 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!