Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы, страница 3

По определению:А1×А2×А3=(А1×А2)×А3=А1×(А2×А3)А 1 × А 2 ×....× А k-1×А к = ( А 1 × А 2 ×....× А k-1) × А кЛегко дать "прямое" эквивалентное определение декартова произведенияА 1 × А 2 × ... × А ккак множества всех "кортежей" a 1, a 2, ..., a k длины k, где a i ∈ А i, i = 1,2,...,k.В случае, когда А 1= А 2= ... = А k= А, обозначаем декартово произведениеА1 × А2 × ... × А k как Аk ( A × A = A 2, A × A × A = A 3 и т.д.) Особый интерес для наспредставляет случай, когда множество А конечно, т.е. состоит из конечного числаэлементов:А = { a 1 , a 2 ,..., a p }Мы будем называть такое множество алфавитом (абстрактным), а его элементы символами. Множество, образованное объединением всех Аk, где k = 1, 2, ..., и одногоидеального элемента, называемого "пустым словом", будем обозначать через A* .Элементы из A* - конечные слова (цепочки символов) в алфавите А.

Для каждого словаw ∈ A* естественно определяется длина слова - число символов, образующих это слово.Длина пустого слова считается равной нулю. Длина слова w обозначается w. Еслипредставить себе, что алфавит А = { a 1, a 2,... , a p } содержит не только все буквыестественного языка, но и знаки препинания, пробела, переноса, цифры, специальныезнаки, используемые в текстах, а также знаки, обозначающие концы строк, страниц и т.д.,то среди элементов множества A* окажутся все мыслимые конечные тексты. Любойконечный текст будет "словом" в алфавите А и, следовательно, любая информация,описанная конечным текстом, может быть изображена "словом" в алфавите А.Дело, однако, не в том, что нами выбран такой обширный и удобный алфавит.

Легкопоказать, что при помощи даже так называемого побуквенного кодирования (т.е. заменыкаждой буквы алфавита А определенным словом в алфавите В), любое слово в алфавите Аможет быть представлено словом в алфавите В, если последний содержит не менее двухсимволов.

Из дальнейшего изложения будет следовать существование простогоалгоритма, определяющего взаимно-однозначное отображениеA*B*для любой пары алфавитов А и В.Следовательно оказывается, что любой алфавит, в том числе и однобуквенный, впринципе, пригоден для изображения информации соответствующими словами.8Таким образом задача обработки информации сводится к нахождению значенийнекоторого частичного отображенияA*A*,где А = { a 1 , a 2 , ... , a p } - конечный алфавит, а А* - множество конечных слов в этомалфавите.Среди частичных отображений A*A* нас будут интересовать, в первую очередь,отображения, значения которых могут быть получены процессами преобразований,определяемыми алгоритмами. Одной из задач, связанных с исследованием частичныхотображений, оказывается задача установления принадлежности того или иногочастичного отображения А*A* к интересующему нас классу.Аналогичная задача давно возникла в математике в связи с заданием целочисленныхфункций целочисленных аргументов, являющихся частичными отображениями NNили N × N × ....

× N ---> N, где N - множество неотрицательных целых чисел { 0, 1, 2,... }, ивозможной их вычислимостью, т.е. с возможностью получать значения функций врезультате некоторой цепочки вычислений.Интуитивно понятие вычислений тесно связано с понятием алгоритма, прежде всегопотому, что вычисления являются частным случаем процессов преобразованияинформации - информации, представленной в форме чисел.Однако оказывается, что к этому частному случаю может быть сведен любойалгоритм.Прежде всего установим связь частичного отображения A* ---> A* с частичнымифункциями NN. Установим следующее взаимно-однозначное соответствие, котороеможно назвать нумерацией ( # ) :#A*Nтак, что по слову w ∈ A* можно было бы определить соответствующий ему номер #(w) инаоборот, по номеру можно было бы определить получившее этот номер слово.

Пустомуслову λ присвоим номер ноль (число). Однобуквенному слову а i присвоим номер i для i =1, 2,....,р. Слову w = a i0а i1а i2....а is присвоим номерNw = i 0 + i 1 x p + i 2 x p 2 + ....+ i s x p s .Нетрудно доказать, что выбранная нумерация обладает требуемыми свойствами, а ееналичие подтверждает существование вычислимого взаимно-однозначного отображенияA* --> В* для любой пары алфавитов А и В.Для каждого отображения F : A*-- F --> А* отображение # индуцирует (порождает)отображение: f : N --- f---> N и для каждого отображения N -- f-->N отображение #индуцирует отображение F из A* в A* в соответствии с диаграммой:Ограничиваясь отображениями, порождаемыми алгоритмами ифункциями, этот результат можно сформулировать следующим образом:вычислимыми1) Каждый алгоритм, определяя частичное отображение А*определяет вычислимую функцию NА* ,N , где f(n) = #(F(w)) для n = #(w).92) Каждая вычислимая функция f(n) : NN определяет алгоритм(частичное отображение на множестве слов алфавита A) А*которого # (F(w)) = f(#(w)).А* , для4.

ВЫЧИСЛИМЫЕ ФУНКЦИИ И ТЕЗИС ЧЕРЧАВопрос о вычислимости целочисленных функций, целочисленного аргумента, еслиговорить совсем кратко, решен следующим образом. Признано (тезис Черча), чтосовокупность всех вычислимых частичных функций совпадает с совокупностью такназываемых частично-рекурсивных функций, т.е. функций, которые можно построить изнабора совсем простых функций путем использования трех четко определенныхопераций: суперпозиции, примитивной рекурсии и минимизации.В качестве исходных простых, считающихся вычислимыми по определению, могутбыть взяты :1) Тождественно равная нулю функция О(х) = О2) Набор функций I nm (x 1, x 2, ..., x n) = x m.3) Функция S(x) = x + 1.Три операции определяются следующим образом:1) СуперпозицияИз вычислимой функции h(z 1, z 2, ..., z n) и n вычислимых функцийg 1(x 1, x 2, ..., x m), g 2(x 1, x 2, ..., x m), ..., g n(x 1, x 2, ..., x m) получаемвычислимую функцию f(x 1, x 2, ..., x m) , определяя ее следующим образом :f(x 1, x 2, ..., x m)=h(g 1 (x 1, x 2, .., x m),g 2(x 1, x 2, ..., x m),..,g n(x 1, x 2, .., x m))2) Примитивная рекурсияПо двум вычислимым функциям g(x 1, x 2, ..., x n) и h(x 1, x 2, ..., x n, x n+1, x n+2)определяем вычислимую функцию f(x 1, x 2 ,..., x n , x n+1) следующим образом :f(x 1, x 2, ..., x n, 0) = g(x 1, x 2 ,..., x n)f(x 1, x 2, ..., x n, y+1) = h(x 1, x 2 ,..., x n,y,f(x 1, x 2, ...,x n, y))3) Операция минимизацииПо вычислимой функции g(x 1, x 2, ..., x n) определяем вычислимую функциюz = f(x 1, x 2, ..., x n) из уравненияg(x 1, x 2, ..., x n -1, z) = x n (*)Значение z=f(x 1, x 2, ..., x n) для данного набора значений аргументов x 1, x 2, ..., x nнаходим, подставляя в уравнение (*) конкретные значения аргументов x 1, x 2, ..., x n-1,а вместо z последовательно подставляем числа 0, 1, 2, ..

