malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

исправить. Это и есть результат работы программы в таком случае. Но программа не должна зацикливаться без выдачи какого-либо результата! Это знает любой программист.

д).Начальная система величин может выбираться из некоторого потенциально бесконечного множества (массовость алгоритма).

Другое не строгое и более “ машинное” описание понятия алгоритма приводит Х.Роджерс [3].

1).Алгоритм задается как конечный набор инструкций конечных размеров.

Любой алгоритм может быть описан словами, например,

задан как программа на языке С.

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

3).Имеются возможности для выделения, запоминания и повторения шагов вычисления.

4).Пусть P - набор инструкций из 1), L - вычислитель из

2). Тогда L взаимодействует с P так, что для любого данного входа вычисление происходит дискретным образом по шагам, без использования аналоговых устройств и соответствующих методов.

5).L взаимодействует с P так, что вычисления продвигаются вперед детерминированно, без обращения к случайным методам или устройствам.

8

В частности, следующий исполняемый оператор программы не может выбираться жребием.

Это неформальное определение алгоритма уточняется ответами на следующие вопросы.

6).Следует ли фиксировать конечную границу для размера входов (начальная система величин в определении Мальцева)?

Ответ нам очевиден из программирования - нет. И в самом деле, если входной величиной является файл (стандартная ситуация), его длина программе неизвестна и она работает с потенциально бесконечным входом, т.е. каждый раз обрабатывается конечная строка2, однако для любого наперед заданного натурального N найдется строка длиной больше, чем

N.

7).Следует ли фиксировать конечную границу для размера памяти?

Ответ тоже очевиден - нет. Если вычислять значение полинома второй или большей степени при неограниченной длине входа (числа символов, необходимых для представления входных значений), то ясно, что для промежуточных вычислений необходимо иметь неограниченную память (ее потребный объем зависит от длины входа). И реально программисты часто

2 О файле говорится как о строке, потому как строкой является и любая последовательность битов, составленная, например, из записей файла

9

сталкиваются с ситуацией, когда программа, скажем, умножения двух матриц размера n0×n0 не может исполняться из-за недостатка памяти, а матрицы размера (n0-1)×(n0-1) умножаются благополучно. Можно задавать и другие вопросы, но для нас этого достаточно.

Этих не строгих определений на практике достаточно и для того, чтобы понять, является ли процесс алгоритмом, и для построения нужного алгоритма. Однако его совершенно недостаточно для ответа на вопрос, существует ли алгоритм решения некоторой проблемы? Для доказательства существования алгоритма решения проблемы достаточно построить такой алгоритм. Здесь годится и неформальное определение. Но чтобы доказать отсутствие такого алгоритма,

надо для начала точно знать, что такое алгоритм. Нам строгое определения алгоритма поможет определить необходимое понятие программы и сформулировать требования к ней.

Каждый алгоритм A вычисляет функцию FA при некоторых заданных значениях входных величин. Функции,

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

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

10

таких формализациях оказался одним и тем же при самых разнообразных попытках расширить понятие алгоритма.

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

Если принять тезис Черча, то тогда доказательство вычислимости функции сводится к доказательству ее алгоритмической вычислимости.

Пост и Тьюринг для уточнения понятия алгоритма построили точно описанные в математических терминах

“ машины”. Несмотря на предельную тривиальность этих машин на них оказалось возможным определить (выполнить) все алгоритмические процессы, когда-либо рассматриваемые в математике.

1.2. Основные предварительные понятия

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

11

1.2.1. Алфавит.

Алфавитом называется конечное множество символов

A=(a,b,...,c). Конечная последовательность символов алфавита A

называется словом в алфавите A. Количество символов в слове

называется длиной слова. Например, если A={a,b}, то ab, aa,

abbaa, bbbbba - слова в алфавите A. Множество всех слов алфавита A обозначается A*.

s, s1 - префикс разложения s1s2s3 .

Возможно несколько различных разложений слова s,

содержащих подслово s2. Слово s2 называется первым

вхождением s2 в s, если префикс s1 обладает наименьшей длиной среди всех таких разложений слова s. Например, слово abaabaaba=a×ba×abaaba=abaa×ba×aba=abaabaa×ba имеет несколько разных разложений с подсловом ba, первое из них содержит первое вхождение ba в слово abaabaaba.

