Теория алгоритмов и формальных языков. Мелихов А.Н - 39 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

2.6. Рекурсивный и рекурсивно перечислимые множества
Рассмотрим некоторую функцию
),...,,(),...,,(
2121 nZn
xxxxxxf
ψ
=
. По
определению она частично вычислима, если существует МТ Z, которая эту
функцию вычисляет. Так как машине Z однозначно сопоставлен геделевский
номер
)(Znqz = , то всякой частично вычислимой функции ),...,,(
21 n
xxxf
можно сопоставить геделевский номер именно той МТ, которая эту функцию
вычисляет.
Введем функцию
),...,,(
21 nZ
xxxΦ , где z - целое неотрицательное число, а
),...,,(
21 n
xxx - некоторая n-ка из N
n
, следующим образом. Если )(Znqz
=
,
причем Z - МТ, вычисляющая значения f на n-ке
),...,,(
21 n
xxx , то значение
функции
),...,,(
21 nZ
xxxΦ совпадают со значениями функции ),...,,(
21 n
xxxf .
Если не является геделевским номером никакой МТ, то значение функции
0),...,,(
21
=
n
xxx . В результате мы получили вычислимую функцию, которая и
можем теперь записать последовательность
,...,...,,
10 n
Φ
Φ
Φ
, которая
перечисляет (быть может с повторением) множество частично вычислимых
функций от n аргументов. Таким образом, мы можем в принципе перечислять
области определения частично вычислимых функций.
Пусть заданы теперь произвольные z и
),...,,(
21 n
xxx . Тогда, чтобы
вычислить значения функции
),...,,(
21 nZ
xxx
Φ
, необходимо сначала выяснить,
является ли z геделевским номером какой-либо МТ. Эту задачу решает МТ
G
2
, введенная в разделе 2.5. Если z не является геделевским номером, то
0),...,,(
21
=Φ
nZ
xxx . В противном случае МТ Z, команды которой
распечатываются МТ G
2
, предлагается ),...,,(
21 n
xxx в качестве исходного
задания. Соединяя G
2
и Z, мы получаем универсальную МТ, вычисляющую
функцию
),...,,(
21 nZ
xxxΦ . Если на ленте этой машины поместить число
)(Znqz = , то она сможет вычислять функцию, соответствующую этому числу.

Страницы