Ш.И._Галиев_МЛ_и_ТА_2004

неразрешимость Этих задач. Для каждой конкретной задачи, налример. для каждого данного слот Р может быть и можно выяснить, применим х нему данный нормальный алгоритм или нет, но нет алгоритма, позволяющего выяснить применимость любого нормаль­ ного алгоритма к любому слову. Эго означает, что рассматриваемый класс задач достаточно обширен и надо как-то разумно делоть их на подклассыи искать для них разрешающие алгоритмы.

2.Теоремы об алгоритмической неразрешимости показывают, что математика не сводится к построениюалгоритмов.

3.Область применения алгоритмов весьма широка и к ней

относятся не тольхо вычислительные процессы. Более того, дли многих проблем, ечнгяюишхея трудными, теоретически построить алгоритм можно, но его реализация сопряжена с очень долгим счетом и необходимостью запоминать большое количество промежуточных результатов. Создание быстродействующих вычисли]ельных машин значительно расширило круг решаемых задач.

§14. Съедение любого преобразования слив в алфавите

квычислению значений целочисленных функций

Пусть А - алфавит, содержащий п букв. Поставим в соот­ ветствие каждой буква а (аеЛ) число (гсделев номер) g(я) из чисел 1,2,...,«, причем различным буквам пасшим в соответствие различные числи Оеделевы номера). Очевидно, что по каждому g(fl) всегда можно восстановить букву. Если задано некоторое слово Р,

например, PmOHaa...a-m(fltfiA'). то сопоставим ему геделев номер:

£(Р)-2*'	'
где bi-giaj и дт -	т-е простое число. Легко видеть, что таким

образом можно определить геделев номер каждому слову Р и по каждому геделеву номеру g{Р) легко восстановить слово, которому соответствует этот номер.

Пример. Пусть А={а,Ь,с). Тогда можно положить g(<i)=l, , g[c)=3. Если P=aabn, то £(/)=2^3^5^71. Если же задаю 251

число .^18, то, представив 18 в виде произведения степеней простых чисел 18=2 *32, получаем, что 18 является гедапевым номером слова

Q-ab.

Пусть задана последовательность слов в алфавите А, которую можно, например, назвать предложением в алфавите А. Тогда этой последовательности слов можно сопоставить последовательность гедслсвых номеров каждого слова в том же порядке, что и слова, либо, считая, что пробел между словами имеет геделев номер (л+1), сопоставить всей последовательности один геделев номер. Напричер, пусть А={а.Ь.с) и задана последовательность слов Р=аЬЬ cabb ею,

тогда либо

HiP'rticbb). g(cabb). &ап) w2'*35‘ 55, 2 ^ 3 ^ - 7 5. г'ГЗ1.

^ )- 2 ^ 3 ^ 5 ^ 7 ^ 1 IJ*13'M7!*19!*23**291+3 I1.

Ясно, что в данных случая» по данному номеру или последо­ вательности номеров можно единственный образом восстановить исходную последовательность слов (предложение).

Как только проведена нумерация, становится понятным, что любое преобразование слов или предложений в алфавите А в слове или предложенииЛ можно свести к вычислению значений функции

И” <р(й) или ¢1= 41(¾¾...¾).

где п,7|],Ч)....я* - геделевы номера преобразуемых слов или пред­ ложений, a m - геделев ноиер результата. Это следует из того, что после введения нумерации можно имгть дело у»е только с соответст­ вующими номерами слов нли предложений а не с самими словами или предложениями.

Очевидно, что еоли у нас есть метод преобразования слов (предложений) алфавит» А. то ecib и метод вычисления значений соответствующей функции. Действительно, чтобы нейти значение <р(л) при я=а, можно по а восстановить слово (предложение), затем : помощью имеющегося метода преобразовать ею в слово, явлвяющееся результатом и по результирующему слову (предложению) найти геделев номер <р(«). Следовательно, ф(а)=р.

