Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

qoaRqo qobRqo qoSooqi как легко убедиться, приписывает к любому слову Р алфавита {а,Ъ} справа букву а и останавливается. § 9. Алгоритм Тьюринга. Вычислимость по Тьюриигу С каждой машиной Тьюринга можно связать некоторый алгоритм Ат ^ а в алфавите А машины Т. Возьмем произвольное слово Р алфавита А и запишем его слева направо в квадратах чистой ленты, причем так, чтобы первая (самая левая) буква Р находилась под читаюш,ей головкой. Приведем машину Т во внутреннее состояние qo. Машина начинает работать. Если она когда-нибудь остановится, то появившееся на ленте слово Q алфавита А является результатом применения машины Т к слову Р. Алгоритм преобразования слова Р в слово Q с помош,ью машины Т называется алгоритмомТьюринга и обозначается через Ат,а- Будем говорить, что машина Тьюринга Т с алфавитом А, включаюш,им 1 и *, частично вычисляет частичную арифметическую функцию f(xi,x2,...,xyj, если для любых натуральных ki,k2,...,kn и некоторых г иw имеем: '^2 ~ ^0 f (^1 '^2 (^0 = SqSq^...Sq), i dag тогда и только тогда, когда определена хотя бы одна из частей этого равенства. Это означает, что применение алгоритма Тьюринга Л к слову (kj,k2,...,k „) даст слово, означающее с точностью до слов S q И S q значение функции f(ki,k2,...,kn) {So - интерпретируется как изображение пустого квадрата ленты). Частично определённая арифметическая функция f(xi,x2,...,xrj называется частично вычислимой по Тьюрингу, если суш,ествует машина Тьюринга, которая частично вычисляет f(xi,x2,...,xn). Арифметическая функция f (xi,x2,...,xn) называется вычислимой по Тьюрингу, если суш,ествует машина Тьюринга Т с алфавитом^, включаюш,им 7 и *, такая, что для любых натуральных ki,k2,...,kn найдутся некоторыег и т : (kj,k „...,kJ = S'o f(kj,k„...,kJS^. Это означает, что применение алгоритма Тьюринга Л к слову (kj,k2,...,k „) даст слово, означающее с точностью до слов Sq И Sq значение функции f(ki,k2,...,kyj, т.е. существует машина Тьюринга, вычисляющая эту функцию для любых значений её аргументов. 160