Игошин Математическая логика и теория алгоритмов (1019110), страница 87
Текст из файла (страница 87)
В итоге алфавит А закодируется числовым множеством А, а алфавит 0 — числовым множеством 9 Тогда, например, если мы имеем машину Тьюринга с внешним алфавитом А = (ам а,) и на ее ленте имеется конфигурация а,а0а,а,агдза,а,ага,ан то при нашей кодировке (или координатизации) ей соответствует следующая упорядоченная четверка натуральных чисел: (22, 3, 1, 13). Поясним, как она получилась. В нашей конфигурации а = а,а0а,а,аг, д; = дз, аэ = ан Р = а,а0а,аь Поэтому а= 10! 10 — двоичное число, которое следующим образом переводится в десятичное: (!0110)з =! .
2" + 0 2з+! 2з+ 1 . 2'+ 0 . 2 = 22. Далее, д, = 3, а, = 1 и, наконец, !) = [1101]г = 13. Второй этап. При таком кодировании система команд машины Тьюринга с алфавитом А и множеством состояний 0 превращается в тройку числовых функций: (г х А -эА (функция печатаемого символа); <р,: 0 х А — > 0 (функция следующего состояния); (рг: 0 хА — > (О, 1, 2) (функция сдвига). Например, если среди команд машины Тьюринга имеется команда д;а, — > дга,'Х, то д,(дь йэ) = й,', <рд(дь а;) = д,", цг(два,.) = Р, где с, = О, 1, 2, если Х = С, П, Л соответственно.
Отметим, что все эти функции у„уг, уг заданы на конечном множестве (г хА и потому примитивно рекурсивны. Третий этап. Выполнив одну команду, машина Тьюринга преобразует имеющуюся на ленте конфигурацию К= ад;а,!) в новую конфигурацию К'= а'д';а',К.
При арифметизации это означает, что упорядоченной четверке чисел (а, дьад 1) ), соответствующей конфигурации К, однозначно сопоставляется упорядоченная четверка чисел (а', дьа',, б'), соответствующая конфигурации К'. Например, прй команде д а, — ~ д4ааП ранее приведенная конфигурация перейдет в конфигурацию К' = а,ага,а,а0аад4а,ава,ан которой соответствует четверка чисел (44, 4, 1, 6).
Так будет происходить почти со всеми конфигурациями, связанными с алфавитами А, (г. В итоге на множестве таких конфигураций будет задана (вообще говоря, не всюду определенная, т.е. частичная) нечисловая функция щ(К) = К', обусловленная данной машиной Тьюринга О. Назовем ее функцией следующего шага. 350 й'(й„д,, а,, р) = й, если <р~(дн а,) = О (нет сдвига), тй+ ср,(до аз), если ср~(дн а,) = 1 (сдвиг вправо), й/и, если д~(до а,) = 2 (сдвиг влево). Совершенно аналогичная, но в определенном смысле двойственная картина наблюдается и для функции б'. при сдвиге вправо (влево) она ведет себя так же, как функция й' при сдвиге влево (вправо).
Так что для нее получаем следующее описание с помощью оператора условного перехода: б, если <рд(дн а ) = О (нет сдвига), б'(й, дн а,, б) = 13/т, если ~рд(дн а,) =1 (сдвигвправо), и13+ ср,(д„а,), если щр(до а,) = 2 (сдвиг влево). 351 При введенной арифметизации этой функции соответствует четверка числовых функций следующего шага. Иначе говоря, й', д', а', 13' — это числовые фУнкции, каждаЯ из котоРых зависит от четырех числовых переменных й, д, а, б. Попытаемся понять, как эти функции связаны с функциями системы команд д„у«, д~. Вопервых, ясно, что д'; = <р и функция д'фактически не зависит от р, а зависит лишь от д, а, т.е. д'(й, дь а,, (3) = ц«(д„аз). Рассмотрим теперь функцию а'(й, д;, а,, 13).
Если йри рассматриваемом такте работы машины ее головка осталась на месте, т.е. обозреваемая ячейка не изменилась, т.е. у«(два,) = О, то ясно, что й' = й. Если головка сдвинулась вправо, т.е. ~р (дь а,) = 1, то это означает, что степень каждого разряда числа й повысилась на единицу: нулевой разряд стал первым, первый — вторым и т.д., т.е. число й увеличилось в т раз (напомним, что и — число элементов в алфавите А, т.е. основание системы счисления, в которой рассматривается наша арифметизация): тй. Кроме того, в образовавшийся младший (нулевой) разряд помещается та т-ичная цифра, которая соответствует при кодировании только что вписанному на ленту элементу из А. Эта цифра равна у,(дь а,).
В итоге получим, что при сдвиге вправо: й'(й, дь а,,б) = тй, + д,(два,). Наконец, при сдвиге на данном шаге головки влево, т.е. при <рд(два,) = = 2, степень каждого разряда числа й понизилась на единицу: первый разряд стал нулевым, второй — первым и т.д., т.е. число й уменьшилось в т раз: й/и. Но поскольку самый младший (нулевой) разряд оказался фактически как бы «отрубленным», то в итоге получилось не частное й/и (оно могло бы оказаться дробным), а его целая часть: !й/и1. Итак, для функции а' мы получаем следующее описание с помощью оператора условного перехода: Наконец, рассмотрим функцию а'(а, 4, а,, 0).
Если сдвига не происходит, то ясно, что а' = др,(4, ат). Если происходит сдвиг вправо, то машина приходит к обозрению самого левого разряда (напомним, что это есть младший разряд) — числа )3: именно он был отброшен при взятии для 13' целой части частного (3/и. Он как раз и представляет собой остаток от деления числа ~3 на лд, т.
е. в этом случае а'= г(т, 13). Если же происходит сдвиг влево, то двойственно получаем: а'= г(т,а). Итак, функция а' получает следующее описание: др,Я, ат), если дрд(ло ат) = 0 (нетсдвига), а'(а, дь, ат, б) = г(лд, 13), если дрЩ, ат) =! (сдвигвправо), г(лд, й), если ярд(дь, аз) = 2 (сдвиг влево). Теперь сделаем выводы. В полученных выражениях для функций с', а', 0', а' задействованы только примитивно рекурсивные функции, и указанные функции получены из этих примитивно рекурсивных функций с помощью оператора условного перехода, который, как мы знаем, сохраняет свойство примитивной рекурсивности, т.е.
из примитивно рекурсивных функций создает снова примитивно рекурсивную функцию. Следовательно, все функции а', д', а', ~3' примитивно рекурсивны. Итак, мы доказали, что на каждом шаге любая машина Тьюринга осуществляет примитивно рекурсивное вычисление. Четвертый этап. Рассмотрим теперь с точки зрения введенной арифметизации работу машины Тьюринга в целом. Пусть задана начальная конфигурация К(0) = Щ, дд, ад, 1)д). Тогда конфигурация К(г), возникающая на такте г работы машины, зависит от величины г и компонент ад, д„а„Ц начальной конфигурации, т.е. она является векторной функцией К(г) = (К (г), К(г), К,(0, К~(г)), компоненты которой, в свою очередь, являются функциЯми, зависЯщими от пеРеменных б а„яд, ад, 13д.
Эти фУнкции определяются следующим образом: К.(0, б„д„ад, 13д) = 0„. К,(г+1, ад, 4, ад, 1)д) = а'(К„(г ад Чд, ао 13д) Кд(г ао, лд ад, 0о), К.(1 по Чо бо* Ро) Ка(г пд Чо йо* Ро))' Кд(0) = Чд', К(!+1) = ц'(К,(г), КдЯ, К,Я, Ка(г)); К,(0) = ад; К,(1+1) = а'(К„(г), К,(г), К,Я, К~(г)). Кв(0) = ()д Ка(г+1) = Р'(К.(г) К(г) К.(г) Ка(г)). (В записях для функций К, К„Ка аргументы Ь~, 4, ад, рддля краткости опушены.) Эти соотношения представляют собой схемы примитивной рекурсии, определяющие функции К„Кд, К„К, с помощью функ- 352 ций а', д', а', )3'. При этом рекурсия ведется по переменной д Примитивная рекурсивность функций а', д', а', )3' установлена на предыдущем шаге доказательства.
Тогда отсюда очевидно следует, что и функции. К„К„К„Кр также примитивно рекурсивны. Пятый этап. Йаконец, на заключительном шаге доказательства покажем, что результат работы машины Тьюринга (т.е. вычисляемая машиной функция) носит рекурсивный характер. (Обратите внимание: не примитивно рекурсивный, а рекурсивный, т.е. здесь придется использовать оператор минимизации р.) Здесь мы докажем утверждение, обратное тому, которое было доказано в предыдущем пункте: всякая функция, правильно вычислимая на машине Тьюринга, частично рекурсивна. Пусть у — функция, правильно вычисляемая машиной Тьюринга. Такая машина„ начав с конфигурации д,ао))о, останавливается в конфигурации вида а,а,)3„т.е.
для такой машины К,(0) = О, Ко(0) = 1, исходное слово на ленте кодируется числом т]3, + а„заключительное слово— числом т)3,+ а„т.е. вычисляется значение функции <р(т))о+а,) = = тб,+ а,. Заключительное слово — это слово, написанное на ленте в тот момент г„когда машина впервые перешла в заключительное состояние а„т.е.
в момент О = Згг[Ко(г) = г). Поэтому )3, = Кр (О), а, = К,(О) и сР(т]Зо+ ао) = т)3, + а, = тКр(Г„О, 1, а„[Зо) + К,(!„О, ао ]Зо). Учитывая, что ]Зо = [х/т), ао = г(т, х), выражение для результирующего значения у(х) можно со всеми подробностями записать так: ср(х) = тКр(р.г[Ко(О О, 1, г(т, х), [х/т)) = г), О, 1, г(т, х), [х/т]) + + К,(рг[К,(0 О, 1, г(т, х), [х/т]) = г], О, 1, г(т, х), [х/т]), где т, г — константы, зависящие от конкретной машины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
