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

Пример. Рассмотрим всюду определенную функцию сложения f(x,y)=x+y. Покажем, что эта функция вычислима по Тьюрингу. Для этого построим машину Тьюринга: до 1 So qo qo So R qi qi 1 Rqi qi 1 q2 q2 1 Rq2 q2 SoLq3 qs 1 So qs Нетрудно убедиться, что эта машина переводит слово (т,п) =77...7 *77...7 в слово 77...7, а последнее слово означает т+1 п+1 т+п+1 ЧИСЛО т+п, следовательно, эта машина Тьюринга вычисляет функцию х+у. Итак, функция х+у вычислима по Тьюрингу. § 10. Связь между машинами Тьюринга и нормальными алгоритмами Теорема 5.5. Пусть Т - машина Тьюринга с алфавитом А. Тогда суш,ествует нормальный алгоритм В над А, вполне эквивалентный относительной алгоритмуТ ь юр и н г а . Доказательство. Каждая конкретная машина Тьюринга содержит конечное число команд вида 1)-3) (§ 7). Выпишем сначала для всех команд вида QJSISKQR (если они есть) машины Т формулы подстановки QJSI^RSK- При э порядок этих формул подстановок друг относительно друга не суш,ественен, ибо никакие две команды машины Т не имели совпадаюш,ими первые два символа. Далее для каждой команды вида QJSILQR (если она есть) выпишем всевозможные формулы подстановки вида siqjsi^rsisi, где sie A, И формулу подстановки qjSi^rSoSi. Затем для каждой команды вида qjSiRqr (если она есть) выпишем всевозможные формулы подстановки QJSISI^IQRSI, где S ie A, И формулу подстановки qjSi^iqrSo. Наконец, выпишем всевозможные формулы подстановок QI —>»A, где Q^ - внутреннее состояние заданной машины Т, и формулу подстановки Л—Що- Полученная таким образом таблица (схема) формул подстановок определяет некоторый нормальный алгоритм В над Покажем, что полученный нормальный алгоритм В вполне эквивалентен относительно алфавита А алгоритму Тьюринга А т ^ а , т.е. оба алгоритма одинаковым образом преобразуют любое слово Р алфавита А. Для этого возьмем произвольное слово Р в алфавите А, пусть, например, P=Ski,Sk2,---Skm, где Ski^A. Машина Тьюринга находится сначала во внутреннем состоянии qo и 161