Алан тьюринг

Сегодня довольно легко столкнутся с недобросовестными школьными учебниками, в частности с учебниками по информатике. В главах, посвященных алгоритмам, вы можете найти непосредственно определение алгоритма. Не пояснение, о чем идет речь, не рассказ о предмете, а именно определение. Причем выделенное жирным шрифтом, старательно обведенное в рамку и помеченное какой-нибудь заметной пиктограммой в виде восклицательного знака. Обычно приправлено всё это соусом из кучи обязательных и необязательных свойств, образуя в итоге феерический кавардак. Давайте попытаемся понять, что же такое алгоритм, почему мы не может дать ему конкретного определения и выясним, какие свойства являются обязательными, а какие нет.

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

В университетах дела обстоят получше, однако автору этих строк на курсе по математической логике и теории алгоритмов пришлось столкнуться все с тем же винегретом из определения алгоритма и его свойств. Разберемся, что тут не так.

Бесконечность не предел

Но перед этим немного вспомним математику. Из школьного курса математики мы знаем, что чисел существует бесконечно много какое бы большое число мы не взяли, всегда можно прибавить единицу и получить число еще большее. Обычно в школе этим и ограничиваются. В университете на курсе высшей математики нам расскажут, что бесконечности на самом деле бывают разные: множества, элементы которого можно пронумеровать натуральными числами считаются счётно-бесконечными. К таким множествам относят сами натуральные числа (числу 1 мы дадим номер один, числу 2 номер два и т.д.), целые числа - натуральные плюс ноль и отрицательные целые числа (первый номер отдаем нулю, второй - числу 1, третий - числу -1, то есть каждой положительное число k получает номер 2k, а каждое отрицательное число -m получает номер 2m + 1). К счетно-бесконечным множествам относят четные, нечетные и даже рациональные числа (числа представимые в виде несократимой дроби m/n, где m - целое, n - натуральное). Получается, что натуральных чисел ровно столько же, сколько четных, и, в то же время, ровно столько же, сколько целых. Количество (мощность) множества натуральных чисел обозначается символом ₀ (алеф-ноль).

Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.

Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ₁ (алеф-один). В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами).

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

Алгоритмы и вычислимость

Суть работы компьютера заключается в проведении некоторого вычисления преобразования одной порции информации в другую порцию. Причем результатом работы не обязательно должно быть число, главное, чтобы информация была представлена в некоторой объективной форме. Обычно под такой формой имеют в виду конечные цепочки символов некоторого алфавита. Получается, компьютерное вычисление есть некоторая функция в сугубо математическом смысле, с областью определения и значений в рассмотренном выше множестве A*. Именно тут возникают определенные проблемы. Если мы можем вычислить функцию, то можем записать промежуточные вычисления в виде текста. Более того, в виде тексте можно описать вообще правила вычисления. Мы знаем, что множество всех текстов счетное. Однако выясняется, что множество всех функций над натуральными числами имеет мощность континуум. Если мы пронумеруем все тексты, то получается функций вида A* -> A* тоже континуум. Получается, что некоторые функции вычислимы, а некоторые нет.

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

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

Частично-рекурсивные функции и тезис Черча

Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг.

Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к натуральным функция путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово частичные показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:

Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.

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

Тезис Тьюринга

Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое конструктивное преобразование. Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:

Каково бы не было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.

Любые попытки построить более мощные автомат заканчивались неудачей: для каждого такого автомата (машина Поста, нормальные алгоритмы Маркова, автоматы с регистрами и несколькими лентами) удавалось построить аналогичную машину Тьюринга. Некоторые ученые объединяют тезис Черча и тезис Тьюринга в тезис Черча-Тьюринга, так как они весьма близки по духу.

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

Свойства алгоритмов

Мы выяснили, почему у алгоритма не может быть конкретного определения. Однако можно определить свойства, которыми должен обладать каждый алгоритм. К сожалению, в литературе часто смешивают обязательные и необязательный свойств. Разберемся подробнее.

Обязательные свойства

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

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

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

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

Необязательные свойства

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

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

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

Заключение

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

Материал данной статьи во многом опирается на 1-ый том Программирование: введение в профессию А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В От Диофанта до Тьюринга и трехтомник А. Шеня по математической логике и теории алгоритмов.

Дата-центр ITSOFT размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.