Наоборот, если есть метод вьгчио.теш* функции 4>(л), го. стало быть, имеется в метод преобразования исходное олова (предло­ жении). Действительно, по записи слова (предложения) мшюго найти соответствующий ему номер а, затем иичислип. |5“ ip(o) и по |! оирсдеиить результирующее слово (предложение).

Тахиы образом, всякое преобразование слон или предложений a:iфаввггаА в слова или предложения того же ллфаииго мпжиа свести к вычислениюзначении некоторой функции, и наоборот.

Раисе «рели всевозможный преобразований слов алфавита пас интересовали преобразования, которые используют механическую процедуру, т.о. преобразовании с помолдао алгориггмоп. П слелу'о- щем и-фаграфс займемся изучением функций, значения которых вычисляются с помощью некоторых ’’механических" процедур, и уста­ новим связь с вычислимостью при помощи нормальных вягорщ-мпи.

§15. Примитивно рекурсюипдс

пойщерскурснкные функции

Рекурсивное определение функции - зю, грубо голоря, опреде­ ление, в котором «начечил функции дао данных api-yMeirron непо­ средственно определяются значениями этой тке функции для "Полос Простых" apiyMBwrou или значениями "болсс ироешх" функций. (Понмтав ''более простой" следует уточните: например, простейшей функцией можно считать функцию-константу). Такой подход е рас­ смотрению функций удобентем, что рекурсивные онреде.'юинхможно рассматривать как алгоритмы.

Здесь, как и Ери определении вычислимости по Маркову или Тыорннту, будем рассматриватьтолько арифметические функции.

Теперь приступим к строгому определению ириштитюрекурсивных а общерекуренвных функций.

1. Следующие функции называются исходными (ироешШими)

функшими:

1)MV.IL функима: 2(.г>=0 ори V i (ikO),

2) функция прибавления единицы: при 9*(д£0), ясно, что. используя функции 2 и ,V. можно получил, любую функциюконстанту, например:

2-N№Z(x))),

з

3) проектирующие функции J" при ясех

,i^C (;-1,2,...,и;*=],2,...)

2. Следующие ираьита служат для получения ковы* функций,

исходе ю У** имеющихся функций.

Подстатяха:

тогаа говорят, что

функция/ получена с- помощыоподстановкииз функцийк,й|,й},..,

Рекурсия:

	yj[x„ * ,	00, ). ,. . , * „
при этом исключается с л	уп=0,ч дляа йкоторого:
б)	массированноецелое неотрицательное число.
Будем гоеорнть, что » случае а) функция/		получина ю g	и А
с помощью рекурсии, a	- параметры рекурсии, а ■		слу­
чае б)-из одной функции А с.помощью рекурсии.

254

Заметам, т е фуикшм/всегда определена: в случив и] значение определялся н: t-ro равенства, далее, если шаек

А *'Л ,-г1лУ). Ю 2-го равеиетет опредааеи fatA p.Jbj*)). анало­

гично в ля> случая б).
V-оператор;
пусть функция	-	ijKMia, что для любых Я|^еь-«х„

существует, но крайней мере, одно значение у, при котором 8(А^5....W H -

Обозначим через \iy(g{x\xi,--Jnj')^) наименьшее значение >,

при котором
Пусть	-.^«vJ-O). Будем тогда rowpro,

что функция / получена и-s функции g с помощью ^--оператора, ссли ля* любыхЛ|.Х; х„ Gyiuecmye'r по крайней мере одно значение у* ДЛЯ

которого

5(ЯГ;J?. ..Г-О-И

Функция налыаастся примгаяидно-рехурсивкой, если она может быть получена из исходныхфункций 1). 2) и 3) с помощью конекнот числа подемноеок и рекурсий.

Функция / называется общерекурситой. «ли он» может быть получена ю йипдлык функций I), 2) и 3) о помощью коШ’Моги'ГНС1и “оистановок, рекурсий и ц-оперитсри. ОбщгрекурсНЛные функции нногда называют р!курсивными функциями.

Из определений очевидно, что каждая примитавко-рскурсивт а функция яалиегся общср^курсивной, но нииаобираг.

