Игошин Математическая логика и теория алгоритмов (1019110), страница 86
Текст из файла (страница 86)
Следовательно, Ы(3, 4) не определено. Пример 33.18. Аналогично, с помощью оператора минимизации можно получить частичную функцию, выражающую частное от деления двух натуральных чисел: хуу= д(х, у) = рг[у г=х] =рг[р(11(х, у, г), 11(х, у, г)) = 1 (х, у, г)]. Заметим, что обе функции из двух последних примеров не всюду определены, т.е. являются частичными.
346 В Задачнике рассматриваются и другие функции, получаемые помощью оператора минимизации (см. М 13.17). С помощью Н-оператора можно построить некоторые всюду определенные аналоги рассмотренных функций: (х — у] = Не[у+ г > х] = рг(У+ 7+ 1 > х] (х/у] = Нг Ьг > х] = НгЫг+ 1) > х]. Первая из этих функций равна О, если х< у, и равна х — у, если > у, Вторая представляет собой целую часть функций х/у. Заметим, что механизм проявления неопределенности функции в точке при вычислении ее значения с помощью Н-оператора такой же, как и при вычислении ее на машине Тьюринга: в случае неопределенности процесс вычисления не останавливается, а продолжается неограниченно долго. Общерекурснвные н частично рекурсивные функции.
Итак, функция называется частично рекурсивной (определение 33.6), если она может быть построена из простейших функций О, 5, 1" с помощью конечного числа применений суперпозиции, примитивной рекурсии и Н-оператора. Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной. Мы уже отмечали, что класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются функции, не всюду определенные, например функции а(х, у) и д(х, у), рассмотренные в примерах 33.17, 33.18, а также, например, нигде не определенная функция/(х) = Ну(х+ 1+ у= 0]. Примером обшерекурсивной, но не примитивно рекурсивной функции может служить и функция Аккермана А(х).
(Доказательство ее общерекурсивности можно найти, например, в 11!.8], часть П1, ~ 1, Хь 42, а.) Продолжим теперь продвижение к поставленной цели — к описанию всех функций, вычислимых на машинах Тьюринга. Следующий шаг — доказательство того, что все частично рекурсивные функции вычислимы по Тьюрингу. Вычнслимость по Тьюрннгу частично рекурсивных функций. ТеоРема 33.19. Если функция Ях, у) правильно вычислимо на машине Тьюринга, то и функция <р(х) = Ну[Як„у) = 0], получающаяся с помощью оператора минимизации из функции ях, у), также правильно вычислимо на машине Тьюринга.
До казател ьств о. Обозначим г" — машину Тьюринга, правильно вычисляющую функцию/(х, у). Используя ее, сконструируем такую машину Тьюринга, которая для заданного значения х вы"исляет последовательно значения /(х, 0), Лх, 1), 1(х, 2), ... до тех "оР, пока в первый раз получится/(х, 1) = О. После этого машина должна выдать на ленту число 1, представляющее собой значение Функции <р(х) =!. Если же для всех )будет иметь место/(х, 1) > О, то 347 машина должна работать вечно, и это будет означать, что функ ция <р не определена в точке х. Начальная конфигурация на коне<.
руируемой машине такова: 21<01"О. Будем мыслить ее следующи<„ образом: <2<0! «0!ь и начнем с применения к ней машины «копиро вание» К2. Получим конфигурацию: 01 "01ьоО! "01ь. Теперь вычислим значение 2"(х, 0), применив машину г< О!'01~д,01г<" ь'. Далее подбираем команды, которые при условии г(х, <) > 0 преобразовывают конфигурацию О!"01<д01Г<" л в конфигурацих2 01 01 дО!д >.
<2,0 — » д„<ОП: 01"0 1ьО 2« «< 1Г<к'ь<; <та«<! + Ча«20. О! 01 Од.,",01Г<. ь<-<; <1« 20 -+ Ча+ЗОЛ: О! 01 Ча«5001~~ 01.01'<1 410ИкЕ Ча«41» <<а«5 1П. 01.0 !'). „01г<к'ь<-', О: О! 01аО; Б-Б-: <20! "01', К2. 01.01<д01.01<; Р: 01 01<д,01г< >; д50 -» д„О: О!'01<<),01г«" >. Последняя команда зацикливает программу, и машина от конфи- гурации 01"01<д„01л<" и переходит к конфигурации 01"012д,О!А<" 2>, затем к конфигурации О!"015д,ОФ" '> и т.д. Допустим, что по ис- течении некоторого времени машина достигла конфигурации 01"01<0,01г<" <2, при которой г(х, 2) = О.
это означает, что <р(х) = < и машина должна выдать этот результат. Число < накопленно в «счетчике» 01( Поэтому поступаем следующим образом. Уже име- ющаяся команда д,Π— » о„<ОП приведет машину к конфигурации 01»0! <Од„, <О. Следующие команды выдают на ленту необходимую конфигурацию <гь01<, т.е.
д»01«<м: а,,О-+ <1 0: 01 01<Од,О; Б Б: БОБ: ),01; <)ьо -+ Чоо: ®01«'2. Теорема доказана. П Следствие 33.20. Всякая частично рекурсивная функция вычисли- мо но Тьюрингу. Доказательство. Итак, поскольку оператор минимизации сохраняет свойство вычислимости по Тьюрингу (этим же свой- ством, как было установлено выше, обладают и операторы супер- позиции и примитивной рекурсии), простейшие функции О, 5, 1„» вычислимы по Тьюрингу, а всякая частично рекурсивная функ- ция получается из простейших с помощью применения конечно- го числа раз трех указанных операторов, то всякая частично ре- курсивная функция вычислима по Тьюрингу.
П 348 Частичная рекуреивиость функций, вычиелимых по Тьюриигу. Наконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что он исчерпывает класс всех вычислиных по Тьюрингу функций. Это нам и предстоит доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь частично рекурсивные функции, т.е. если функция вычислимо ло Тьюрингу, то она частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины Тьюринга, вычисляющей функцию Яхн ..., х„), можно построить рекурсивное описание этой функции.
Эта теорема впервые была доказана Тьюрингом. Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна, Доказательство. Прежде чем приступить кдоказательству теоремы, обратим внимание на следующее обстоятельство. Машина Тьюринга, преобразовывающая слова в алфавите А = (аь, аь ..., а 1), никак не различает природу этого алфавита.
В частности, она никак не отличает числа от «нечисельн работая с числами, машина не считает их в смысле известных арифметических правил, а преобразовывает слова, представляющие собой записи чисел на каком-то языке (в какой-то системе счисления). Правила преобразований задаем мы с помощью соответствующей программы, и мы же даем полученному машиной словесному результату числовую интерпретацию.
Именно в этом смысле мы говорили о вычислимости машиной Тьюринга тех или иных числовых функций. Чтобы доказать сформулированную теорему, необходимо идею арифметической (числовой) интерпретации работы машины Тьюринга довести до определенного совершенства и показать, что любое преобразование, осуществляемое машиной Тьюринга, если его интерпретировать как вычисление, является частично рекурсивным. Разделим доказательство на этапы (их будет пять). Первый этап.
Арифметизация машин Тьюринга начинается с того, что мы вводим в машину своего рода арифметическую систему коорлинат. Эта система координат предназначена лля конфигураций машины. Как известно, в каждый момент времени конфигурация на ленте машины Тьюринга имеет вид ад;аф, где а — слово в алфавите А = (аь, а„..., а 1), записанное на ленте левее обозреваемой в данный момент ячейки; Ъ вЂ” состояние, в котором находится в данный момент машина; а, — содержимое обозреваемой в данный момент ячейки; ~3 — слово в алфавите А, записанное на ленте правее обозреваемой ячейки. Указанной конфигурации однозначно сопоставлЯетсЯ УпоРЯдоченнаЯ четверка (а, 1(н а,, Р) чисел, определяемых следующим образом: о = 1; а, = /„а — число, изображаемое цифрами, полученными кодированием символов слова и по следующему правилу: эти символы интерпретируются как т-ичные цифры, т.е.
цифры т-ичной системы счисления, т. е. 349 а; кодируется цифрой 1; 1) аналогично получается из !), но при этом читается справа налево, т.е. крайняя слева ячейка !) содержит самый младший разряд, а крайняя справа — самый старший (это сделано для того, чтобы нули справа от ~) не влияли на значение !)). Завершим кодирование элементов машины Тьюринга. Символу а0 пустой ячейки сопоставим число О, сдвигу вправо П сопоставим 1, сдвигу влево Л вЂ” 2, отсутствию сдвига С сопоставим О, буквой г закодируем заключительное состояние (состояние остановки) д0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