12

1.2.2.Кодирование.

В теории всегда рассматриваются вычислимые функции,

отображающие одни множества слов в другие. Множества слов в некотором алфавите выбраны в силу универсальности этих множеств для представления величин, потому что все прочие

виды величин кодируются и представляются словами.

Пусть A - алфавит, A* - множество всех слов в алфавите A,

B A*, M - множество некоторых объектов. Закодировать объекты из M в алфавите A означает задать однозначное

соответствие f:B→M. Взаимно однозначного соответствия не

требуется. Слово b B , m=f(b), m M, называется кодом или

именем объекта m в кодировании f.

Рассмотрим алфавит A={1}, тогда натуральное число n

использовать алфавит A={0,1}, то всем программистам известно,

как кодируются целые и вещественные числа, а также символы различных алфавитов. Слово 11 есть код числа 3, а слово 011,

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

13

величины. Однако всегда по заданному коду закодированный объект должен восстанавливаться однозначно.

Понятно, что при изучении вычислимых функций можно ограничиться рассмотрением только числовых функций

(функций, определенных на множестве натуральных чисел N, со значениями в N), предполагая наличие подходящей кодировки. И

все рассматриваемые множества – только подмножества множества натуральных чисел N либо само N.

1.2.3.Бесконечный алфавит

Иногда удобно использовать бесконечные алфавиты вида

A={a,b,...,c,di,tij}, содержащий конечное число символов a,b,...,c, i,j=0,1,... . Такой алфавит формально бесконечен, так как содержит бесконечное число символов di, tij. Однако он легко кодируется в конечном алфавите A0={a,b,...,c,d,t,n,m}. При этом символы di кодируются словами dnn...n , а символы tij - словами tnn...nmm...m, в которых символ n повторяется i раз, а символ m - j раз. Таким образом, всегда можно оставаться в конечных алфавитах даже при использовании такого сорта бесконечных алфавитов.

1.2.4.Наборы (кортежи)

Пусть задан алфавит, B=A {,}, где “ ,” - специальный выделенный символ. Кроме слов в A придется далее

14

1.2.5.Термы

Термы (функциональные термы) - это слова особого вида,

записанные в функциональном алфавите. Функциональный алфавит состоит из трех групп символов, используемых для записи функций. Первую группу составляют предметные

символы (предметные переменные), изображающие переменные.

Для их обозначения будут использованы строчные буквы x, y, z,

или эти же символы с индексами. Вторую группу составляют

функциональные символы, изображающие функции. В качестве функциональных символов будем использовать буквы f, g, h

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

Понятие терма определяется шагами по индукции.

Сначала определяются термы длины 1, т.е. слова длины 1 в

функциональном алфавите, которые есть термы по определению.

Термами длины 1 называются односимвольные слова из

15

предметных символов. Например, термами являются слова x и y, а слово f термом не является.

Далее, пусть для некоторого, k>1, термы длины меньше k

уже определены. Тогда слово t длины k называется термом,

если оно имеет вид f(t1,t2,...,tт), где t1, t2, ..., tт - термы длины меньшей чем k, f – т-арный функциональный символ (т

входных переменных). Пусть, например, дан функциональный

g2

Рис. 1.1.

16

Понятие терма введено чисто синтаксически безотносительно к понятиям функции, переменной и т.п. Просто

есть алфавит, символы которого разбиты на три подмножества и

терминам «предметный символ» и «функциональный символ».

Интерпретацией I называется отображение, которое

сопоставляет:

- каждой предметной переменной x - элемент I(x)=dx N,

элемент dx множества N называется значением переменной x, N

называется оснόвным множеством или областью интерпретации.

- каждому k-местному функциональному символу fk -

частичную функцию I(fk)=Fk:N×N×… ×N→N. Функция Fk

называется значением функционального символа fk.

- каждому терму t=fk(x1,x2,…,xk) сопоставляется значение терма I(t)=dt N, dt=val(fk(x1,x2,...,xk)). Функция val (от английского value - значение) задана на множестве термов, она определяется по индукции:

-val(x)=I(x)=dx Dx;

-пусть t=fk(t1,t2,...,tk) - терм длины n, термы t1, t2,

..., tk длины меньшей, чем n и функция val определена для термов длины меньшей чем n.

17