Отметим. ‘Гто иршисгавно и эбщерекурсивные функции явля­ ются всюду определенными функции*, так как исходные фунпми всюду определены, а подстановки, рекурсии и ц-оператир не меняет всюду определенности.

2SS

§ I6. Примитивпо-рекурсивносп. некоторых функций, '{асснчил-рскурснслме фушецив

Теорема 6.8. Следующие фуикиии ямяет-гся примнт рекурсикными;

1) х+у;	2) х*у;
	т-1 ,вслид>0,
г) А	4) ад=
х-у, *>?,	г*-у,
{	б) M -J
), х<у;	I у-Х. Х<у\
0,х-0,	[1,1=0,
{	*)*•<*)- 4
,х*к	i.0, wO;

S) гш(х,у) равна остатку отдеюникунаг, 10) lt{y.,y) равна часпгаму отделения)! нах; 11)х1; 12)шт(х,>); 13)пи»(ад...,;0;

14)max(jy0;

15)max(xiAV

Докичтелылвп. 1. Обозначим первое функцию через/ Hues Л,0)“ЖН1)-Я--,;,'{*), ЛЯ-1)=^+-1)=={л-1'у>+1=Лз:7)41=ЗДад))=Л<^ДЛу)), где

В результате jfy,y)r*+y получается рекурсией из примитивнапвкурсивных функций W и h(x,y,z)=jV(r), следовательно,/ - примитивно-рекурсивна.

2. Обозначим функцию умножения х над> через i|i.Тогда V (x.0)^0 = 0 = Z(x);

1де h \x jv ) ~К!-Л Итак, 'K V ) пвяучастся рекурсией из примитивно рекурсивных функций g f(x)=Z(x) и следоватеньно,

функция ц;-примитивно-рекурсивна, 3. Обозначим функцию втвед*иич в степень ПЕрезф. Для ариф­

метических функций полагаем, что х°=1 для любых целик х, в том

числе и для 1=0, т. е. ОМ (¢(0,0)=1). Получим

Ф(*.0)-*"-1-А'(ДхВ;

ф ,у+ № '^*х= < ?(х,у)ш х™ 4ф ,у)^к‘ \х,у1ц(х,т,

где Л*"(х^>г) ” V(rt/,z), т.е,	ф получается рекурсией из примитивно-
ргкуреивных функций й,	*{г)=Л,(Дх)) и	у,гу=^х,г), следова­

тельно, ¢ )-примитивно-рекурсивна.

Аналошчным образом доказывается и для функций 4)~15).

Из теоремы следует, что примитивно-рекурсивные функции образуют достаточно широкий масс всюду определенных функций.

Рассмотрим, кик можно вычислять значения примитивно рекурсивны' функций. Каждая 1гримишцно-рЕкурсивкья функция получаемся из исходных функций 1), 2) и 3) с помощью конечного I числа подстановок и рекурсий Представление функции с помощью

__J подстановки и рекурсии, примененных к исходным функциям, можно рассматривать как набор инструкций д и "механического" выиислеии» значения функций. Следовательно, доказательство примитивно-р>гкур- снвности функции является одниьременно доказательством сущест­ вования алгоретма вычисления значений функций. Рассмотрим, например, функцию у(*.у)=л«>). Установлено, что

4-(¾.0) = Z(3e>=0; у(*,)+})=АУ М Л гдвЛ^Й-*+1’.

Таким образом, значение у(х.>) при >=0 определено. Зная значение этой функции при некоторых х и у, можем определить значение этой функции при * иу+1, используя уже схему вычисления значений функции.^*,)'), для которой значение приj=0 известно, а при у>0 можно выразить через функцию N, зависящую от аргумен­

та	1) и т.д.
	Итак, ехгму задания примитивно-рекурсивны): функций можно

рассматривать как процедуру вычисления ее значений. Вычисление се чначений определяется схемой достаточно просто, явно и осущест­ вляется иеканическим образом.

