Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 4
Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
Пусть А - алфавит, содержащий n букв. Поставим в соответствие каждой букве число (геделев номер) g(a) из чисел 1,2,...,n, причем различным буквам поставим в соответствие различные числа (геделевы номера). Очевидно, что по каждому g(a) всегда можно восстановить букву. Если задано некоторое слово Р, например, P=ak1ak2...akm ), то сопоставим ему геделев номер:
,
где bi=g(aki) и qm - m−е простое число. Легко видеть, что таким образом можно определить геделев номер каждому слову Р и по каждому геделеву номеру g(P) легко восстановить слово, которому соответствует этот номер.
Пример. Пусть А={a,b,c}. Тогда можно положить g(a)=1, g(b)=2, g(c)=3. Если P=ааbа, то g(P)=21*31*52*71. Если же задано число N=18, то, представив 18 в виде произведения степеней простых чисел 18=2 *32, получаем, что 18 является геделевым номером слова Q=ab.
Пусть задана последовательность слов в алфавите А (которую можно, например, назвать предложением в алфавите А). Тогда этой последовательности слов можно сопоставить последовательность геделевых номеров каждого слова в том же порядке, что и слова, либо, считая, что пробел между словами имеет геделев номер (n+1), сопоставить всей последовательности один геделев номер. Например, Пусть А={a,b,c} и задана последовательность слов Р=аbb саbb аа, тогда либо
g(P)=g(abb), g(cabb), g(aa) = 21*32*52, 23*31*52*72, 21*31
либо
g(P)=21*32*52*74*113*131*172*192*234*291*311.
Ясно, что в данных случаях по данному номеру или последовательности номеров можно единственным образом восстановить исходную последовательность слов (предложение).
Как только проведена нумерация, становится понятным, что любое преобразование слов или предложений в алфавите А в слова или предложения А можно свести к вычислению значений функции
m= ϕ(n) или m= ϕ (n1,n2,...nk),
где n,n1,n2,...,nk - геделевы номера преобразуемых слов или предложений, а m - геделев номер результата. Это следует из того, что после введения нумерации можно иметь дело уже только с соответствующими номерами слов или предложений, а не с самими словами или предложениями.
Очевидно, что если у нас есть метод преобразования слов (предложений) алфавита А, то есть и метод вычисления значений соответствующей функции. Действительно, чтобы найти значение ϕ(n) при n=α, можно по α восстановить слово (предложение), затем с помощью имеющегося метода преобразовать его в слово являющееся результатом и по результирующему слову (предложению) найти геделев номер ϕ(α). Следовательно, ϕ(α)=β.
Наоборот, если есть метод вычисления функции ϕ(n), то, стало быть, имеется и метод преобразования исходного слова (предложения). Действительно, по записи слова (предложения) можно найти соответствующий ему номер α, затем вычислить β=ϕ(α) и по β определить результирующее слово (предложение).
Таким образом, всякое преобразование слов или предложений алфавита А в слова или предложения того же алфавита можно свести к вычислению значения некоторой функции, и наоборот.
Ранее среди всевозможных преобразований слов алфавита нас интересовали преобразования, которые используют механическую процедуру, т.е. преобразования с помощью алгоритмов. В следующем параграфе займемся изучением функций, значения которых вычисляются с помощью некоторых "механических" процедур, и установим связь с вычислимостью с помощью нормальных алгоритмов.
Примитивно рекурсивные и общерекурсивные функции
Рекурсивное определение функции - это, грубо говоря, определение, в котором значения функции для данных аргументов непосредственно определяются значениями этой же функции для "более простых" аргументов или значениями "более простых" функций. (Понятие "более простой" следует уточнить: например, простейшей функцией можно считать функцию-константу). Такой подход к рассмотрению функций удобен тем, что рекурсивные определения можно рассматривать как алгоритмы.
Здесь, как и при определении вычислимости по Маркову или Тьюрингу, будем рассматривать только арифметические функции.
Теперь приступим к строгому определению примитивно рекурсивных и общерекурсивных функций.
1. Следующие функции называются исходными (простейшими) функциями:
1) нуль функция: Z(x)=0 при ,
2) функция прибавления единицы: N(x)=x+1 при , ясно, что, используя функции Z и N, можно получить любую функцию-константу, например:
1=N(Z(x)),
2=N(N(Z(x))),
3=N(N(N(Z(x)))),
. . . . . . . .
3) проектирующие функции Jin (x1,x2,...,xn)=xi при всех x1,x2,...,xn≥0 (i=1,2,...,n; n=1,2,...)
2. Следующие правила служат для получения новых функций, исходя из уже имеющихся функций.
Подстановка
f(x1,x2,...,xn)=g(h1(x1,x2,...,xn),...,hm(x1,x2,...,xn)), тогда говорят, что функция f получена с помощью подстановки из функций g, h1, h2,..., hm.
Рекурсия
при этом исключается случай n=0, для которого:
В случае а) будем говорить, что функция f получена из g и h с помощью рекурсии, а x1,x2,...,xn - параметры рекурсии.
В случае б) говорят, что функция f получена из одной функции h с помощью рекурсии.
Заметим, что функция f всегда определена: в случае а) значение f(x1,x2,...,xn,0) определяется из 1-го равенства, далее, если мы знаем f(x1,x2,...,xn,y), то из 2-го равенства определяем f(x1,x2,...,xn,y+1), аналогично и для случая б).
µ - оператор:
пусть функция g(x1,x2,...,xn,y) такова, что для любых x1,x2,...,xn существует по крайней мере одно значение у, при котором g(x1,x2,...,xn,y)=0.
Обозначим через µy(g(x1,x2,...,xn,y)=0) наименьшее значение у при котором g(x1,x2,...,xn,y)=0.
Пусть f(x1,x2,...,xn)=µy(g(x1,x2,...,xn,y)=0). Будем тогда говорить, что функция f получена из функции g с помощью µ-оператора, если для любых x1,x2,...,xn существует по крайней мере одно значение у, для которого
g(x1,x2,...,xn,y)=0.
Функция называется примитивно рекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий.
Функция f называется общерекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и µ-оператора. Общерекурсивные функции иногда называют рекурсивными функциями.
Из определений очевидно, что каждая примитивно рекурсивная функция является общерекурсивной, но не наоборот.
Отметим, что примитивно и общерекурсивные функции являются всюду определенными функциями, так как исходные функции всюду определены, а подстановки, рекурсии и µ-оператор не меняют всюду определенности.
Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
Теорема. Следующие функции являются примитивно рекурсивными:
Доказательство.
1) Обозначим первую функцию через f. Имеем
f(x,0)=x+0=x=J11 (x),
f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1=N(f(x,y))=h(x,y,f(x,y)), где h(x,y,z) = N(z).
В результате получили, что f(x,y)=x+y получается рекурсией из примитивно рекурсивных функций g(x)=J11(x) и h(x,y,z)=N(z), следовательно, f - примитивно рекурсивна.
2) Обозначим функцию умножения х на у через ψ . Тогда
ψ(х,0)=х•0 = 0 = Z(x);
ψ(x,y+1)=x•(y+1)=x•y+x=ψ(x,y)+x=f(ψ(x,y),x)=h*(x,y,ψ(x,y)),
где h*(x,y,z) = f(x,z). Итак, ψ(x,y) получается рекурсией из примитивно рекурсивных функций g*(x)=Z(x) и h*(x,y,z)=f(x,z), следовательно, функция ψ - примитивно рекурсивна.
3) Обозначим функцию возведения в степень через ϕ. Для арифметических функций полагаем, что х0=1 для любых целых х, в том числе и для х=0, т. е. 00=1 (ϕ(0,0)=1). Получим
ϕ (x,0)=xo=1=N(Z(x));
ϕ(x,y+1)=xy+1=xy•x=ϕ(x,y) •x=ψ(ϕ(x,y),x)=h**(x,y,ϕ(x,y)),
где h**(x,y,z) = ψ(x,z), т.е. ϕ получается рекурсией из примитивно рекурсивных функций g**(x)=N(Z(x)) и h**(x,y,z)=ψ(x,z), следовательно ϕ - примитивно рекурсивна.
Аналогичным образом доказывается и для функций 4)-15).
Из теоремы следует, что примитивно рекурсивные функции образуют достаточно широкий класс всюду определенных функций.
Рассмотрим, как можно вычислять значения примитивно рекурсивных функций. Каждая примитивно рекурсивная функция получается из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий. Представление функции с помощью подстановки и рекурсии, примененных к исходным функциям, можно рассматривать как набор инструкций для "механического" вычисления значения функций. Следовательно, доказательство примитивно рекурсивности функции является одновременно доказательством существования алгоритма вычисления значений функций. Рассмотрим, например, функцию ψ(х,у)= х•у. Выше установлено, что
ψ(х,0) = Z(x)=0;
ψ(x,y+1)=f( ψ (x,y),x), где f(x,y)=x+y.
Таким образом, значение ψ(х,у) при у=0 определено. Зная значение этой функции при некоторых х и у, можем определить значение этой функции при х и у+1, используя уже схему вычисления значений функции f(x,y), для которой значение при y=0 известно, а при у>0 можно выразить через функцию N, зависящую от аргумента f(x,y-1) и т.д.
Итак, схему задания примитивно рекурсивных функций можно рассматривать как процедуру вычисления ее значений. Вычисление ее значений определяется схемой достаточно просто, явно и осуществляется механическим образом.
Теорема. Множество примитивно рекурсивных функций является счетным множеством, множество общерекурсивных функций тоже является счетным множеством.
Доказательство. Все функции константы - примитивно рекурсивны, следовательно, и общерекурсивны. Тогда их не меньше, чем счетное множество. Доказательство того, что их не более чем счетно, приводится с помощью геделевой нумерации, т.е. удается показать, что каждой общерекурсивной функции можно сопоставить некоторое целое неотрицательное число (геделев номер), причем различным функциям сопоставляются различные числа. Из этой нумерации и следует, что общерекурсивных функций не более чем счетное множество.
Можно доказать следующую теорему.
Теорема. Существуют арифметические всюду определенные функции, не являющиеся общерекурсивными функциями.
Функция ϕ от n аргументов называется частично рекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и µ‘ -оператора, где µ‘ - оператор определяется так же, как и µ -оператор, но уже не требуется, чтобы для существовал у такой, что g(x1,x2,...,xn,y)=0, т.е. при некоторых значениях x1,x2,...,xn может и не существовать у такого, что
g(x1,x2,...,xn,y)=0.
Очевидно, что всякая общерекурсивная функция является частично рекурсивной, но не наоборот. Можно доказать следующие важные теоремы.
Теорема. Всякая частично рекурсивная функция (общерекурсивная) является частично вычислимой (вычислимой) по Маркову функцией.
Теорема. Всякая частичная функция, частично вычислимая (вычислимая) по Маркову, является частично рекурсивной (общерекурсивной) функцией.
Ламбда-исчисление
Прежде чем ввести лямбда-исчисление укажем возможную область её использования в вычислительных моделях.
Различают следующие вычислительные модели:
императивную (процедурную) вычислительную модель (императив – повеление, требование), когда имеется последовательная система команд. Языки программирования, такие как АЛГОЛ, ФОРТРАН, С и т.п. основываются на этой вычислительной модели и объединяются под названием императивные или процедурные языки;
логические вычислительные модели, основанные на вычислениях с помощью логики предикатов. Примеры таких языков Пролог, Дейталог, Параллельный Пролог;
функциональные вычислительные модели, в которых программа рассматривается как множество определений функций. В основу этой модели положено мак называемое «ламбда-исчисление». Примером языка, основанного на ламбда-исчислении, является язык ЛИСП;
объектно-ориентированные вычислительные модели. В императивных (процедурных) и функциональных вычислительных моделях операция принимается за субъект, а вычисления представляются в виде использования операций с некоторыми объектами. Однако если сделать наоборот, т.е. объект операции принять за субъект, а применение операций рассматривать как передачу запроса объекту, который и выполняет эту операцию, то такая модель является объектно-ориентированной, т.е. объекты рассматриваются как процессы. Реализованы в языках PLASMA, Mesa, LOOPS и др.
Теперь перейдем к некоторым понятиям ламбда-исчисления.
Ламбда-исчисление было введено Черчем около 1930 года как один из подходов для обоснования логики и математики. В дальнейшем часть этого исчисления явилось одной из теорий вычислений.
Ламбда-исчисление – это теория, рассматривающая функции как правила, а не как графики и фактически выделяющая вычислительный аспект при введении функций.
Чёрч предложил использовать ламбда-исчисление для формализации понятия эффективной вычислимости. Тьюринг показал, что вычислимость по Тьюрингу эквивалентно ламбда-вычислимости. Таким образом, несмотря на свой очень простой синтаксис, ламбда-исчисление способно реализовать все механически вычислимые функции.
Синтаксис ламбда-исчисления.
Выражение в ламбда-исчислении представлено в префиксной форме, т.е. вначале располагается оператор, например, вместо а+b пишется +аb, а вместо а/b+b×с пишется (+(/аb)(×bс)).
Все программы представляются в виде выражений, а процесс выполнения программы заключается в определении значения этого выражения и это называется оценкой выражения.
Оценка выражения производится путём повторения операции выбора и упрощения тех частей этого выражения, которые можно упростить. Такая часть выражения называется редексом, а операция упрощения называется редукцией.
Процесс редукции завершается, когда выражение, преобразованное редукцией, не содержит больше редекса. Выражение, не содержащее редекса, называется нормальной формой.
Например, при оценке выражения (+(/62)(×25)) сначала выбираются редексы и упрощаются соответственно до 3 и 10. Полученное выражение (+3 10) также является редуцируемым, поэтому имеем
(+3 10)→13.
Результат (оценка выражения) 13 невозможно упростить, поэтому он считается нормальной формой.
Применение функции. Применение функции f к аргументу x обозначается как (fx). Функция от нескольких аргументов представляется, например, следующим образом (f(x,y,z)). Однако функцию от нескольких аргументов можно интерпретировать как результат синтеза функций от одного аргумента. Например (+3 4) можно интерпретировать как (+3)4, т.е. как прибавление тройки к аргументу 4.
Ламбда-абстракция – это одно выражение, определяющее функцию. Например, выражение
(λx.+x1)
определяет функцию прибавления к переменной x единицы. Запись λx. показывает, что это выражение является ламбда-абстракцией, формальным параметром которой является x. Выражение, которое следует за точкой (в данном случае это +x1) является телом ламбда-абстракции.
Рассмотрим следующее ламбда-выражение:
(λx.+xy)3
Здесь x считается связанной переменной, 3 значением для x.
Для оценки этого выражения необходимо, чтобы переменная y уже имела какое-либо значение. Обычно значение свободной переменной определяется во внешнем выражении, содержащем это выражение.
β - преобразование
Пусть имеем выражение (λx.+x1)4, в котором записаны последовательно лямбда-абстракция (λx.+x1) и аргумент 4. При замене x на 4 получим (+4 1). Это правило преобразования называется β - преобразованием.
Примеры β - преобразований:
(λx.+x1)4→+4 1
(λx.+xx)5→+5 5→10
(λx.3)5→3
(λx.(λy./yx))2 6→(λy./y2)6→6 2→3
(λf.f3)(λx.+x1)→(λx.+x1)3→+3 1→4,
где (λx.+x1) – аргумент для предыдущей ламбда-абстракции.
Кроме того в ламбда-исчислении вводятся α - преобразование, η -преобразование, рекурсии и т.д.
Если выражение содержит несколько редексов, то возможно одновременное их оценивание, например, если имеем (х (+3 5) (– 5 2)),
то можно представить это выражение в виде следующего графа, см. Рис.
Посредством параллельной редукции всех редексов можно увеличить скорость вычислений. При этом появляется возможность параллельной обработки, и имеются следующие преимущества по сравнению с процедурными языками.
(1) Графовая структура ламбда-исчисления позволяет выявить редексы для параллельной обработки.
(2) Нет необходимости в централизованном управлении операциями редукции, которые нужно делать для процедурных языков.
(3) Связь между редексами можно выполнить полностью унифицировано.
В процедурных языках задачи распараллеливания вычислений требуют специальных программ, в том числе и синхронизацию (по времени) этих вычислений. В языках с ламбда-исчислением этого не нужно. Сама структура программы однозначно определяет оптимальное число параллельных ветвей вычислений.