Глушков: кибернетика и ОГАС

Математик до кибернетики

Виктор Михайлович Глушков (1923–1982) начинал не как инженер и не как кибернетик, а как алгебраист-тополог.

12 декабря 1955 года он защитил в МГУ докторскую диссертацию «Топологические локально нильпотентные группы». Её содержание — одна из версий пятой проблемы ГильбертаДавид Гильбертнемецкий математик · 1862–1943Человек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти..

Напомним, о чём речь. Гильберт в 1900 году спросил: обязательно ли непрерывная группа преобразований, локально устроенная как евклидово пространство, является группой Ли — то есть обязательно ли непрерывность влечёт гладкость? В 1952 году Глисон, Монтгомери и Циппин ответили «да» для локально компактных локально евклидовых групп. Оставались более общие постановки, и Глушков продвинул одну из них — для локально бикомпактных групп, получив описание их строения. Ему было тридцать два, и работа была сделана в Свердловске, в педагогическом институте, вне всяких научных центров.

Это стоит помнить, читая дальше: человек, ставший символом советской кибернетики, пришёл в неё с сильным чисто математическим результатом.

Теорема, работающая у вас в редакторе

В 1961 году Глушков напечатал в «Успехах математических наук» обзор «Абстрактная теория автоматов», а в 1962-м — книгу «Синтез цифровых автоматов» (Ленинская премия 1964 года). Там есть конструкция, которую в мировой литературе называют автоматом Глушкова, и с ней вы имеете дело каждый раз, когда пишете регулярное выражение.

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

Приём Глушкова: пронумеровать вхождения букв и сделать номера состояниями.

Возьмём выражение $a(b\mid c)^{*}$. Пронумеруем буквы: $a_1$, $b_2$, $c_3$. Считаем три множества:

• начала — какие позиции могут быть первой буквой слова: $\{1\}$;
• концы — какие могут быть последней: $\{1,2,3\}$;
• следования — какая позиция за какой: $\text{сл}(1)=\{2,3\}$, $\text{сл}(2)=\{2,3\}$, $\text{сл}(3)=\{2,3\}$.

Автомат готов: состояния — это позиции плюс начальное состояние $q_0$; из $q_0$ по букве идём в начала, из позиции $i$ по букве — в те элементы $\text{сл}(i)$, которые помечены этой буквой; принимающие состояния — концы.

Существенное свойство: у автомата Глушкова ровно $n+1$ состояние, где $n$ — число вхождений букв в выражение. Не больше и не меньше — размер известен заранее. Именно поэтому конструкция удобна на практике, и именно она (в разных обличьях) стоит внутри библиотек регулярных выражений.

Институт кибернетики

В 1956 году Глушков приехал в Киев — в ту самую лабораторию, где Лебедев за пять лет до того собрал МЭСМ. В 1957-м он возглавил Вычислительный центр АН УССР, а в декабре 1962 года на его основе был создан Институт кибернетики. Глушков руководил им двадцать лет, до смерти.

Машины института:

• «Киев» (1958) — с языком, приближённым к математической записи;
• «Днепр» (1961) — первая советская управляющая машина, то есть работающая не с задачами, а с производственным процессом в реальном времени; выпускалась десять лет;
• «МИР» (1965) и «МИР-2» — «машина для инженерных расчётов»: маленькая, с аппаратной поддержкой символьных вычислений и входным языком высокого уровня. Идея была та, которая позже станет персональным компьютером: машина на рабочем столе инженера, а не в вычислительном центре.

В 1967 году на выставке в Лондоне «МИР-1» купила IBM — единственный случай покупки советской ЭВМ американской фирмой.

ОГАС

В 1962 году Глушков предложил Общегосударственную автоматизированную систему учёта и обработки информации.

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

Хронология: идея 1962 года; эскизный проект 1964-го; расчётная стоимость превышала стоимость космической и атомной программ вместе взятых; срок — 15–20 лет.

У предложения был предшественник. В 1959 году Анатолий Китов направил в ЦК записку (её называют «Красной книгой») с предложением создать единую сеть вычислительных центров двойного назначения — военных и гражданских. За это Китова исключили из партии и сняли с должности: идея делить военные машины с народным хозяйством была признана вредной.

ОГАС не построили. Причины называют разные, и, по-видимому, работали все сразу:

• ведомственная. Центральное статистическое управление и министерства теряли контроль над собственной отчётностью. Система, показывающая реальные цифры в реальном времени, невыгодна тому, кто эти цифры составляет.
• экономическая. Реформа 1965 года пошла по другому пути — через хозрасчёт и прибыль предприятий, а не через центральный расчёт.
• техническая. Машин нужного класса и, главное, каналов связи в стране не было. С 1969 года промышленность перешла на копирование архитектуры IBM, и собственные линии, включая линию Глушкова, стали сворачивать.
• и та, что глубже прочих. Система предполагает, что первичные данные достоверны. В экономике, где выполнение плана определяет судьбу директора, отчётность есть предмет переговоров, а не измерения. Сеть, собирающая недостоверные данные быстрее, точнее не станет.

Ближайший аналог, доведённый до работающего состояния, — чилийский проект Cybersyn (1971–1973), закрытый военным переворотом. Он был меньше на несколько порядков.

Что осталось

Институт кибернетики работает и носит имя Глушкова. Автоматная теория — учебник. «Днепр» и «МИР» вошли в историю техники. Идея, что управление есть задача об информации, а не о воле, стала общим местом.

А сам вопрос — можно ли вычислить оптимальный план для целой страны — остался тем же, каким его оставил Канторович. Математика говорит: если данные есть, план вычисляется. Спор всегда шёл и идёт не о математике, а о слове «если».

Задача. Постройте автомат Глушкова для выражения $(a\mid b)^{*}a$.
(Ответ: позиции $a_1$, $b_2$, $a_3$. Начала $=\{1,2,3\}$, концы $=\{3\}$, следования: $\text{сл}(1)=\text{сл}(2)=\{1,2,3\}$, $\text{сл}(3)=\varnothing$. Состояний четыре: $q_0$ и три позиции. Из $q_0$ по $a$ — в 1 и 3, по $b$ — в 2; из 1 и из 2 — так же; из 3 никуда. Принимающее одно: 3. Заметьте, что автомат недетерминированный — по букве $a$ из одного состояния есть два перехода; это и означает, что дальше придётся либо перебирать, либо детерминировать.)

Следующая точка: Кембридж под Бостоном — где вопрос «замостят ли эти плитки плоскость» окажется вопросом без алгоритма.