и т.д. Эта последовательностьподстановок прекращается, как только набор конкретных значений аргументов x 1, x 2, ...,x n-1 и очередное подставляемое значение z оказываются набором значений аргументов, накотором не определена функция g(x 1, x 2, ..., x n), или в случае, когда уравнение (*)оказывается удовлетворенным. В первом случае функция f(x 1, x 2, ..., x n) считаетсянеопределенной на данном наборе значений аргументов x 1, x 2, ..., x n. Во втором значением функции f(x 1, x 2, ..., x n) на наборе значений аргументов x 1, x 2, ..., x n считаетсяпоследнее, подставленное вместо z, число. Если последовательность подстановок непрекращается, функция f(x 1, x 2, ..., x n) считается не определенной на данном наборезначений аргументов. Ясно, что, если функция f(x 1, x 2, ..., x n) определена для данногонабора значений аргументов x 1, x 2, ..., x n, ее значение получается после конечного числашагов, и мы вправе считать ее вычислимой частичной функцией.10Замечания1.

Хотя исходные функции О(х), I nm (x 1, x 2, ..., x n) и S(x) определены всюду, операцияминимизации приводит к частичным функциям (определенным не всюду), и,следовательно, в определенных выше операциях суперпозиции и примитивной рекурсиимогут участвовать частичные функции. Считается, что функции, определяемые этимиоперациями, определены только для тех наборов значений аргументов, для которыхопределены все функции, входящие в правые части соответствующих равенств.2. Тезис Черча постулирует возможность получения значений любой вычислимойчастичной функции процессом, использующим лишь операции суперпозиции,примитивной рекурсии, минимизации и вычисления функций 0(х), S(х), I nm (x). Конечно,тезис Черча не утверждает, что такой же результат не может быть получен другимивычислениями.Так, например, вычисление суммы двух целых x и y можно свести к вычислениюрекурсивной функции SS(x,y), определяемой примитивной рекурсиейSS(x, 0)=x, SS(x, y+1))= SS(x, S(y))=S( SS(x, y))Конечно же, искомая сумма может быть получена и обычным сложением чисел x и y.Несмотря на простоту используемых исходных функций и скромный набор операций,в отсутствии (по крайней мере, явном) средств разделения области значения независимыхпеременных, а также средств выделения области определения функции, в частично рекурсивной форме представимы все известные вычисления, и есть серьезные основаниясчитать, что и все возможные.В качестве первого примера, иллюстрирующего возможности выбранных средств,рассмотрим функцию f(x,y), задаваемую формулами f(x, y) = x - y, если x >= y, и f(x, y)=0,если x < y.

Легко проверить, что f(x, y) может быть задана примитивной рекурсией :f(x, 0)=x, f(x, y+1)=f(x, S(y))=g(f(x, y)),где g(z) определяется примитивной рекурсией : g(0) = 0, g(S(z)) = z.Вторым примером рассмотрим вычитание z = x-y, определенное только приx >= y. Эта частичная функция z является результатом операции минимизации длясоотношения SS(x,z) = y, где SS(x,z) определенная выше функция сложения. Легко видеть,что значение z определено операцией минимизации только при x >= y и поиск значений zпри x < y не завершится.

Последний пример иллюстрирует общее правило,заключающееся в том, что частично - рекурсивная функция определена для тех и толькотех значений аргументов, для которых ее значение может быть вычислено по общимправилам в соответствии с ее представлением.3. Устанавливая связь отображений на множестве слов из A* и функциямицелочисленного аргумента, мы рассматривали функции лишь одного аргумента.Сформулированное же решение вопроса вычислимости касается также и функций многихпеременных. Рассмотрение функций многих переменных вполне естественно вматематике, хотя их привлечение, в принципе, не расширяет понятие вычислимости.Действительно, можно задать алгоритмы взаимно-однозначных отображенийN × N × ...