Математическая логика и теория алгоритмов

§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу С каждой машиной Тьюринга можно связать некоторый алгоритм АТ,А В алфавите^ машины Т. Возьмем произвольное слово Р алфавита А и запишем его слева направо в квадратах чистой ленты, причем так, чтобы первая (самая левая) буква Р находилась под читающей головкой. Приведем машину Т во внутреннее состояние Ро­ машина начинает работать. Если она когда-нибудь остановится, то появившееся на ленте слово Q алфавита А является результатом применения машины Т к слову Р. Алгоритм преобразования слова Р в слово Q с помощью машины Т называется алгоритмом Тьюринга и обозначается через АТ , А - Будем говорить, что машина Тьюринга Т с алфавитом А , включающим 1 и *, частичновычисляет частичную арифметическую функцию Л^\,хъ:.,х„), если для любых натуральных к],къ--,к„ и некоторых г и т имеем; /раз тогда и только тогда, когда определена хотя бы одна из частей этого равенства. Это означает, что применение алгоритма Тьюринга АГ , А к слову (к^,к2,...,к„) даст слово, означающее с точностью до слов S Q И Б'о" значение функции Д^1,А:2,-.ДП ) (^О ~ интерпретируется как изображение пустого квадрата ленты). Частично определенная арифметическая функция называется частично вычислимой по Тьюрингу, если существует машина Тьюринга, которая частично вычисляет Дх]Д'2,.,.,х„). Арифметическая функция Я^\,хъ...,х,) называется в ы ч и с л и м о й по Т ь ю р и н г у , если существует машина Тьюринга Т с алфавитом А , включающим 1 и *, такая, что для любых нат>'ральных кькъ-,кп найдутся некоторыег и т ; 238