Дополнение. К курсу «Дискретная математика для программистов»

К курсу «Дискретная математика для программистов»

Наивная теория алгоритмов

Изложение построено в форме дополнения к учебнику «Дискретная математика» издание 2013 года.

В этом Дополнении изложено доказательство первой теоремы Гёделя о неполноте, основанное на понятии алгоритма. Приводимое доказательство в своих идеях следует брошюре Успенского[1] [32], и является достаточно далёким от оригинального доказательства Гёделя. Приведенное изложение далеко и от Успенского, поскольку сокращено, упрощено, «запрограммировано» и выдержано в стиле учебника.

…Ты когда-нибудь видела, как рисуют множество?

– Множество чего? – спросила Алиса.

– Ничего, – отвечала Соня. – Просто множество!

– Не знаю, – начала Алиса, – может...

– А не знаешь — молчи, – оборвал ее Болванщик.

Льюис Кэрролл, Алиса в стране чудес

4.4 ¢. Наивная теория алгоритмов

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

Тем не менее, даже этого нестрогого понятия оказывается достаточно во многих важных случаях, также как и нестрогого понятия «множество» в наивной теории множеств оказывается достаточно для многих полезных построений, в частности тех, которые приведены в этом учебнике.

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

Отступление. Обычно в «строгой» теории алгоритмов вводится одно или несколько «уточнений» понятия алгоритма, например: машина Тьюринга, машина Поста, нормальный алгорифм Маркова, и многие другие. В сущности, каждое такое уточнение понятия алгоритма определяет формальный способ записи предписаний, т. е. программ и неформальный алгоритм интерпретации программ, т. е. правила применения программ к аргументам для получения результатов. Все предложенные к настоящему моменту уточнения интуитивного понятия алгоритма оказались эквивалентными (в строгом математическом смысле), что дало основание выдвинуть тезис Тьюринга–Чёрча, неформально постулирующий, что все уточнённые понятия алгоритма равнообъёмны интуитивному понятию алгоритма. Формальные уточнения понятия «алгоритм» и построенная на их основе строгая теория алгоритмов обладают несомненными достоинствами и подлежат неукоснительному изучению. Однако теория алгоритмов имеет две имманентных особенности, которые в практическом применении проявляют себя как неудобства. Во-первых, введение формального способа записи алгоритмов резко усложняет и затрудняет программирование, поскольку программировать приходится в терминах очень низкого уровня (ячейки ленты машины Тьюринга и тому подобное). Во-вторых, поскольку способ интерпретации программ все равно остается неформальным и потому допускает различные реализации, затруднительно ввести независящую от реализации меру для прямого сравнения алгоритмов, и приходится применять косвенные критерии, подобные асимптотическим оценкам трудоемкости и тому подобное.

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

Не ограничивая общности, далее считается, что зафиксирован некоторый конечный алфавит символов U, достаточный для записи всех необходимых объектов. Алгоритмы записываются с помощью последовательностей символов из этого алфавита; данные, к которым применяются алгоритмы, также записываются с помощью последовательностей символов (возможно, других символов), элементы всех множеств записываются с помощью слов в этом алфавите, функции действуют из множества слов в множество слов в этом алфавите и т. д. Например, можно считать, что в алфавит U входят кириллические, латинские и греческие буквы, прописные и строчные, в различных начертаниях, арабские цифры, знаки препинания, скобки, математические знаки и т. д. При этом правила записи (кодирования) различных объектов считаются известными. В частности, считаются известными правила записи натуральных чисел (например, с помощью десятичных цифр), арифметических выражений (например, с помощью знаков операций, чисел и переменных), алгоритмов (например, с помощью псевдокода). Таким образом, принимается, что существуют алгоритмы, которые по любому слову в данном фиксированном алфавите U (п. 1.8.8) позволяют надежно определить, соответствует ли это слово правилам записи, и определить, какой именно объект записан. Доказывать существование подобных алгоритмов лексического и синтаксического анализа нет нужды — это эмпирический факт, доступный в повседневных ощущениях при работе с компьютерами.

Имена алгоритмов записываются прописными полужирными латинскими буквами в прямом начертании, чтобы легко отличать их от имен множеств и иных объектов. Сами алгоритмы записываются на псевдокоде. Если алгоритмы имеют входные данные и результаты, то они указываются отдельно и называются заголовком алгоритма, а операторы, задающие сам алгоритм, называются телом алгоритма.

4.4 ¢ .1. Вычислимые функции

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

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

A Í Dom A ´ Im A.

Если отношение А обладает свойством функциональности (см. п. 1.6.1), то говорят что алгоритм A реализует вычислимую функцию.

Если функция является вычислимой, то есть если предъявлен реализующий её алгоритм, то может быть построено бесконечно много других алгоритмов, также реализующих эту же функцию. Действительно, для этого достаточно вставлять в тело любого из уже построенных алгоритмов произвольные ненужные операторы, выполнение которых не влияет на результат. Все алгоритмы, реализующие одну и ту же функцию, называются функционально эквивалентными. Функциональная эквивалентность, очевидно, действительно является отношением эквивалентности на классе алгоритмов и определяет фактор-множество (п. 1.7.2) классов функционально эквивалентных алгоритмов. Это фактор-множество взаимно однозначно соответствует классу вычислимых функций, поэтому можно выбрать какой-либо из функционально эквивалентных алгоритмов, объявить его представлением вычислимой функции и использовать в качестве функции везде, где это необходимо, в частности в других алгоритмах для вычисления значения этой функции. Это оправдывает используемые далее вольности в обозначениях и в словесных оборотах, когда вычислимые функции и их представления не различаются, подобно тому, как мы говорим о функции, предъявляя запись реализующей её формулы (п. 3.2.4).

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

