Пиксель. История одной точки - Элви Рэй Смит

есть существенное отличие — петли или, как говорят программисты, циклы. Вы повторяете внешний цикл (шаги с 1 по 4), пока не закончатся гвозди, а внутренний «вложенный» цикл (шаги 3 и 4) вступает в дело, если гвоздь согнулся от неумелых ударов молотка. Выполнение начинается с первой инструкции и, возможно, никогда не закончится, если, скажем, после каждого удара гвоздь будет гнуться. Количество выполняемых шагов обычно намного, а иногда и значительно больше, чем количество инструкций.

В инструкции по забиванию гвоздей есть два шага, при которых происходит ветвление, — они представлены в форме «если… тогда… в противном случае…» (шаги 2 и 4). Их называют условными переходами: «Если какое-то условие выполнено, то переходи к одному шагу, в противном случае — к другому». Условный переход — обычно его обозначают символом ЕСЛИ (if) — изменяет порядок выполнения инструкции в списке.

Он также избавляет от бесконечного цикла. Рассмотрим такой пример: (1) Скажите «Привет». (2) Перейдите к шагу 1. Нет условного перехода, позволяющего выйти из цикла. Такой систематический процесс начинается, но никогда не заканчивается.

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

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

Это не значит, что математика не важна. Люди систематически осваивали ее на протяжении тысячелетий. Даже в эпоху вездесущих калькуляторов дети все еще учатся складывать два числа столбиком. Как известно, чтобы это сделать, нужно последовательно сложить каждую пару цифр, начиная справа, и записать их сумму в ответ. Если (это важно!) она равна или больше 10, то 1 переносится на следующий шаг и прибавляется к цифре, стоящей на одну позицию левее. И так далее. В процессе сложения столбиком есть еще одно неявное ЕСЛИ: если закончились цифры и больше нет единицы для переноса, придется остановиться. Это набросок процесса, который обычно называют алгоритмом сложения. Не сомневаюсь: мы все счастливы, что наши калькуляторы теперь хорошо его «знают» и при необходимости могут сложить даже не два, а два десятка чисел.

В прошлом веке слово «алгоритм» стало синонимом термина «систематический процесс». Оно произошло от искаженного имени персидского математика IX века аль-Хорезми. Он жил в древнем Багдаде и писал о систематических процессах, связанных с десятичной системой счисления — новой, только что появившейся в Индии концепцией, описывающей странную, доселе неведомую штуку под названием «ноль». В позднем Средневековье ее стали называть алгоризмом или авгримом, еще дважды исказив имя ученого. Таким образом, понятие алгоритма коренится в числах и манипуляциях с ними, но никоим образом с ними не связано.

Джеффри Чосер в XIV веке использовал фразу Nombres in augrym (числа в десятичной системе) для описания делений на астролябии. Но его друг Томас Аск употребил этот термин более выразительно. Его слова, приведенные в эпиграфе, говорят о силе концепции ноля — Sypher in augrym (цифра 0 в десятичной системе). По сути, он утверждает, что, хотя сам по себе ноль ничего не значит, его добавление значит очень много. С нашей точки зрения, каждый ноль справа увеличивает число на порядок и действительно имеет существенное значение. Авгрим Аска далек от нашего алгоритма, но по прошествии времени его афоризм кажется пророческим, предсказавшим потенциал Усиления.

Что произойдет, если количество шагов в алгоритме станет невероятно огромным, число циклов многократно увеличится, уровень их вложенности значительно углубится, а условные переходы сильно разветвятся? Задавая такие вопросы о систематических процессах на рубеже XX века, математики проложили путь к миру универсальных вычислительных машин, хотя сами и не догадывались об этом. Они еще не осознали двойного великолепия Гибкости и Усиления, а также присущих им сверхспособностей.

е-Проблема

Давид Гильберт, король математиков, работал в Геттингенском университете — центре математической вселенной, пока в 1930-е годы нацисты не подвергли гонениям профессоров еврейского происхождения. Еще в 1900 году он использовал свой международный авторитет, чтобы привлечь внимание к проблемам, затрагивающим основы математики. Наибольшую известность из них получили Вторая (противоречивы или нет аксиомы арифметики?) и Десятая (Есть ли универсальный алгоритм решения диофантовых уравнений?). Каждый, кто сумеет решить любую из них, сразу же будет признан математиком мирового уровня.

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

Возьмем утверждение: все предметы — сосновые шишки. Или вот еще одно: все предметы — это айва. Если объединить два этих утверждения союзом или, получится составное утверждение, которое всегда разрешено в такой системе: все предметы — сосновые шишки, или все предметы — айва. В системе есть правило, позволяющее заменить составное утверждение эквивалентным: все объекты — сосновые шишки или айва. Здесь слово «эквивалентный» означает, что если первое утверждение верно, то верно и второе, а если первое ложно, то ложно и второе. Таким образом, перестановка слов не меняет истинности утверждения. Простая перестановка сводит два начальных утверждения, объединенных союзом или, в одно, при этом или занимает положение между сосновыми шишками и айвой, а не между двумя утверждениями. Может показаться очевидным, но суть в том, что каждый шаг в этой логической системе преобразует одно утверждение в эквивалентное с помощью простой, даже тривиальной операции. Новое утверждение вытекает из старого.

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

Математиков интересуют именно истинные утверждения. Ученые начинают с очень простых — заведомо