Составители:
Рубрика:
нумерации может быть выполнена некоторой машиной, которую
обозначим через M
. Очевидно, что машина M
1 1
может вычислить и
свой собственный геделевский номер. Очевидно также, что
существует машина M
2
, которая для любого восьмеричного числа X
выдаст один из двух ответов:
• “число X не является геделевским номером какой-либо
машины”;
• “число X является геделевским номером машины, имеющей
следующие команды …”.
Определим Q
z
(X) следующим образом:
f(X), где f(X) – значение функции f(X),
Q
z
(X) = вычисляемой машиной с номером z для задания X;
0, если z не является номером какой-либо машины.
Теорема 4.2. Функция Q
z
(X) частично-вычислима.
(X), Q (X),…, Q
Доказательство. Последовательность Q
n0 1
(X),…
перечисляет, быть может с повторениями, множество частично-
вычислимых функций. Тем самым мы можем также перечислять
области определения таких функций.
Пусть заданы конкретные значения z и X. Чтобы вычислить
Q
z
(X), необходимо сначала с помощью машины M
2
узнать, является
ли z геделевским номером какой-либо машины. Если ответ
положительный, то определив по z набор команд соответствующей
машины Тьюринга Z, можно предложить этой машине X в качестве
входного задания. Таким образом, соединяя вместе M
2
и Z, получим
машину, вычисляющую Q
z
(X). Теорема доказана.
Машина, вычисляющая Q
z
(X), называется универсальной
машиной Тьюринга.
Рекурсивные множества
Пусть A – некоторое множество натуральных чисел. Функцию
1, если x∈A;
0, если x∉A,
A
(x) =χ
164
Страницы
- « первая
- ‹ предыдущая
- …
- 78
- 79
- 80
- 81
- 82
- …
- следующая ›
- последняя »
