ВВЕДЕНИЕ

В послевоенные годы получили большое развитие автоматические быстродействующие вычислительные машины, которые теперь применяются для решения самых разнообразных математических и логических задач. Характерная особенность этих машин, отличающая их от прежних вычислительных машин, заключается в том, что при выполнении своих функций, начиная с того момента, как в них введены начальные данные и программа, они работают без всякого вмешательства человека вплоть до выдачи окончательного результата. Производительность современных электронных автоматических машин огромна: они способны выполнить в одну секунду до 20 000 арифметических операций, что по крайней мере в 10 раз больше того, что может сделать за смену квалифицированный вычислитель, работающий на хорошем клавишном арифмометре. Область применения автоматических машин продолжает расти: машины решают сложные системы уравнений, переводят с одного языка на другой, играют в шахматы и т. д. Очень велики перспективы применения на производстве автоматических машин, осуществляющих управление всем технологическим процессом в масштабе крупного завода. Кроме того, возможность быстрой и надежной математической обработки, а также анализа экспериментальных данных создает предпосылки для появления новых, ранее недоступных методов исследования во многих областях науки.

Теперь уже все признают, что автоматические вычислительные машины представляют собою мощные орудия

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

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

Для математической логики характерно исследование сущности таких понятий, как «вычислительный процесс», «математическое доказательство», «алгоритм» и т. д. Еще за несколько лет до создания современных электронных автоматических вычислительных машин в математической логике были выработаны точные понятия «алгоритм» и общая схема автоматической вычислительной машины (машина Тьюринга), а также выяснена тесная связь между алгоритмами и машинами. Это позволило установить ряд важных теорем, раскрывающих сущность процессов, реализуемых в автоматических машинах; в частности, было строго доказано существование таких проблем, для которых невозможно машинное решение. Рассмотрению связи между алгоритмами и машинами и посвящена предлагаемая книга.

В §§ 1—4 на ряде примеров разъясняется, что такое алгоритм, и строятся алгоритмы для решения некоторых классов математических и логических задач.

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

Параграфы 7—13 посвящены ряду важных фактов теории алгоритмов, причем в качестве основного понятия теории взято понятие машины Тьюринга.

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

однако, как нам кажется, не мешают, а, наоборот, благоприятствуют лучшему уяснению существа дела. Для общности картины кое-что дано в обзорном порядке (§ 7).

Сделаем еще одно замечание. Современные машины с автоматическим управлением называют электронными, так как их важнейшие узлы сконструированы из электронных ламп или других электронных приборов (например, из полупроводников). Применение электронной техники обеспечивает большую экономию во времени на реализацию отдельных операций, совершаемых машиной. Однако основная черта этих машин — автоматическое управление процессами, происходящими в них, — не возникает за счет применения именно электронной техники. В принципе, электронные устройства можно было бы заменить даже механическими, т. е. можно было бы создать механическую вычислительную машину с автоматическим управлением, которая способна решать те же задачи, что и электронная (правда, значительно медленнее). Таким образом, возникновение вычислительных машин нового типа нельзя рассматривать как результат развития только электронной техники. Более того, первое описание общей схемы автоматической вычислительной машины (машина Тьюринга, см. § 8) было дано в теории алгоритмов еще в 1936 году как описание механического устройства. Первые фактически сконструированные машины (1940 г.) были электромеханическими.

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