Набор инструкций, которые задаются машине для достижения результата, называется алгоритмом. Этот термин произошел от латинского варианта написания имени аль-Хорезми. Необходимо отметить, что вычислительные алгоритмы будут в значительной степени опираться на решения задач, известные уже с давних пор. Помните, как аль-Хорезми в своей книге «Китаб аль-джебр ва-ль-мукабала» не только рассматривал абстрактные математические объекты, но и давал практические рекомендации жителям Багдада, как искать решение повседневных проблем? Так же вычислительной машине нет необходимости объяснять теорию, которую она не в состоянии понять. Для машины необходимо только, чтобы ей задали соответствующие установки, какие расчеты в каком порядке производить.
Ниже представлен пример алгоритма, который задается вычислительной машине. Допустим, у этой машины есть три ячейки памяти, в которые можно внести соответствующие числа. Сможете ли вы посчитать, каков будет результат этого алгоритма?
Этап A. Введите число 1 в ячейку памяти № 1, а затем перейдите к шагу B.
Этап B. Введите число 1 в ячейку памяти № 2, а затем перейти к шагу C.
Этап C. Введите в ячейку памяти № 3 сумму чисел, находящихся в ячейке памяти № 1 и ячейке памяти № 2, а затем перейдите к шагу D.
Этап D. Введите в ячейку памяти № 1 число из ячейки памяти № 2, а затем перейдите к шагу E.
Этап E. Введите в ячейку памяти № 2 число из ячейки памяти № 3, а затем перейдите к шагу C.
Можно заметить, что машина будет зациклена, так как на этапе Е она возвращается к этапу C. Таким образом, этапы C, D, E будут повторяться бесконечно.
Ну что? Вы поняли, что таким образом рассчитывает машина? Нужно совсем немного времени для того чтобы расшифровать полученную последовательность чисел. Вы можете догадаться, что этот алгоритм описывает последовательность чисел, которые нам уже хорошо известны, а именно числа Фибоначчи!
[21] На этапах А и В были введены первые два члена последовательности: 1 и 1. На этапе C вычисляется сумма двух предыдущих чисел. На этапах D и Е в память заносятся последующие числа из ряда таким образом, чтобы алгоритм мог работать циклично. Если вы заходите проверить, как работает данный алгоритм, то сможете убедиться, что получится следующая последовательность чисел: 1, 1, 2, 3, 5, 8, 13, 21 и т. д.
Несмотря на то, что алгоритм выглядит достаточно просто на первый взгляд, машина Тьюринга все еще не способна его обработать. В соответствии с определением, данным их автором, эта машина не может осуществлять операцию сложения, как это указано на этапе C. В ее функции входят только внесение, прочтение и замена элементов в памяти в соответствии с инструкциями на каждом этапе. Таким образом, можно задать ей алгоритм сложения, согласно которому числа складываются в соответствии с их разрядами и запоминанием чисел в уме, по аналогии со счетами. Другими словами, сложение не является частью аксиоматики машины, а это уже одна из ее теорем, которые должны иметь свой алгоритм для использования. После того как этот алгоритм будет составлен, он может быть использован на этапе C, и машина Тьюринга, таким образом, вычислит числа Фибоначчи.
Повышая сложность задач, можно научить машину Тьюринга выполнять операции умножения, деления, возведения в квадрат, извлечения квадратного корня, находить решения уравнений и тригонометрические соотношения, вычислять приближенное значение числа π, определять декартовы координаты геометрических фигур или исчислять бесконечно малые величины. Таким образом, при условии составления соответствующих алгоритмов машина Тьюринга способна решать любые математические задачи, которые мы уже успели рассмотреть, причем точность таких расчетов будет значительно выше.
Теорема о четырех красках
Возьмем карту территории, состоящую из нескольких областей, отделенных друг от друга границами. Какое минимальное количество цветов необходимо использовать при их раскрашивании, чтобы две соседних области всегда были разного цвета?
В 1852 г. южноафриканский математик Фрэнсис Гутри задался этим вопросом и высказал предположение, что для раскрашивания любой карты достаточно четырех цветов. После него многие ученые пытались доказать это утверждение, но никому не удавалось этого сделать на протяжении более чем столетия. Получилось, однако, достичь некоторого прогресса, в результате чего установлено, что все возможные карты могут быть сведены к 1478 отдельным случаям, каждый из которых требует проведения множества проверок. Один человек или даже целая команда людей не сможет проверить все возможные варианты. Для этого не хватило бы и целой жизни. Представьте разочарование математиков, у которых есть метод для доказательства или опровержения гипотезы, но нет достаточного количества времени для реализации соответствующей задачи!
В 1960-х гг. идея использовать компьютер начинает зарождаться в сознании некоторых ученых, и наконец в 1976 г. два американца, Кеннет Апел и Вольфганг Хакен, объявили, что они доказали теорему. Потребовалось более 1200 часов на проведение расчетов и было проведено 10 миллиардов элементарных операций на вычислительной машине, чтобы перебрать все возможные варианты для 1478 типов карт.
Оглашение этого результата имело эффект разорвавшейся бомбы в математическом сообществе. Можно ли доверять этому новому типу «доказательств»? Можем ли мы принять действительность доказательства такой длины, которое ни один человек в мире не смог бы дочитать до конца? До какой степени можно доверять машинам?
Эти вопросы вызывают много споров. В то время как одни утверждают, что мы не можем быть на 100 % уверены в том, что машина не ошибется, другие отвечают им, что то же самое можно было бы сказать и о людях. Неужели электронный механизм менее надежен, чем биологический механизм вида Homo sapiens? Данные, полученные с помощью машины из металла, менее надежны, чем доказательства, полученные машиной из плоти и крови? Мы уже неоднократно были свидетелями того, как математики, зачастую даже самые великие, допускали ошибки, которые обнаруживались только спустя какое-то время. Должно ли это заставить нас усомниться в правильности самого математического знания? В работе машины, несомненно, могут случиться неполадки, в результате чего будут допущены ошибки, но, если ее надежность по крайней мере равна человеческой (а зачастую она выше), нет никаких оснований отказываться от использования результатов, полученных с ее помощью.
Сегодня математики научились доверять компьютерам, и большинство из них в настоящее время считает действительным доказательство теоремы о четырех красках. Многие другие результаты были также получены с помощью компьютеров. Тем не менее прибегать к этому методу доказательства считается нежелательным. Краткое доказательство, сделанное без применения вычислительной техники, считается более красивым. Поскольку цель математики – изучение абстрактных объектов, доказательства, выведенные человеком самостоятельно, более наглядны и позволяют лучше понять саму их суть.
