С.В. Яблонский - Введение в дискретную математику (1060464), страница 23
Текст из файла (страница 23)
Такого рода функции будем называть частичныли Яуннцитши счетнозначной логики, Обозначим через Р"» множество всех частичных функций счетнозначной логики. Как и в случае ве всюду определенных функций из Р, (см. гл. 3), можно ввести понятие несущественной переменной. Определение. Переменная х, называется несущественной для функции ((хо ..., х„) из Р»; если существует функция т" из Р», такая, что ~'(хо ..., х„) = ~(хь ..., х„) на Ег и переменная д не существенна для ('(хь ..., х„). В дальнейшем частичные функции будем рассматривать с точностью до несущественных переменных, относительно которых множество Ег цилиндрично. В атом случае существует доопределение функции (, т.
е. функция (' из Р», которая несущественно зависит от всех таких переменных, ч Определение. Функция Дхь ..., х„), гдето~ Р»; называется вычислимой, если существует машина Тьюринга йй такая, что: а) при (ао ..., гг„)жЕг машина Ю1, будучи применена к основному иоду для (ао ..., и ) и находясь в начальном состоянии над его левой единицей, останавливается и в ааключительном состоянии ва ленте выдает код для )(гсн ..., и.); б) при (ан ..., а )ФЕ, машина лг, будучи применена к основному коду для (ао ..., а.) и находясь в начальном состоянии над его левой единицей, либо не останав- 144 ч ! Фуппцпоплльпые системы с опетлцпями лнвается, либо остапавлпвается, по пря этом запись на ленте отлична от кода любого числа из Е„.
а Замечание. Константы нз Е„моя«по таки!е счи"« тать вычислимыыи фувкцяял!и с пустым множеством переменных в следующем смысле. Пусть Т еи Е „. Рассмотрим машину, задаваемую "« табл. (5. Покольку т — константа, то в начальном положении лента считается пустой. Очевидно, машина, пачнТабл цца 15 Таблица 16 х хтю х, Ояхт+! 1Ьх + 15»« Оях! 1дх«!ях« ная от исходной ячейки, движется вправо и формирует массив из т+ 1 единиц — код т, и затем возвращается ва левый конец массява. Приведем прка!ер вычнслпмой функции. П р и м е р 6.
Покажем, что функция 0(х) 0 вычпслима. Для этого возьмем в!ашину, определяемую табл. 16. Очевидно, что эта машина «реализуета функцию 0(х) О. Заметим, что данная машина «реализуета также функ- . цию 1(х„х,) х, + 1 и константу 0 (как функцию, аавпсящую от пустого множества переменных). Обозначим через Р,, класс всех вычнслвмых функций. Очевидно, Ран«с= Р»,. О и р е д е л е н н е.
Машина Тьюринга й реализует (вычисляет) функцию 1(х„..., х„) (из класса Р,,) ярааильным образом, если: а) при (а„..., с«„)!и Е, машина й, будучи применена к основному коду для (с«„ ..., а„) н находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для 1(а„ ..., а„); при этом останов происходит над левой еДиниЦей коДа ДлЯ 1(!Ео ...,а„); 6) прн (!»о ..., а.)ФЕ, машина й, будучи применена к основному коду для (по ..., с«„) и находясь в начальном состоянии над его левой едпинцей, не останавливается.
Легко видеть, что машина (см. табл. (6) реализует 0(х) м 0 правильным образом. гл. ь вычпслпмыв э~пкцпн 145 Лемма 5. Если Дхь ..., я«) — вычислимая Яункция, то существует машина Тьюринга, которая вычисляет ее нравильным образом. Доказательство. Пусть %' — машина, вычисляющая функцию ~(яи ..., я„). Соответствующее преобразование записи ленты, положения головки и состояний обозначим через А'. Рассмотрим преобразование А = «К,А'р О«К«э. Здесь К,— преобразовапие кода для (ан ..., а.) в удвоенный код с буферным словом 01. На первой решетке будет код для (его ..., а„), на второй — сплошной массив из единиц. Х' — преобразование, моделирующее на первой решетке преобразование А'; вне этой решетки Л' в рабочей вове ставит символ 1.
р — предикат, выясняющий внд слова на первой решетке после работы оператора Л'. Просмотр слова осуществляется при помощи второй решетки, которая своим массивом нз единиц отмечает зону обследования на первой решетке. Полагаем р $, если слово является массивом из единиц, и р= О, если в слове найдутся две единицы, между которыми имеется нуль, или в нем нет единиц вообще. О,— преобразование, которое стирает все единицы на. второй решетке и останавливается над левой единицей слова, расположенного на первой решетке.
К, — преобразование квазиосновного кода в основной. Из'данной схемы видно, что в случае, когда после осуществления Таблица 17а преобразования Л' запись на первой решетке будет отлична от массива в из единиц, преобразование зацккливается, так как будет все время вычисляться предикат р. Машина бч, соответствующая пре- образованию А, и будет искомой. Лемма доказана, В дальнейшем для вычислимых функций будем использовать исключительно машины, вычисляющие их правильным образом. Теперь перейдем к описанию некоторых простейгпих вычислимых функций. Рассмотрим следующие функции: 440 ч, ь Фтпкцпоплльпьге спсткмы с опктлцпями $) копстапта 0; 2) о (х) = х+ 4; 3) 1" (г„..., х») = х, где $ - лг ( я.
Покажем, что данные функции вычислимы. Это уже сделано для константы О. Вычислпмость функций Я(х) и » 1~ следует из того, что оии реализуемы следующими машинами (см. табл. 17а, б). Машина для»'" (х„..., а„) идет направо (в начальном сосгояиии обозревается, как Таблица 1тб м» », О Оян»,+ ели Оьз +» 1Л»»» ОЕ»» ОЛ» Ода»+ 1Ьх„+ всегда, левая единица основного кода) и стирает все мас- сивы основного кода для (пь ..., а„), кроме т-го, ватем возвращается влево и встает над левой единицей остав- шегося массива. в 5. Операции С, Пр и )л На множестве Р"», определим три опе()ацпи: С (суперпозиция), Пр (примитивная рекурсия) и р (минимизация).
Операция суперпозиция вводится так же, как и для предыдущих функциональных систем: сначала определяется понятие формулы 6(х„..., х„) над данной системой функций из Р»; потом каждой формуле 6 сопоставляетч ся функция~и(х„..., х,), принадлежащая Р», .При атом, если па наборе (с»о ..., я.) окажется, что одна из фупкций, входящая в 6, будет неопределенной, то считаем, что ~и(с»м ° °, с» )будет также неопределенной. Болев точно, пусть Ф(х„..., х„) ~(~,(хо ..., х„), ..., ~ (х„..ч х„)).
»47 гл. ». вычпслпмык фгв»»ц»»п Возьмем произвольный набор (а„..., а ) чисел из расширеввого ватуральвого ряда. Если ва зтов» ваборе определевы Функции 1о ..., 1 и функция 1 определена ва наборе (Д(ао ..., а.), ..., 1«(ао ..., а.)), то Ф определена иа (а„..., а„) и Ф(а„..., а.) =1 (Л(а„..., а„), ... ..., 1 (и„ ..., а„)); в противном случае Ф ве определена ва наборе (а„ ..., и.). Операция примитивной рекурсии определяется следующим образом.
Пусть »г(х», ° , х ) и »(»(х», . ° 1 х»1 х»«», х»«») ) — про" извольяые функции из Р'„. Построим фувкцию Дх„... ... х„, х»«»), используя «схеь»у» примвтиввой рекурсии: ~(х„..о х., 0)=»р(х„..., х»), 1(х„..., х„, у+ 1)- »(»(х„..., х„, у, Дхм ..., х„, у)). Пусть (а„..
„а.+,) — произвольный набор чисел из Е„° Полагаем Дам .. «сс., 0)»р(сс,, ..., и„). Если »р ва атом наборе во определена, то считаем, что ве определена 1(ам ..., а„, О), а также ((а„..'„а„, у) при любом у, В противном случае полагаем »(а„..., а„, 1) = ф(и„..., а„, О, 1(а„..., а., О)). Если правая часть ве определепа, то считаем, что 1(а„..., а„, 1), а также ~(а„..., сс„, у) ве определены при любом у, у>1 и т. д. Через ковечвое число шагов мы либо определим »(а„..., а„, а„«,), либо уставовим, что ва этом наборе 1 ве определена. Из данного рассуждения видно, что если 1(а„ ... ..., а„, а„+,) ве определена, то при (1 > а„+, ие определена будет также и ((а„..., а„, б). Про функцию 1 будем говорить, что ова получена из функций »р и »у при помощи операции примитивной рекурсии.
Пример 7. Покажем, что функция 1(х<, х,) х,+ + х, может быть получена через примитквяую рекурсию из простейших вычислимых фувкцвй. «) Некоторые кз перев«язых у»о и»(» могут отсутствовать 143 ч. 1. ФънкционАльпыв спстю1ы с опкРАцпямн В самом деле, 1(Х„О) = 1, (х,), 1(х„у + 1) = Б (/(Х„У)). Замечание. Операция Пр позволяет для каждой ФУНКЦИИ 1Р(ХЬ ..., Хв) ВВОДИтъ НЕСУЩЕСТВЕННЫЕ ПЕРЕМЕН- иые, а именно: Дх„..., х., 0) 1р(хо ..., хв), 1(х„.', х„, у+1) Ч1(х» ..., х ).
Операция минимизации определяется следующим образом. Пусть 1р(х>, ..., Х„„х.) — произвольная функция из Рз; Построим функцию Дхо ..., х, х ) через оператор минимизации >У(Ху» Хв) = Ру(>Р(Х» ' .> Хв->> У) Хв)> что означает, что для произвольного набора (а„ ..., ав) составляется уравнение 1Р(а„..., а. „У) ав.' а) Если существует у из Ез, являющееся решением 0 этого уравнения, то берем минимальное иа решений и обозначим его через р„. Если значения 1р(а„..в а „0), ...; 1р(а„..., ссв „р„— 1) также определены, то полагаем 1(а„..., с1в „а.)= Р„. б) В противном случае, т. е. в случае, когда либо уравнение не имеет решений, либо хотя бы одно из значений 1р(а„ ..., ав о 0), ..., 1р(а„ ..в а о 11у- 1) не определено, функция 1(а,, ..., а.) также не определена.
Про функцию ( говорят, что она получена из функции ур прн помощи операции минимизации. П р и ы е р 8. Пусть 1р(х) = х+ 1. Определим через операцию )А функцию ~(х): 1 (х) = )гу (1Р (У) = х) . Ясно, что не определена прп х = О, х — 1 прп х>0, 1ру гл. 4. Вычислимые Функции Рар ~ Рч ~ Рчр ~ Ре Предыдущий пример показывает, что класс Р„существенно шире, чем класс Р,. Можно показать, что и класс Р, существенно шире, чем класс Р„. Рассмотрим примеры примитивно-рекурсивных функций. Возьмсы функции Яя(х), Яя(х), (х/2), 2", х,— 'х, и х,.х„ где (О при х = О, (1 при х = О, <1 при хчьО, й( ) <О при хФО, 0 при х, (хз, х,— 'х, х, — х, при х!) х,.
Функции [х/2], 2* и х, х, имеют обычный смысл; целая часть х/2, показательная функция и умножение. Их при- митивная рекурсивность вытекает из следующих соот- ношений: | Яу(0) = 1, Яу(х+ 1) = О, | 2' = 1, 2кы = 2 2*. < Яй(0) = О, Ян(х+1)=1, | ~ | ~ ~ ~ ~ ~ ~1 | в и х, 0=0, х, (х, + 1) = х х, + х„ Здесь константа 1 получается суперпозпцпей 0 и Я(т), х, +х, примитпвпо-рекурсивпа, а 2х получается из пес Данные операции позволяют построить трп следующие фуннциональные систеа!ы. 1. Множество Р„всех функций, которые мо)кно получить из системы функций! (О, Я(х), 1щ (х!, . ° ° ха). 1 а =!и~и, п=1, 2, ) при помощи операций С, Пр и р, называемое классом частично-рекурсивных функций. П.
Класс рекурсивных функций, т. е. множество Р, всех всюду определенных функций из Р„. П1. Класс примитивно-рек/!рсивных функций, т. е. множество Р„, всех функций, которые можно получить из системы (О, Я(х),1" (х„..., х„),1 ( т < п, и 1, 2, ) при помощи операций С и Пр. Очевидно, что 150 ч. е Функционзльные системы с ОпеРАциями суиерпозицпе11; 0-'4=0, ( х,-'0 х„ (х+1) — 1 х, х,-'(х,+1)=(х,— х )-1, Здесь х — ' 1 — вспомогательная функция. Данные примитивно-рекурсивные функции позволяют строить многие другие примитивно-рекурсивные функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
