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

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

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

Если помните, Тьюринг установил, что для е-Проблемы Гильберта решения не существует: невозможно алгоритмически определить, является ли произвольное утверждение простой логики первого порядка истинным или ложным. Конечно, в некоторых случаях решение есть, но не во всех. Общего алгоритма не существует. Нечто подобное отмечается и у компьютеров — определенная непознаваемость или неразрешимость называется проблемой остановки: в общем, вы не можете знать даже такую простую вещь, как остановится ли выполнение программы! Не существует систематического теста, чтобы выяснить это. Не существует алгоритма, который при наличии текста программы и ее входных данных определил бы, остановится ли она в конце концов или будет работать вечно.

Другими словами, для выявления остановки не существует ДНК-теста. Вы должны запустить программу и лишь тогда узнаете, что произойдет. То есть нужно пройти весь путь вычислительных операций от начала до конца, если он существует. Если программа остановится, то вы получили ответ, но если этого не произойдет, то вы не знаете ответа. А что, если еще немного подождать? Вы просто будете искать ветра в поле. Возможно, программа попала в бесконечный цикл. Ничего конкретного вы не можете знать.

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

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

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

(1) Вычесть входное число x из входного числа y. (2) Если результат отрицательный, измените цифру в шаге 3 на 4, в противном случае измените ее на 5. (3) Перейдите к шагу 4. (4) Напишите «минус» и остановитесь. (5) Напишите «плюс» и остановитесь.

Давайте попробуем проделать это с x, равным 7, и y, равным 6: (1) 7 минус 6 равно 1. (2) Результат положительный, поэтому: (3) Перейдите к шагу 5. (5) Напишите «плюс» и остановитесь. Программа может быть не только неприятным переплетением ветвей и циклов, но еще и движущейся целью. Большинство современных операционных систем «защищают» программиста — как самоблокирующиеся автомобильные двери, — запрещая такой самомодифицирующийся код. Это слишком легко может посеять хаос. Тем не менее Тьюринг перенес эту идею в мир настоящих компьютеров. Свою инструкцию условного перехода для реального оборудования он реализовал с помощью самомодифицирующегося кода.

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

Программирование

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

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

Программирование — секрет успеха универсальных вычислительных машин, но ученым потребовалось не менее десяти лет, чтобы понять это. Тьюринг опубликовал первые программы в своей знаменитой статье 1936 года «О машинно-вычислимых числах». Он написал их для концептуальных машин — машин Тьюринга, — которые демонстрировали концепцию универсальных машинных вычислений. Поэтому принято считать, что именно он изобрел программирование и концепцию хранимой в памяти программы. Он придумал слово computation (машинное вычисление), из которого родилось слово «компьютер», но слово «программирование» изобрел не он. Тьюринг использовал другой термин — «подготовка таблицы инструкций». Откуда же тогда взялось слово «программирование»?

Давайте более внимательно посмотрим, что на самом деле сделал Тьюринг. Предположим, ему понадобилась машина, которая переворачивает любую строку букв на входной ленте. Он разработал набор правил — таблицу инструкций — для конкретной машины Тьюринга, в которой реализована систематическая перестановка букв. Назовем ее машиной А. Затем он «скармливал» правила А универсальной машине. Вспомним рисунок, где изображены произвольная машина A и универсальная машина U, каждая со своей лентой. «Закодированные правила А» на этом рисунке — это то, что мы теперь назвали бы программой для А. Умная, интеллектуально интересная часть работы состоит в разработке таблицы инструкций для машины А, а не в ее кодировании в форму, требуемую для машины U. Кодирование — это простой и в чем-то даже механический набор действий. В нашем примере с машиной-карточкой эта работа заключается в замене пробелов на 0, записи лицевой ориентации карточки как f и так далее. Довольно рутинное занятие. Машине такое не надоест, а человек умрет от скуки.

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

Однако в конце 1940-х те, кто создавал первые аппаратные компьютеры, использовали термин setting up — предустановка, или настройка, — чтобы описать,