Замечание 2. Для алгоритмов неизвестно нормальных форм (п. 3.4.2), к сожалению.

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

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

A: Dom A ® Im A,

Im A = A (Dom A),

r = A (a), где a ÎDom A, r ÎIm A.

Замечание. Вычислимая функция может быть частичной, т. е. в записи алгоритма A может быть указано, что алгоритм принимает на вход значения типа T ₁ и выдает на выход значения типа T ₂ (A: T ₁® T ₂), но при этом, на самом деле, Dom A Ì T ₁ и Im A Ì T ₂, т. е. область отправления и область прибытия шире области определения и области значений, соответственно. В этом случае считается, что при применении к неподходящему аргументу вычислимая функция не вырабатывает никакого результата. Тем самым наивная теория алгоритмов приближается к суровой программистской практике.

Примеры.

1. Суперпозиция вычислимых функций, очевидно, вычислима. Тем самым любая формула над базисом вычислимых функций задает вычислимую функцию.

2. Алгоритмы 1.3, 1.4–1.7, 3.1–3.5, 4.1 задают вычислимые функции.

Отступление. Понятие тип, или тип данных, использованное в предыдущем замечании, имеет важное значение в программировании. С точки зрения наивной теории алгоритмов тип — это некоторое перечислимое (и разрешимое, см. п. 4.4 ¢. 3) множество слов в алфавите U. В программировании понятие типа (и родственное понятие класса) применяется, в частности, для проверки правильности применения (частичных) вычислимых функций и алгоритмов. А именно, указывая типы параметров функции, программист задает (до некоторой степени) область определения функции, и система программирования может проверить, принадлежит переданный аргумент указанному типу, или нет (это возможно, поскольку тип — разрешимое множество). Результаты этой проверки могут быть использованы для диагностирования или предотвращения ошибки и других полезных действий. В этом разделе нам не понадобилась теория типов, но это важное и практически полезное ответвление наивной теории алгоритмов.

4.4 ¢ .2. Перечислимые множества

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

A = { a Î U ^* | a:= A ()}.

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

В используемом псевдокоде в теле алгоритма, перечисляющего множество, как правило, присутствует оператор yield a.

Замечание 1. Иногда оператор yield a отсутствует в явном виде, но тогда он всегда моделируется оператором A:= A + a добавления элемента a в изначально пустое множество A.

Замечание 2. Всякое конечное множество может быть задано перечислением элементов { a ₁, …, a_n } (п. 1.1.2) и тем самым является перечислимым. Действительно, алгоритм begin yield a ₁; …; yield a_n end очевидно, перечисляет это множество. В частности, алфавит U перечислим, перечисляющий его алгоритм обозначим U.

Замечание 3. Всякое перечислимое множество A линейно упорядочено (п. 1.8.1). Действительно, порядок выполнения операторов yield (или оператора добавления элемента) очевидно, линеен.

Замечание 4. Перечислимые множества (и только они!) могут появляться в заголовке цикла по множеству for a Î A do B (a) end for, где B — некоторый алгоритм. Действительно, чтобы реализовать этот цикл, достаточно в теле перечисляющего алгоритма A заменить оператор yield a вызовом алгоритма B (a).

Замечание 5. Конкретные перечисляющие алгоритмы, приводимые в примерах, генерируют каждый элемент ровно один раз, как это и требуется в обычных множествах. Однако явно накладывать такое ограничение на перечисляющие алгоритмы необязательно. Действительно, если имеется перечисляющий алгоритм, который перечисляет какие-то элементы несколько раз, то в его тело можно вставить проверку, исключающую повторные добавления элементов. Перечисляющие алгоритмы, генерирующие элементы по несколько раз, можно использовать для работы с мультимножествами, которые в этом разделе не понадобились.

Примеры.

1. Множество натуральных чисел перечислимо:

N = { n | n:= 0; while true do n:= n +1; yield n end while }.

2. Алгоритмы 1.1, 1.8–1.9 задают перечислимые множества.

Пустое множество Æ и множество всех слов U ^* перечислимы. Пустое множество перечислимо пустым алгоритмом skip, а множество всех слов перечислимо очевидным алгоритмом, который вначале перечисляет все слова длины 1, потом все слова длины 2 и так далее.

Теорема 1. Существуют невычислимые функции и неперечислимые множества.

Доказательство. Число различных слов в непустом конечном алфавите счётно. Всякий алгоритм — это слово в конечном алфавите, следовательно, число различных алгоритмов не более чем счётно. Фактор-множество (п. 1.7.2) не может превосходить исходное множество по мощности, поэтому множество классов функционально эквивалентных алгоритмов не более чем счётно. С другой стороны, множество всех подмножеств счетного множества несчётно. Значит число различных множеств слов и число различных функций из множеств слов в множества слов несчётно. Следовательно, невозможно взаимно-однозначное соответствие из множества алгоритмов в множество множеств и в множество функций. чтд

Следствие. Существуют перечислимые множества и вычислимые функции; их количества не более чем счётны.

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

Пример. Множество N перечислимо, множество N²=N´N также перечислимо. Например, следующий алгоритм N2 перечисляет пары натуральных чисел < a, b >:

s:=1; while true do s:= s +1; for a from 1 to s– 1 do yield < a, s–a > end for end while.

Перечислимость множеств тесно связана с вычислимыми функциями натурального ряда. Действительно, перечислимое множество N (и его отрезки, п. 1.2.5) — это удобное и естественное средство нумерации, то есть перечисления множеств слов. Пусть A — перечислимое множество, заданное алгоритмом A. Рассмотрим вычислимую функцию F: N ® A, заданную следующим алгоритмом:

func F (n: N): A

k:=0;