! Теорема 6.9. Мкижкмво примитнино-рекурсивных функций является счетным множеством, множество общерекурсивных функций тоже является счетным множеством.

Доказательств. Все функции константы - примитаино-рекур- сиины. следовательно, и общерекурсивны. Тогда их не меньше, чем счетное множество. Доказательство того, что их не Волсе чем счетно, приводется с помощью гвделевой нумерации, т.е. удается покмать, что каждой о5шерекурсивной функции можно соноиавить кекпгарое целое неотрицательное число (геделев номер)! причем различным функциям сопоставляются различные числа. Из этой нумервши и спелугг, 1гго пбщерекурсианых функции не более чей счетное '/ножество.

Можно доказать следующую теорему.

Теорема 6.10. Существуют арифметические всюду опреде­ ленные функции, Не являющиеся общерекурсиеиыхш функциями.

Функций (р от п аргументов называется частично-рекурсивной, если она может быть получена яз исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и ц‘-оператора, где д‘-операгор определяется так же, как и ji-оператор, но уже

258

не требуется, чтобы для V*],V%...,Vx„ существовал у такой, *сго т.е. при некоторых значениях Х\Хъ.. может и

не сущесгзоватьутиного, что к к м ... w H -

Очевидно, что всякая общерекурсивни функция является частичка рекурсивной, но tie наоборот. Можно доказать следующи: важные теоремы.

Теорема 6.11. Всякая частичио-рехурсиаяая функция (общергкурснпиая) авлятая частично вычислимой (вычислимой) по Маркину функций.

Теорема 6.12. Всякля частичная функция, частично вычис­ лимая (вччислимаа) по Маркову, является чаетиччо-рехурыиной (общерекурсивнои) функцией.

§ 17, Ламода-исчпсление

Прежде чем ввести памбаа-исчисление, укажем возможную область ее использования в вычислительных моделях.

логические вичтпытеяывле модели, основанные HJ вычиелгниях с помощью логики предикатов. Примеры таких язиков ПРОЛОГ,

ДЕЙТАЛОГ;

фуикцитатые вычислительные «одели, s которых Програм­ ма рассматривается как ыножесгво определений функций. В основу

259

этой модели положено так называемое «ламбда-исчислвние». Приме­ ром ячикв, основанного па ламбда-исчислении, имеется 436IK ЛИСП;

обьектю-ориентфаеанные вычислительные модели. В импера­ тивных (процедурных) и функциональных вычислительных моделях операция принимается за субъект, а вычисления првдставлякзтся в ви­ де использования операций с некоторыми объемами. Однако если сделать наоборот, т.е. объект операции принять за субъект, а приме­ нение операции рассматривать как передачу запроса объекту, который и выполняет ату операцию, то тикая модель является объектноориентированной, т.е. объект рассматриваются как процессы. Реви­ зована в языках PLASMA, MESA, LOOPSи др.

Теперь перейдемк некоторымпонятиям ламбда-исчислсния. Ламбда-исчисленис было введено Черчем как один из подходов

для обосновании логики и математики. В дальнейшем часть этого ис­ числения явитсь одной из теорий вычислений.

Лямбда-исчисление - это теория, рассматривающая функции как правша, а не как графики и фактически выделяющая вычисли­ тельный аспект при введении функций.

Ч5рч предложил использоватьламбда-исчисленнг для формали­ зации понятия эффективной вычислимости Тьюринг показал, что вы­ числимость по Тьюрингу эквивалентна ламбда-вычислимости. Таким образом, несмотря на свой ичень простой синтаксис, гамбда-исчи- сление способна реализовать все механически вычислимые фукмщи.

Выражение в лямбда-иочислении представлено в префиксной форме, т.е. вначкле располагается оператор, например, вместо а+Ь

пишется +аЬ. а вместо a/b+Ыс пишется (+(lab){xbc)).

Все программы представляются с виде выражений, а процесс выполнения программы заключается в определении шачения этого выражения и это называется оценкой выражвкия.

Оценка выражения производится повторением операции выбора и упрощением тех частей этого выражения, которые можно

260