«В. П. Одинец Зарисовки по истории компьютерных наук Учебное пособие Сыктывкар 2013 УДК 004:93 ББК 32.975 О 42 Печатается по решению редакционно-издательского совета Коми государственного педагогического института от ...»

б) некоторое состояние машины Поста (т. е. некоторую расстановку меток по ситуациям). При этом будем считать, что в начальном состоянии машины каретка ставится против секции с номером 02.

Каждая команда машины выполняется за один шаг, при этом если на k-ом шаге выполнялась команда с номером i, то, если эта команда имеет единственную отсылку j, на k + 1 шаге выполняется команда j; если же имеем команду передачи управления (и две отсылки j1 и j2), то, если секция к моменту выполнения этой команды была пуста, выполняется команда j1, если же секция была помечена, то следующей выполняется команда j2.

В процессе работы машины Поста осуществится один из трех сценариев:

I. В ходе работы машина дойдет до выполнения невыполнимой команды: печатания метки в непустой секции или стирания метки в пустой секции. При этом машина останавливается. Этот исход называют безрезультатным «остановом» (б.о.).

II. В ходе работы машина дойдет до выполнения команды stop (остановка). Этот исход называют результатным «остановом» (р.о.).

III. В ходе работы не будет остановки ни по первому, ни по второму сценарию, т. е. машина работает бесконечно.

Рассмотрим теперь, как записывается число на машине Поста. Для начала рассмотрим числа из 0= {0}. Число n будем записывать в виде (n + 1) отмеченных подряд ячеек (= секТ. е. для каждой отсылки каждой команды списка найдется в списке такая команда, номер которой равен рассматриваемой отсылке.

Тем самым начальное состояние машины полностью определено состоянием ленты.

ций)1. Обозначим через En совокупность всех таких состояний машины Поста, в каждом из которых на ленте будут помечены ровно (n + 1) секций, а каретка может стоять где угодно.

Обозначим через An En совокупность всех таких состояний машины Поста, в которых каретка стоит против самой левой из отмеченных секций. Обозначим через Cn En совокупность всех таких состояний, в которых каретка стоит слева от массива, а через Cn En совокупность всех таких состояний, когда каретка стоит справа от массива. Наконец, обозначим через Bn En совокупность всех таких состояний, когда каретка стоит против одной из отмеченных секций. По сути состояния An, Cn, Bn, En – это совокупности протоколов2 машины Поста.

Рассмотрим теперь 3 задачи, каждая из которых приводит к прибавлению 1 к числу n:

Задача: Написать программу машины Поста, которая для любого n 0 = {0}, будучи применена к произвольному состоянию из класса An (соответственно Bn, Cn ), дает результативный «останов» в каком-то состоянии из En1.

Решением первой задачи (назовем ее Аn) будет, например:

Решением второй задачи (Bn) будет, например:

Решением третьей задачи ( Cn ):

Отмеченные подряд секции называют массивами, а число ячеек (= секций) в массиве – его длиной.

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

Пусть теперь имеем два алгоритма A1 и A2, имеющих одинаковые области задания. Будем говорить, что A1 и A2 равносильны, если к любому исходному данному из их общей области задания они оба применимы (и в этом случае дают один и тот же результат), либо оба не применимы. В 1936 г. в работе [30] Э. Пост сформулировал свою знаменитую гипотезу («Гипотеза Поста»): каждый алгоритм, все результаты которого суть натуральные числа, а областью задания служат k k 1, k или, равносилен алгоритму с той же совокупностью возможных исходных данных, задаваемому некоторой программой машины Поста [31, с. 68–69].

либо на 0. Пусть результат применения А к любому исk ходному данному из 0 либо 0 (если такой результат существует) принадлежит 0. Положим:

Напомним, что про f говорят, что f вычисляется алгоритмом А или что алгоритм А вычисляет функцию f.

Функция f : k o (или o ) называется вычислимой, если существует алгоритм, ее вычисляющий [31].

лимой по Посту, если существует программа р машины Поста, вычисляющая функцию f, т. е. р обладает свойствами:

если f x0,..., xk y, то программа р, применяемая к исходному данному x0,..., xk, заканчивает работу, оставляя на ленте запись числа «у».

если f x0,..., xk (т. е. не определено), то применение программы р к x0,..., xk не приводит к результативной остановке.

Теперь можно напомнить и знаменитый тезис Поста:

Пусть Е одно из множеств k (k ),. Тогда класс выo числимых функций из Е со значениями в 0 совпадает с классом функций из Е со значениями в 0, вычислимых на машине Поста.

Исторически сложилось так, что в том же 1936 г., когда была опубликована статья Э. Поста [30], Алонзо Черч (Alonzo Church:

1903–1995) опубликовал работу [32], в которой был тезис («тезис Черча»), равносильный тезису Поста:

Всякая всюду определенная вычислимая числовая функция является общерекурсивной1.

Позже, в 1952 г. Стивен Клини (Stephen Kleene: 1909–1994) обобщил тезис Черча: всякая (не обязательно всюду определенная) вычислимая функция частично рекурсивна. Этот тезис, называемый «тезисом Клини-Черча», также эквивалентен тезису Поста.

Существуют и другие утверждения, эквивалентные тезису Черча: прежде всего утверждение, связанное либо с введенным в 1936 г. ленточным автоматом Алана Тьюринга (Alan Turing:

Напомним, что частично рекурсивными называются функции, которые могут быть получены из тождественно нулевой функции и функции прибавления единицы ( f x x 1 ) с помощью трех операций: 1) подстановки (функций в функцию), т. е. суперпозиции; 2) рекуррентного (= индуктивного, = рекурсивного) определения функции. Частично рекурсивные функции в общем случае определены не всюду. Если же частично рекурсивная функция определена всюду, то ее называют общерекурсивной (подробнее см. § 9). Здесь уместно добавить, что как работа Э. Поста [30], так и работа А. Черча [32] были развитием теоремы К. Геделя (Kurt Gdel: 1906–1978) о неполноте символических логик [33].

1912–1954) [34; 35], либо с «нормальными алгорифмами А. А.

Маркова», либо с «алгоритмами А. Н. Колмогорова» и др.

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

Итак, пусть (в десятичной системе счисления) встречается d) q1 : 0,1, где q1 w, если в разложении числа есть сколь угодно длинные отрезки из девяток и q1 v, в противном случае.

Наконец, рассмотрим функцию h :

Так вот, интуиционисты1, начиная от Л. Э. Я. Брауэра (L. E. J.

Brouwer: 1881–1966), отвергают следующее утверждение:

Можно также доказать, что если утверждение (*) верно, то, в силу очевидной вычислимости функций v и w, функция q также Подробнее см. [37; 48], при этом автор книги [48] Аренд Гейтинг (Arend Heyting: 1898–1980) сам был учеником Л. Брауэра.

будет вычислима. Что касается функции h, то неизвестно, вычислима эта функция или нет!

Упражнения 1. а) Выписать все программы машины Поста длины 1.

б) Сколько существует программ машины Поста длины 2, длины 3, длины n? n 4.

2. Существует ли программа машины Поста, дающая при любом начальном состоянии:

а) результативную остановку;

б) безрезультативную остановку;

в) неограниченное продолжение работы?

Каково наименьшее число команд в этих программах?

3. Доказать, что если для некоторой программы известно, что существуют 3 начальных состояния, для которых программа дает соответственно: результативный «останов», безрезультативный «останов», неограниченное продолжение работы, то число qкоманд в этой программе не менее 4. Написать все эти программы длины 4.

4. а) Написать такую программу машины Поста, которая, будучи примененной к произвольному состоянию En(n 0), дает результативный «останов» в каком-либо состоянии из класса En1.

б) Существует ли при этом программа из менее чем 23 команд?

5. Пусть q 0\{1}. Составить программу сложения произвольного количества чисел, записанных на произвольных, но не превосходящих q расстояниях друг от друга.

6. Пусть f : 20 0 такая, что Функцию f называют вычитанием.

Составить программу вычитания одного числа из другого, учитывая, что если f x, y, то программа не должна приводить к результативной остановке.

7. Составить программу деления чисел на 2, 3, 4, …, k. Под делением будем понимать вычисление функции 8. Составить программу умножения двух чисел (x, y).

9. Составить программу вычисления квадрата числа x.

10. Докажите, что множество программ машины Поста не более чем счетно.

11. Пусть множество программ машины Поста пронумеровано (см. упр. 10). Пусть f : 0 = {0}, такая, что не приводит к результативному “останову ” или если результат не есть запись натурального числа;

дает результат, являющийся записью числа k.

Доказать, что так построенная функция не вычислима на машине Поста.

Указание: Рассмотреть оба случая. При этом в случае отсутствия результативного «останова» или, если результат не есть запись никакого натурального числа, учесть, что программа не вычисляет f потому, что f определена на всем.

§ 8. Вычислительная модель Тьюринга.

Машина фон Неймана Как уже отмечено выше, 1936 г. был годом появления сразу трех выдающихся работ по теории алгоритмов: Э. Поста, А. Тьюринга и А. Черча соответственно. Отметим, что в примечании редакции к статье Э. Поста сказано: «Читателю рекомендуется сравнить статью А. М. Тьюринга “О вычислимых числах”, долженствующую появиться вскоре в журнале “Лондонского математического общества”. Настоящая статья [т. е. статья Поста], однако, хотя и имеет более позднюю дату1, написана совершенно независимо от статьи Тьюринга».

Что же убедило редакцию журнала в этом утверждении?

Прежде всего то, что машины Поста и Тьюринга описывают разные вычислительные модели.

Итак, машина Тьюринга – это ленточный автомат с двумя алфавитами – внутренним (называемым также алфавитом состояний) алфавитом S q0, q1,..., qn, содержащим всегда начальное состояние q0 и q1 – конечное состояние, и внешним, состоящим из произвольных символов, который содержит символ a0 (пустоты секции (= ячейки)) и не содержит символов внутреннего алфавита, а также содержит символы R и L.

Напомним, что машина Тьюринга управляется командами трех типов:

1) qi a q j b, если в состоянии qi S наблюдается ячейка с символом a, то перейти в состояние q j S и поместить в данную ячейку символ b.

Статья Тьюринга поступила в редакцию 28 мая 1936 г., а статья Поста – осенью того же года.

2) qi a q j bR, если в состоянии qi S наблюдается ячейка с символом a, то перейти в состояние q j S и поместить в данную ячейку символ b, после чего перейти к обозрению соседней справа ячейки.

3) qi a q jbL, если в состоянии qi S наблюдается ячейка с символом a, то перейти в состояние q j S и поместить в данную ячейку символ b, после чего перейти к обозрению соседней слева ячейки.

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

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

Команда считается применимой к данной комбинации на ленте, если в этой комбинации в качестве подслова встречается левая часть этой команды.

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

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

Машиной Тьюринга называют пару алфавитов и программу над ними.

Их называют бланками.

Заметим, что, как и машина Поста, машина Тьюринга относится к числу ленточных автоматов.

Скачок в теории алгоритмов был сделан еще во время Второй мировой войны великим американским математиком Джоном фон Нейманом (John (Janos) von Neumann: 1903–1957). Им была создана модель компьютера (компьютер фон Неймана), удовлетворяющая трем принципам:

1. Программа состоит из набора команд, которые выполняются (автоматически) в определенной последовательности друг за другом (= принцип программного управления).

2. Основная память состоит из перенумерованных ячеек; при этом процессору в любой момент доступна каждая ячейка (= принцип адресности).

3. Программы и данные хранятся в одной и той же памяти, и над командами можно выполнять те же действия, как и над данными (= принцип однородности памяти).

Таким образом, компьютер фон Неймана имеет как минимум три элемента:

а) центральный процессор, выполняющий команды программы;

б) оперативную память, в которой хранится программа и обрабатываемые ею данные;

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

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

Прежде чем перейти к другим вычислительным моделям (нормальным алгорифмам А. А. Маркова и частично-рекурсивным функциям), напомним некоторые этапы жизни К. Геделя, Э. Поста, А. Тьюринга и Дж. фон Неймана.

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

Начнем с Курта Геделя (Kurt Gdel: 1906–1978), чьи теоремы о неполноте (1931)1 оказали огромное влияние на других членов четверки.

Родившись в Австро-Венгрии в городе Брюни (ныне Брно – Чехия), побывав гражданином Чехословакии, затем Австрии, а с поглощением Германией в 1936 г. Австрии – гражданином Германии, Курт Гедель в г. бежит через СССР в США. Там он работает в Институте Перспективных Исследований в Принстоне (штат Нью-Джерси) до самой смерти (от истощения, в силу психического забоКурт Гедель левания) [51].

Сформулируем «пунктиром» только одну из них: «Любая эффективно аксиоматизируемая теория (т. е. теория, в которой есть возможность алгоритмически решить, является ли данное утверждение аксиомой) в достаточно богатом языке, т. е. языке, в котором можно определить понятие натурального числа и операций сложения и умножения, является либо неполной, либо противоречивой». Неполнота, напомним, означает наличие высказываний, которые нельзя ни доказать, ни опровергнуть, исходя из аксиом этой теории, а противоречивость – это возможность доказать любое высказывание, как истинное, так и ложное.

Теперь несколько слов о родившемся в 1897 г. в Российской Империи в Августове (теперь Польша) Эмиле Посте. Его отец в том же 1897 г. уезжает (с братом) на заработки в США, отсылая деньги жене на троих детей. В 1904 г. семья соединилась в НьюЙорке в Гарлеме. С детства Эмиль интересовался астрономией, позже математикой. В 1917 г. он получил степень бакалавра по математике в Городском колледже (City College) Нью-Йорка. В 1917–1920 гг. Э. Пост учится в аспирантуре Колумбийского университета; в 1920–1921 гг. – стажер Принстонского университета.

А уже в 1923 г. Эмиль Пост в сообщении, сделанном на ежегодном съезде Американского матобщества (AMS), обобщил понятие дифференцируемости, опубликованном в 1930 г. [109].

С 1932 г. и до конца жизни (1954) Э. Пост преподает в Городском колледже. Основные работы Э. Поста (кроме создания ленточного автомата) связаны с математической логикой [50]. (О значении этих работ для представления знаний в системах искусственного интеллекта будет сказано в главе III § 13.) Лондоне, куда семья возвратилась из Индии, где его отец был служащим администрации2. В 6 лет Алана отдают в школу А. Тьюринг принял яд после двухлетней травли, связанной с его гомосексуальностью.

British Civil Service.

левском Колледже (King’s College); в 1935 г. заканчивает учебу в Кембриджском университете. В 1936 г. А. Тьюринг публикует свою версию ленточного автомата.

Во время Второй мировой войны А. Тьюринг участвует в работах по дешифровке немецких радиодонесений (раскрытию секретов «Enigma») (см. выше). Работая над созданием программ для вычислительных машин, А. Тьюринг в 1949 г. строит первую шахматную программу. Он фактически подошел вплотную к изучению проблемы NP-сложности, не решенной до сих пор [52; 53].

Родившийся, как и Курт Гедель, в Австро-Венгрии (Будапешт) Джон фон Нейман (John von Neumann: 1903–1957) был одним из величайших математиков XX в. Дж. фон Нейман был старшим сыном известного еврейского банкира, получившего титул барона при Императоре (1848–1916) Франце Иосифе I (1830– 1916). Венгерское имя Янош трансформировалось при переезде в США в 1933 г. в Джон. В 17 лет отец, желавший видеть сына продолжателем своего банкирского дела, соглашается с выбором сына в качестве основной специальности химии как компромисс между увлечением сына математикой и необходимостью изучать финансы. В 18 лет Нейман покидает Венгрию и становится студентом Берлинского университета (1921–1923), позже он продолжил учебу в Цюрихе в Технологическом институте (1923– 1925). В 1926 г. он получает два дипло- Джон фон Нейман ма: инженера-химика в Цюрихе и диплом доктора1 наук (по математике) за диссертацию по теории множеств.

В том же 1926 г. фон Нейман был, как он позже вспоминал, «раздавлен» опубликованным парадоксом Банаха-Тарского2 о том, что трехмерный шар евклидова пространства равносоставлен (из конечного числа кусков) двум своим копиям (см. [39– 40]).

И в доказательстве парадокса Банаха-Тарского, и в доказательстве теоремы Хаусдорфа3 особую роль играет следующая схема:

1. Ищется специальное разбиение некоторой группы Г с двумя образующими на три подмножества.

2. Строится свободное изометрическое действие этой группы на заданное множество (это шар в парадоксе Банаха-Тарского и S2 – в теореме Ф. Хаусдорфа).

3. Используется разбиение Г и аксиома выбора, чтобы произвести нужное разбиение шара (соответственно сферы) [41].

В 1929 г.4 размышления фон Неймана над этим парадоксом привели его к понятию аменабельной дискретной группы5, значение которой для развития теории алгоритмов постоянно возрастает.

Соответствует степени кандидата наук в России.

Парадокс Банаха-Тарского и теорема Ф. Хаусдорфа доказываются фактически одинаково. В парадоксе Банаха-Тарского это сделано с помощью сдвига.

В 1914 г. Ф. Хаусдорф доказал теорему о том, что двумерная сфера S2 c проколотым счетным множеством Т (т. е. S 2 S 2 \ T ) может быть представлена в конгруентны друг другу и конгруентны В и С.

В 1939 г. аменабельные топологические группы стал рассматривать Н. Н. Боголюбов.

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

С 1927 г. фон Нейман начинает преподавать математику в германских университетах: в 1927–1929 гг. – в Берлинском, в 1929–1930 гг. – в Гамбурге. Усиление влияния нацистов в Германии вынуждает фон Неймана принять решение об эмиграции в США. С 1933 г. он преподает математическую физику в Принстонском университете. Принятию в столь престижный университет способствовала вышедшая в 1932 г. книга Дж. фон Неймана о математических основах квантовой механики и плодотворное использование в ее изложении математической логики [42].

Еще работая в Берлинском университете, фон Нейман сделал попытку математической формализации теории конфликтов, названных им деликатно «общественными играми» (см. [38]).

Развитие этой работы привело через 16 лет (в 1944 г.) к появлению основополагающего труда (совместно с Оскаром Моргенштерном (Oskar Morgenstern: 1902–1977) «Теория игр и экономическое поведение», оказавшего огромное влияние на развитие социологии, экономики и военного дела [43].

В 1933 г. Дж. фон Нейман избирается профессором Института прикладных исследований в Принстоне и работает там до своей кончины в 1957 г. В 1943–1955 гг. он одновременно является консультантом Научно-исследовательской лаборатории в ЛосАламосе, занимавшейся «атомным» проектом. Для решения вычислительных задач, возникавших в рамках этого проекта, фон Нейман и предлагает свою концепцию вычислительной машины.

В 1952 г. под его руководством заканчивается строительство компьютера в Принстоне, реализующего его идеи (см. выше гл. I, а также [54]).

§ 9. Вычислительные модели Маркова и Клини В 1949 г. сын знаменитого российского математика А. А. Маркова (1856–1922) Андрей Андреевич Марков (младший) (1903–1979) создал свою вычислительную модель, столь же наглядную, как и ленточные автоматы Поста и Тьюринга, но использующую меньшее число команд (см. [44; 46]).

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

A B (замена в текущем слове подслова1 А на слово В) Команда в модели Маркова считается применимой к данному слову, если ее левая часть является подсловом к слову становится новое слово, отличающееся от исходного тем, что первое слева вхождение подслова А заменено словом В.

Слово «с» является подсловом слова «в», если «в» представимо в виде b lar, где l и r некоторые, возможно, пустые слова. (Пустое слово будем обозначать через ).

Очередной шаг в модели Маркова заключается в том, чтобы в списке команд найти первую, применимую к текущему слову.

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

Например, пусть дан алфавит a, b и пусть задан алгорифм Маркова над этим алфавитом формата: a b. Этот алгорифм меняет первую слева букву «а» обрабатываемого слова на букву «в», пока команда не перестанет быть применимой, т. е. алгорифм заменяет все буквы «а» исходного слова на буквы «в» [46].

Что же послужило толчком к появлению нормального алгорифма Маркова? Это связано прежде всего с развитием конструктивной математики, берущей свое начало в трудах Лейтзен Эгберта Яна Брауэра (Luitzen Egbert Jan Brouwer Luitzen Egbert Jan:

1881–1966)1 и Германа Вейля (Hermann Weyl: 1885–1955) [47].

Их критические тезисы об имевших хождение в тот период теоремах существования, не «предъявлявших» конкретного объекта, фактически были направлены против «жонглирования» понятием актуального бесконечности. Они выступили инициаторами создания математики (прежде всего математического анализа), в которой в качестве объектов изучения фигурируют лишь конструктивно определяемые объекты. (Такое направление в математике было названо интуиционизмом) (см. [47; 48; 55]).

К сожалению, достаточно длительно неприятие большинством математического сообщества этих идей, ограничивающих, по мнению многих математиков, математический инструментарий, Brouwer L. E. J. Intuitionisme en formalisme. – Amsterdam, 1912.

привело к определенным трудностям в изучении основ самой математики.

А. А. Марков высказал в 40-х гг. мысль о том, «что различные идеализации, фактически применяемые в современной математике, далеко не одинаковы с точки зрения возможности содержательного истолкования математических теорем, в основе которых лежат эти идеализации». В настоящее время имеется реальная возможность осуществлять пересмотр основ анализа. Она обеспечивается разработанностью теорий, связанных с точным определением таких понятий, как «вычислимая арифметическая функция» и «алгорифм» [46, с. 315–316].

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

В приведенной выше цитате А. А. Маркова упомянута «вычислимая арифметическая функция».

удовлетворяло и понятие мощности бесконечных множеств, когда часть может Стивен Клини А. А. Марков был разносторонним математиком. Основные труды у него были по топологии, топологической алгебре, теории динамических систем, конструктивной математике и теории алгоритмов (= алгорифмов). (Биография А. А. Маркова дана в § 10.) Kleene S. C. On the interpretation of intuitionistic number thory // J. Symb.

Logic. – 10 (1945). – P. 109–124.

По этому поводу отметим, что обойти трудности актуальной бесконечности математики попытались с помощью нестандартного анализа (подробнее см. [3; 49]). Но пока в этой области реальные новые результаты еще сравнительно скромны.

Другой подход возник на рубеже XX и XXI вв. и связан с работами нижегородского математика Ярослава Дмитриевича Сергеева (р. 1963). Он придумал арифметику, восходящую к идеям итальянских математиков последней трети XIX в., включая У. Дини (1845–1918), Д. Пеано (1858–1932), и объединяющую конечные и бесконечные числа2. В основе этой арифметики лежит понятие гросс-единицы (grоssone). Гросс-единица – это бесконечное число, обозначаемое через, равное по определению количеству элементов в – множестве натуральных чисел, т. е.

1,2,3,...., 1,, а – самое большое натуральное число3.

Это число выбирается в качестве основания новой системы счисления. Множество конечных и бесконечных чисел можно раскрыть как Ловягин Ю. Н. Гиперрациональные числа как основа математического анализа // Вестник Сыктывкарского ун-та. – Сер. 1. – Вып. 7 (2007). – С. 17–34.

Не путать с порядковыми числами.

Роль Ф фактически сравнима в вычислительных процессах с ролью бесконечно большого числа М в М-задачах при использовании симплекс-метода.

Отметим, что множество всех четных положительных чисел содержит /2 чисел.

Через 1/ обозначают простейшее по записи бесконечно малое число.

Важным постулатом для арифметики Сергеева является следующий: любой процесс суммирования содержит не более Ф шагов1.

Вернемся теперь вновь в 1936 г. Кроме работ Поста и Тьюринга о ленточных автоматах, о которых шла речь выше, в этот год появились две работы С. К. Клини «Общие рекурсивные функции натуральных чисел» [56] и «Определяемость и рекурсивность»2.

В этих работах Клини уже практически отвечает Э. Посту, который написал в своей работе «Финитные комбинаторные процессы»: «Автор ожидает, что его формулировка (т. е. вычислимости по Посту) окажется логически эквивалентной рекурсивности в смысле Геделя-Черча» [30].

Напомним, что три следующие функции называют простейшими. Число в верхнем индексе будет означать количество переменных. Сами функции – это функции нескольких натуральных переменных со значениями из множества 3) I n x1,..., xn,..., xm xn, 1 n m – выбор (или проекция).

Sergeyev Ya. D. Arithmetic of infinity. – Edizioni Orizzonti Meridionali, CS.

2003. – 112 p.

Kleene S. K. Definability and recusiveness // Duke Math. J. – V. 2 (1936). – P. 340–353.

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

будем называть оператором примитивной рекурсии.

Функцию называют общерекурсивной, если она частично рекурсивна и всюду определена.

Наконец, примитивно рекурсивными называют функции, получаемые из простейших с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Впервые общерекурсивная функция, не являющаяся примитивно рекурсивной, была построена учеником Д. Гильберта Вильгельмом Аккерманом (Wilhelm Ackermann: 1896–1962) в бытность его еще студентом, но доказательство того, что она не будет примитивно рекурсивной, им дано только в 1928 г. Широко распространенное в информатике видоизменение функции Аккермана, зависящей уже только от двух аргументов, принадлежит Руже Петер (Политцер) (Rzsa Pter: 1905–1977) и Рафаэлю Робинсону (Raphael Mitchel Robinson: 1911–1995) (см. [45, с. 5]).

Функция двух переменных Аккерма- Ружа Петер на-Петер имеет следующий вид:

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

Отметим, что А. А. Марков дополнил существенно теорему С. К. Клини о представлении частично рекурсивных функций через примитивно рекурсивные, – точнее, им дана полная характеризация примитивно рекурсивных функций, допустимых в качестве внешней функции в формуле С. К. Клини1 (см. [55]).

А теперь несколько слов о творцах теории рекуррентных функций: С. С. Клини, В. Аккермане, Р. Петер и Р. Робинсон, а также о научном руководителе С. К. Клини – профессоре Алонзо Черче (Alonzo Church: 1903–1995).

А. Черч родился в Вашингтоне в семье судьи. Степень бакалавра получил в Принстонском университете в 1924 г. Степень Ph. D. – там же в 1927 г. Затем один год преподавал в университете Чикаго. Позже по одному году был на стажировке в универKleene S. On the forms of the predicates in the theory of constructive ordinals // Amer. J. Math. – V. 66 (1944) (см. также [57]).

ситетах Гарварда, Геттингена и Амстердама. Начиная с 1929 г., Черч преподает в университете Принстона (до 1967 г.), а затем в Калифорнийском университете в Лос-Анджелесе (до 1990 г.).

После статьи 1936 г. [32], в которой были продемонстрированы алгоритмически неразрешимые задачи, Черч построил теорию -исчисления, которое имело свойства, одинаковые с машиной Тьюринга1.

Стивен Коул Клини (Stephen Cole Kleene: 1909–1994) родился и жил в США. В 1930 г. он получил степень бакалавра в Амхерст Колледже, а степень Ph. D. в 1934 г. в Принстонском университете, где его научным руководителем был Алонзо Черч.

С 1935 г. С. К. Клини был связан с университетом Висконсин-Мэдисон. В 1939–1941 гг. он был на стажировке в Принстонском Институте Перспективных исследований. Когда США стали участвовать во Второй мировой войне (1941–1945), С. К. Клини служил в Военно-морском флоте США в качестве инструктора по навигации. В 1961 г. С. К. Клини избирается президентом Международного союза истории и философии науки [58]. Наиболее знаменита его книга «Введение в метаматематику».

Вильгельм Аккерман (Wilhelm Ackermann: 1896–1962) – немецкий математик. Он поступил в университет в Геттингене в 1914 г., продолжил там же учебу после Первой мировой войны. В 1925 г. под руководством Д. Гильберта он защищает диссертацию и получает степень Ph. D. В течение четырех лет (с перерывом на поездку в Кембридж на полгода как Рокфеллеровский стипендиEnderton H. B. In memorian: Alonzo Church // The Bull. оf Symbol. Logic. – Vol. 1. – No 4 (Dec. 1995). – P. 486–488.

ат), В. Аккерман исполняет обязанности секретаря Д. Гильберта. С Арнольдинум (Arnoldinum) в Бургштайнфурте и затем в Люденшайде1. В «Философские замечания относительно математической логики и исследований оснований математики», сразу Вильгельм Аккерман [59]. За работы по теории множеств и основаниям логики В. Аккерман был избран почетным профессором университета в Мюнстере.

Ружа Петер (Rzsa Pter в девичестве Politzer) (1905–1977), поступив в Университет Эствос Лоранд, намеревалась изучать химию, но начав слушать лекции всемирно известного математика Липота Фейера (Lipt Feier: 1880–1959), заинтересовалась математикой. Другой математик Лашло Кальмар (Lszl Kalmar:

1905–1976) впервые обратил ее внимание на рекурсивные функции. В 1932 г. на IX Математическом Конгрессе в Цюрихе была представлена ее работа, в которой исследователь впервые предложила выделить изучение рекурсивных функций в отдельное направление. В 1935 г. Ружа Петер получает степень Ph. D. и ее приглашают в журнал «Symbolic Logic» редактором. Во время Второй мировой войны она была в Будапештском гетто, чудом выжила. После войны Ружа Петер преподает в педагогическом Remus D. Professor Wilhelm Ackerman, Lehrer am Arnoldinum und Forscher in der Mathematik // 400 Jahre Arnoldinum 1588–1988. Festschrift. – Greven, 1988. – S. 211–219.

колледже, а затем с 1955 г. она уже профессор университета, в котором когда-то училась. В 1951 г. выходит ее монография «Рекурсивные функции», а в 1976 г. – знаменитая книга «Recursive Functions in Computer Theory». Именно выход этой книги способствовал использованию функции Аккермана-Петер для графического изображения всевозможных поверхностей, использующихся в строительстве, навигации и военном деле.

Другим видоизменением оригинальной функции Аккермана занялся Рафаэль Митчелл Робинсон (Raphael Mitchel Robinson:

1911–1995). Он родился в Калифорнии. В 1932 г. получил степень бакалавра, а в 1935 г. – Ph. D. Обе степени – по математике, в Университете Беркли. Вскоре после 1942 г. начинается его интенсивная работа над теорией «существенной неразрешимости»

А. Тарского (в 1939 г. Тарский переезжает из Польши в США), завершившаяся изданием в 1953 г. совместного труда «Неразрешимые теории»1 (в 1941 г. Р. М. Робинсон женится на своей бывшей студентке Джулии Баумэн (Julia (Bowman) Robinson: 1919–1985), ставшей самой известной женщиной-математиком второй половины XX в., первой женщиной-президентом Американского Математического общества). Отметим еще его работы (1952) по компьютерному изучению чисел Мерсенна, т. е. простых чисел вида M n 2n 1. Проблема су- Джулия Робинсон Tarski A., Mostowski A., Robinson R. M. Undecidable theories. – Amsterdam:

North Holland, 1953.

ществования бесконечного множества чисел Мерсенна до сих пор не решена1.

Упражнения Составить протоколы Алгорифмов Маркова для следующих задач:

§ 10. Проблемы разрешимости и перечислимости Вернемся теперь к проблеме алгоритмической разрешимости.

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

Пусть PM – произвольный предикат, заданный на более чем счетном множестве Мо. Этому предикату PM соответствует частичное отображение f M : M 0 0,1.

Henkin L. In memoriam: Raphael Mitchell Robinson // Bull. Symbol. Logic (1995). – P. 340–343.

Прообраз M f M 1 1 m M 0 : f M m 1 – множество истинности предиката. Предикат PM и соответствующее множество Мо называют перечислимыми, если функция f M вычислима, т. е. существует алгоритм, который для любого набора значений m переменных, принадлежащего области определения предиката, за конечное число шагов определяет истинное или ложное значение предиката, или, что равносильно, перечислимое множество М может алгоритмически генерироваться (т. е. что существует вычислимая генерирующая последовательность gg:: 0 M 0 1, такая, что g ( 0) = М).

Перечислимое множество М (перечислимый предикат PM ) называют разрешимым, если область определения соответствующей ему вычислимой функции f M : M 0 0,1 совпадает с универсальным множеством для f M : M 0 0,1.

Существуют перечислимые множества, но не разрешимые.

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

Более того, имеет место строгое утверждение: подмножество M N перечислимо тогда и только тогда, когда для него можно построить разрешимое множество P 2 так, что Знак означает отображение «в», при этом область D задания f M может быть частью некоторого универсального множества H 0, которое замкнуто относительно операций объединения, пересечения и дополнения подмножеств из M 0. Например, функция f x 1/ x, при x 0. Тогда в качестве M 0 возьмем [0,1].

мой всюду ее продолжением, а это неверно.

Иными словами, множество перечислимо тогда и только тогда, когда оно является проекцией разрешимого множества.

Впервые применил полученный результат к разделу математической логики (теория доказательств) в 1943 г. Эмиль Пост1.

Его результат гласит: множество всех выводимых в явно заданной формальной аксиоматической теории формул перечислимо.

Предположим теперь, что задано порождающее множество (алфавит) и конечное число определяющих соотношений. Рассмотрим следующую массовую проблему : являются ли равномерными два данных слова над исходным алфавитом при заданных определяющих соотношениях?

В 1947 г. А. А. Марков и Э. Пост опубликовали независимо друг от друга следующий результат2: Для решения проблемы с произвольным набором определяющих соотношений алгоритма не существует, и, более того, для некоторых полугрупп с заданной системой определяющих соотношений нет алгоритма, распознающего равенство слов3.

В 1956 г. Григорий Самуилович Цейтин (р. 1936) привел простой пример4 такой полугруппы с 5 образующими a, b, c, d, e и определяющими соотношениями:

Post E. L. Formal Reductions of the General Combinaterial Decision Problem // Amer. J. of Math. – 66 (1943). – P. 197–215.

Post E. L. Recursive unsolvability of problem of Thue // Journ. Symb. Logic. – № 12 (1947). – Р. 1–11.

Марков А. А. Невозможность некоторых алгоритмов в теории ассоциативных систем // ДАН СССР. – Т. 55 (1947). – С. 587–590.

Цейтин Г. С. Ассоциативное исчисление с неразрешимой проблемой эквивалентности // ДАН СССР. – Т. 107. – № 3 (1956). – С. 370–371.

Заметим, что еще в 1950 г. А. М. Тьюринг построил полугрупповое исчисление с сокращениями, для которого неразрешима проблема распознавания эквивалентности слов. В 1952 г.

П. С. Новиков, основываясь на этой работе А. М. Тьюринга, построил конечно-определенную группу с неразрешимой проблемой распознавания эквивалентности слов [64].

В 1958 г. А. А. Марков решил проблему гомеоморфии, т. е.

проблему разыскания «алгоритма», распознающего для любых данных полиэдров, гомеоморфны ли они.

При этом полиэдры задаются комбинаторно их триангуляциями. Решение было отрицательным, т. е. проблема гомеоморфии неразрешима1. При этом А. А. Марков ограничился полиэдрами специального вида: а именно, n-мерными многообразиями, где n 4. В качестве базового было взято четырехмерное многообразие с заданной фундаментальной группой, строящееся аналогично построению из книги Г. Зейферта и В. Трельфалль2. Далее использовался результат С. П. Адяна (1955)3 об алгебраической неразрешимости проблем распознавания некоторых свойств групп.

Отметим, что для трехмерных многообразий проблема разрешимости не решена даже с учетом доказательства гипотезы Торстена (Thorsten Ekedahl: 1955) о классификации трехмерных многообразий, данного Г. Я. Перельманом в 2003 г.

(для n 2 проблема гомеоморфии для многообразий разрешима.) Марков А. А. Неразрешимость проблемы гомеоморфии // ДАН СССР. – Т. 121. – № 2 (1958). – С. 218–220.

Зейферт Г., Трельфалль В. Топология. – М.; Л., 1938.

Адян С. И. Алгоритмическая неразрешимость проблем распознавания некоторых свойств групп // ДАН СССР. – Т. 103. – № 4 (1955). – С. 533.

Григорий Яковлевич Перельман (р. 1966) окончил в 1983 г.

знаменитую физико-математическую школу № 239 (в Ленинграде), затем учился на математико-механическом факультете ЛГУ и в аспирантуре при Ленинградском отделении Математического института (сокращенно ЛОМИ) им. В. А. Стеклова АН СССР (с 1992 г. – ПОМИ), где и работал после защиты кандидатской диссертации. В конце 80-х гг. уехал на 6 лет в США, там он был на должностях профессора-исследователя в разных университетах, включая институт Куранта (R. Courant Institute) Нью-Йоркского университета и университет Беркли (University of California, Berkeley).

В 1995 г. Г. Я. Перельман вернулся в Санкт-Петербург в ПОМИ, но вместо лаборатории геометрии, где он работал до отъезда в США, он стал работать (до 2006 г.) в лаборатории математической физики – и это не случайно. Именно аппарат математической физики, точнее изучение потока Риччи-Гамильтона – нелинейного аналога уравнения теплопроводности, – позволило Г. Я. Перельману в 2002 г. доказать гипотезу Торстена о полной классификации компактных трехмерных многообразий, и – как частный случай, – гипотезу Пуанкаре: всякое односвязное компактное трехмерное многообразие без края гомеоморфно трехмерной сфере.

В 2006 г. Г. Я. Перельман был удостоен Филдсовской медали (и премии), а в 2009 г. – премии Клея1, которые он не принял.

В связи с трехмерными многообразиями выделим особо нерешенную, так называемую, алгоритмическую проблему Пуанкаре. Известно, что каждая трехмерная поверхность задается некоторым дискретным кодом – конечным набором символов. При этом одна и та же поверхность имеет бесконечное число различМатематический институт и премия были учреждены в 1998 г. бостонским бизнесменом Л. Т. Клеем (Clay Landon T.) и его женой Лавинией Д. Клей (Lavinia D. Clay).

ных кодировок. Алгоритмической проблемой Пуанкаре называют проблему существования алгоритма, определяющего по заданному кодовому слову, задает ли оно трехмерную сферу (подробнее см. [61]).

Приведем теперь биографии упомянутых выше А. А. Маркова (1903–1979), П. С. Новикова (1901–1975) и Г. С. Цейтина (р. 1936).

Как было уже сказано в начале § 9, Андрей Андреевич Марков (мл.) родился в семье выдающегося русского математика А. А. Маркова (1856–1922). А. А. Марков (мл.) до 1953 г. жил и работал в Санкт-Петербурге – Петрограде – Ленинграде, за исключением двух лет (1942–1944), когда его эвакуировали из блокадного города. В 1919–1924 гг. он учился в Петроградском университете (окончил в 1924 г.), затем в аспирантуре Астрономического института. В 1935 г. ему без защиты присвоена степень доктора физико-математических наук, за работы по теории динамических систем и работу о конечномерных векторных пространствах1, а в 1936 г. он становится профессором и заведующим кафедрой геометрии2 Ленинградского государственного университета. Идеи конструктивизма овладели А. А. Марковым еще в предвоенные годы – он организовал в Ленинграде семинар, где разбирались работы А. Черча, С. К. Клини, А. М. Тьюринга и Э. Поста. Поэтому выход в 1954 г. его знаменитой книги «Теория алгорифмов» [46] был подведением итогов размышлений о необходимости «коструктивизирования математики».

Марков А. А. О векторных пространствах конечной размерности // Труды II Всесоюзного математического съезда. – М.; Л.: Изд-во АН СССР. – Т. (1934). – С. 138–175.

А. А. Марков заведовал кафедрой геометрии с 1936 по 1942 г. и с 1944 по 1953 г.

В 1953 г. А. А. Марков начинает строить «конструктивный»

математический анализ (не путать с конструктивной теорией функций, см., например, классическую монографию И. П. Натансона 1949 г.)1. Конструктивная функция действительного переменного, по Маркову, оказалось, не может иметь точек разрыва2.

Более того, как показал в 1962 г. Г. С. Цейтин, такая функция в любой точке непрерывна, т. е. для нее может быть указан алгоритм, перерабатывающий всякий 0 в соответствующий (по Коши) [63].

С 1953 по 1959 г. основным местом работы А. А. Маркова становится Математический институт им. В. А. Стеклова, а с 1959 до 1979 г. – кафедра математической логики в МГУ им.

М. В. Ломоносова, где он начал осуществление проекта изложения конструктивной математической логики в общем контексте конструктивной математики (см., например, [62]).

Говоря о А. А. Маркове, следует также упомянуть о его роли в развитии отечественной криптографии.

В 1953 г. членом-корреспондентом АН СССР одновременно с А. А. Марковым стал Петр Сергеевич Новиков, коренной москвич. Московский университет П. С. Новиков оканчивает в г., затем учится в аспирантуре (научный руководитель – Н. Н. Лузин (1883–1950)). С 1929 г. П. С. Новиков преподает в Химикотехнологическом институте им. Д. И. Менделеева. Наконец, с г. и до конца жизни (1975) П. С. Новиков работает в Математическом институте АН СССР, совмещая с преподаванием в МГПИ им. Ленина.

Натансон И. П. Конструктивная теория функций. – М.; Л.: ГИТТЛ, 1949. – 688 с.

Марков А. А. Непрерывность конструктивных функций // Сб. материалов научной сессии ЛГУ 1952/1953. Секция математических наук. – Л.: Изд-во ЛГУ, 1952. – С. 22–23.

Разработанный П. С. Новиковым «принцип сравнения индексов»1 позволил дать решение одной из проблем дескриптивной теории множеств, что в дальнейшем привело к ее использованию в теории селекторов и, как следствие, в различных компьютерных технологиях (представление Новикова – Кастэна)2. В 1952 г. П. С. Новиков получает доказательство алгоритмической нераз- П. С. Новиков решимости проблемы тождества [64], а тремя годами позже (1955)3 – алгоритмической неразрешимости проблемы тождества слов в конечно-определенных группах, поставленных еще в 1912 г. М. Дэном (1878–1952). Дальнейшие результаты в этом направлении были получены П. С. Новиковым совместно с его учеником (по МГПИ), будущим академиком РАН, Сергеем Ивановичем Адяном (р. 1931) в 1958–1968 гг. [65], включая и решение (1968) знаменитой проблемы Бернсайда4.

Novikoff P. Fonctions implieities mesurablies // Fund. Math. – Bd 17 (1931). – P. 8–25; Novikoff P. Sur la separabilite des ensembles projectifs du seconde classe // Fund. Math. – Bd 25 (1935). – P. 459–466.

Одинец В. П., Шлензак В. А. Основы выпуклого анализа / пер. с польск.

В. П. Одинца при участии М. Я. Якубсона; под ред. В. Н. Исакова. – М.– Ижевск: РХД, 2011. – 520 с.

Новиков П. С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Труды МИАН СССР. Изд-во АН СССР. – 1955. – Т. 44.

– С. 3–143.

В 1902 г. Уильям Бернсайд (William Burnside: 1852–1927) в работе, опубликованной в журнале «Quart. J. Pure and Appl. Math» (1902. – V. 33. – P. 230– 238), поставил вопрос о периодических группах: всегда ли конечна конечно порожденная группа, каждый элемент которой имеет конечный порядок. При этом Бернсайд выделил случай, когда порядки всех элементов группы ограничены в совокупности (т. е. в группе выполняется тождественное соотношение xn 1 при некотором натуральном n ). В работе [65] было дано отрицательное решение проблемы для всех нечетных периодов n 4381.

Григорий Самуилович Цейтин (р. 1936) по окончании в 1956 г. математико-механического факультета ЛГУ стал работать в НИММ1 при этом же факультете, занимаясь проблемами машинного перевода, теорией программирования и создания языка программирования АЛГОЛ (версия 1968 г.) и т. д. Его публикации: в 1956 г. в ДАН СССР, подробная в 1958 г. в Трудах МИАН СССР (т. 52, с. 172–189) «Ассоциативное исчисление с неразрешимой проблемой эквивалентности» – стали классическими работами в теории алгоритмов.

Г. С. Цейтин был одним из создателей и основных преподавателей Юношеской Математической Школы при математикомеханическом факультете ЛГУ (начало ее работы – 1960 г.).

В 1975 г. Г. С. Цейтин защитил докторскую диссертацию. К началу 90-х гг. XX в. относится сотрудничество Г. С. Цейтина с фирмой IBM, результатом которого стал переезд в США и работа в этой фирме до 2009 г.

Отметим также, что Г. С. Цейтин является одним из виднейших эсперантистов планеты.

Упражнения 1. Докажите вычислимость по Тьюрингу следующих функций:

В лаборатории, которой руководил Г. С. Цейтин, работал и Николай Кириллович Косовский (р. 1945), который установил алгоритмическую неразрешимость универсальной теории кольца двоично рациональных чисел.

2. Показать, что если две функции вычислимы по Маркову, то их композиция вычислима по Маркову.

3. Дан алфавит a, b.

а) Пусть А – подмножество слов, начинающихся с буквы «а».

Дайте прямую нумерацию для А и докажите ее алгоритмическую вычислимость.

б) Пусть В – множество слов, которые читаются одинаково слева направо и справа налево (множество «палиндромов»). Дайте прямую нумерацию для В и докажите ее алгоритмическую вычислимость.

в) Пусть С – множество слов, содержащих не более одной буквы «а». Дайте прямую нумерацию для С и докажите ее алгоритмическую вычислимость.

§ 11. X-я проблема Гильберта Среди проблем алгоритмической разрешимости особое место занимает X-я проблема Гильберта, сформулированная в докладе на II Международном конгрессе математиков в 1900 г. Суть проблемы – существует или нет алгоритм, определяющий за конечное число шагов наличие у данного многочлена нескольких переменных с целыми коэффициентами ЦЕЛЫХ корней.

Первые подвижки в решении этой проблемы появились в начале 50-х гг. XX в. и связаны с именем Мартина Дэвиса (Martin Davis: 1928). Еще в конце 40-х гг. М. Дэвис выдвинул гипотезу:

каждое перечислимое множество является диофантовым.

Под диофантовым множеством понимается некоторое подмножество A k (где k ), для которого существует многочлен P x,..., x, y,..., y с целыми коэффициентами y1,..., yn, где При этом М. Дэвис показал, что любое перечислимое множество М натуральных чисел можно представить в форме:

(Это представление принято называть нормальной формой по Дэвису [68]).

В 1959 г. М. Дэвис и Х. Путнам (Hilary Putham: 1926) доказали ослабленную гипотезу Дэвиса (для экспоненциальных диофантовых уравнений), опираясь на недоказанное до сих пор предположение, что существует сколь угодно длинная арифметическая прогрессия, содержащая только простые числа1.

Ослабленную гипотезу Дэвиса без этого предположения удалось доказать в 1960 г. Джулии Робинсон (Julia Robinson результат опубликован в 1961 г. в совместной статье Д. Робинсон, М. Дэвиса и Ю. В. Матиясевич Davis M., Putham H. Reductions of Hilbert’s tenth problem // The Journal of Symbolic Logic. – V. 23. – № 2 (1958). – Р. 183–187.

Мальцев А. И. О некоторых пограничных вопросах алгебры и математической логики // Труды Международного конгресса математиков (Москва, 1966).

– М.: Мир, 1968. – С. 217–231.

точку, доказав гипотезу М. Дэвиса [70]. Одновременно им дан отрицательный ответ на вопрос в X-й проблеме Гильберта. Отметим, что научным руководителем Ю. В. Матиясевича был С. Ю. Маслов.

В связи с X-й проблемой Гильберта уместно заметить, что если, вместо требования целых корней полинома, потребовать действительных корней, то, как показал в 1942 г. (публикация 1948 г.

[67]) великий польский логик А. Тарский (Alfred Tarski (Tajtelbaum): 1902–1983), за конечное число шагов алгоритмическое решение проблемы наличия таких корней всегда существует.

Что касается алгоритмического решения проблемы в случае требования рациональных корней полинома, то до настоящего времени ответ неизвестен (см. также [71]).

Завершим этот параграф краткими биографическими данными главных действующих лиц: М. Дэвиса, Х. Путнам, Джулии Робинсон, А. И. Мальцева, С. Ю. Маслова, Ю. В. Матиясевича, А. Тарского.

Мартин Дэвис родился в 1928 г. в Нью-Йорке в семье польских евреев, эмигрировавших из Лодзи в США. Учился в Городском колледже в Нью-Йорке. Там одним из его преподавателей оказался Эмиль Пост, что имело для М. Дэвиса решающее значение. Получив в 1948 г. степень бакалавра, М. Дэвис поступает в Принстонский университет, где его научным руководителем становится А. Черч1.

В 1949 г. М. Дэвис получает степень магистра, а год спустя степень Ph. D. Его первым местом работы был университет в Иллинойсе (1950–1952 гг.), затем Принстонский институт Перспективных исследований, где он работал по теме, поддерживаемой Jacson A. Interview with Martin Davis // Notices of the AMS. – V. 55. – № (2007). – P. 560–571.

Агентства Национальной безопасности США. Совместная работа с Хилари Путнам началась в 1956 г. В совместная публикация, она спонсировалась Военно-Воздушными силами США.

философию математики. Время Великой депрессии семья Путнам провела во Франции, возвратясь в США Хилари Путнам классе. В университете в Пенсильвании Путнам получает степень бакалавра (по математике и философии); далее он учится в Гарварде и Калифорнийском университете (Лос-Анджелес), где и получает в 1951 г. ученую степень Ph. D. за диссертацию под названием «Значение понятия вероятность в приложениях к конечным последовательностям».

Позже он преподает в Северозападном университете (Эванстон, штат Иллинойс), в Принстоне и в Мичиганском технологическом институте (MIT). В 1976 г. Х. Путнам был выбран Президентом Американского Философского общества. Следует также отметить бескомпромиссную борьбу Х. Путнам с проявлениями антисемитизма, а также борьбу за социальную справедливость1.

В 1964–1973 гг. Х. Путнам был активнейшим борцом против участия США во вьетнамской войне [72].

Джулия Баумэн Робинсон родилась в 1919 г. в красивейшем городе штата Миссури – Сент-Луисе. Ее мать умерла, когда Джулии было два года. Некоторое время ее воспитывает бабушка, жившая в Фениксе (штат Аризона). После вторичной женитьбы отца семья переезжает в Сан-Диего (штат Калифорния). В 1936 г.

она оканчивает среднюю школу с медалью (Bausch-Lomb medal) и поступает в Колледж Сан-Диего. Благодаря финансовой поддержке своей тети2 Джулия переводится в университет Беркли (University of California ot Barkeley).

Среди преподавателей этого университета она выделяет ассистента Рафаэля М. Робинсона, который помог ей в изучении теории чисел, и в 1941 г. выходит за него замуж. По окончании учебы в университете она поступает в аспирантуру, и под научным руководством великого польского логика Альфреда Тарского защищает в 1948 г. диссертацию на степень Ph. D. под названием «Определяемость и разрешимость проблем в арифметике».

С этого времени Д. Робинсон начинает вплотную заниматься X-й проблемой Гильберта. В 1950 г. ей была предоставлена возможность сообщить о своих результатах на XI Международном КонВозможно, в этом сыграло свою роль то, что его отец – Самуэль Путнам – был коммунистом, а мать Рива – еврейкой.

Отец Джулии разорился в результате Великий Депрессии и покончил собой.

грессе математиков, проходившем в Кембридже (штат Массачусетс, США). В 1959 г. М. Дэвис и Х. Путнам шлют Д. Робинсон свою работу по X-й проблеме Гильберта, а в 1961 г. выходит их (троих) совместная работа, послужившая в 1970 г. фундаментом для окончательного решения Ю. В. Матиясевичем этой проблемы. Кроме X-й проблемы Гильберта, Д. Робинсон для фирмы RAND Corporation занималась задачей игры с нулевой суммой, а для Военно-морского флота США – задачами гидродинамики. В 1982 г. Д. Робинсон была избрана (на 4 года) Президентом Американского Математического общества. (В истории этого общества женщина впервые была избрана на такой пост.) В 1985 г.

Д. Робинсон избирают в Американскую Академию Искусства и Науки [37].

Как уже было сказано выше, в 1966 г. Анатолий Иванович Мальцев выдвинул свою ослабленную гипотезу Дэвиса.

А. И. Мальцев родился в 1909 г. в семье стеклодувов Мишеронского стекольного завода Владимирской губернии1 Костериных2.

Окончив среднюю школу в 1927 г., А. И. Мальцев поступает в МГУ на механико-математический факультет. По окончании МГУ в 1931 г. преподает в Энергетическом институте г. Иваново, а затем там же в Педагогическом институте. В 1934 г. поступает в аспирантуру МГУ, где его руководителем становится А. Н. Колмогоров.

После защиты кандидатской диссертации в 1937 г. Мальцев возвращается в Педагогический институт. В 1939 г. его направляют на учебу в докторантуру в МИАН им. В. А. Стеклова.

В 1941 г. он успешно защищает докторскую диссертацию и стаНыне это Московская губерния.

После 1917 г. завод получил название «Пионер».

новится сотрудником МИАНа, одновременно (до 1960 г.) преподает в Педагогическом институте г. Иваново.

В своих работах он постепенно уходит от чисто алгебраической тематики к теории рекурсивных функций и математической логике. В итоге он становится основным творцом теории классов моделей и алгебраических систем1 [74].

В 1958 г. А. И. Мальцев был избран действительным членом АН СССР, а в 1959 г. он переезжает в Новосибирск, где заведует отделом алгебры Института математики СО АН СССР (подробнее см. [76]).

В 1939 г. в Ленинграде в семье филологов родился Сергей Юрьевич Маслов. В 1956 г. он поступил на механико-математический факультет ЛГУ. В 1961 г. принят в аспирантуру по специальности «Математическая логика». В 1970 г. С. Ю. Маслов защищает докторскую диссертацию, которую, правда, утверждают лишь через 2,5 года, в 1973 г. Впрочем, докторскую диссертацию ученика С. Ю. Маслова, будущего академика Ю. В. Матиясевича, тоже утверждают больше года.

С середины 70-х гг. С. Ю. Маслов начинает преподавать в Ленинградском финансово-экономическом институте им. Н. А. Вознесенского (ЛФЭИ), вначале на кафедре экономической кибернетики, а позже – высшей математики. В ЛФЭИ С. Ю. Маслов С. Ю. Маслов Например, двухосновные алгебраические системы Мальцева – это графы (подробнее см. [75]).

продолжил исследования по ИИ и теории дедуктивных систем.

Особо следует сказать о семинаре «Общая теория систем», которым он руководил с 1967 по 1982 г. Этот семинар, начинавшийся на математико-механическом факультете ЛГУ, а затем переместившийся в квартиру С. Ю. Маслова, стал одним из первых интердисциплинарных семинаров в Ленинграде. На нем обсуждались не только проблемы науки, но и искусства и литературы (включая «самиздат»), не всегда одобряемые тогдашними властями. Эти семинары как глоток «чистого воздуха» в период застоя продолжались вплоть до трагической гибели С. Ю. Маслова1 [77; 78].

Ученик С. Ю. Маслова Юрий Владимирович Матиясевич родился в 1947 г. в Ленинграде. Учился в физико-математической школе № 239, а 10-й класс (1963/64 учебный год) – в знаменитой Колмогоровской школе-интернате при МГУ. Ю. В. Матиясевич был победителем II и III Всероссийской (1962, 1963) и VI Международной олимпиады (1964) [79]. В 1964–1969 гг. он учится на математико-механическом факультете ЛГУ. При этом со второго курса его научным руководителем становится Сергей Юрьевич Маслов. Уже на втором курсе Ю. В. Матиясевич получает результаты по логике, опубликованные в Докладах Академии Наук СССР и доложенные на XV Международном Математическом Конгрессе в Москве (1966).

Один год (1969–1970) он учится в аспирантуре ЛОМИ, а в 1970 г. защищает кандидатскую диссертацию. В том же году Ю. В. Матиясевич завершает решение X-й проблемы Гильберта2.

С 1970 г. он работает в ЛОМИ. В 1972 г. им была защищена докторская диссертация, посвященная проблеме разрешимости.

С. Ю. Маслов трагически погиб в автокатастрофе в 1982 г.

Матиясевич Ю. В. Дифантовость перечислимых множеств // Доклады АН СССР. – Т. 191. – № 2. (1970). – С. 279–282.

В последние годы Ю. В. Матиясевич занимается, кроме задач логики, и задачами дискретной математики, в частности гипотезой четырех красок. В 2008 г. его избирают действительным членом РАН, а в январе 2009 г. – Президентом Санкт-Петербургского математического общества.

Альфред Тарски (Alfred Tarski (Tajtelbaum): 1902–1983) родился в 1901 г. в Варшаве в семье Тайтельбаумов (Tajtelbaum).

(Альфред поменял фамилию в 1923 г.) Формально до 1917 г.

Польша была частью Российской Империи. Поэтому не случайно научным руководителем Альфреда станет родившийся в Серпухове и окончивший гимназию в Иркутске, а университет в Мюнхене Станислав Лещневский (Stanisaw Leniewski: 1886–1939).

Альфред Тарски с 1918 по 1924 г. учится в Варшавском университете, завершив учебу защитой докторской диссертации1.

С. Лещневский был одним из создателей польской школы логиков и философов. Альфред Тарски в период с 1924 по 1931 г. получает глубокие результаты в теории множеств и в той части логики, которую позже назовут семантикой. Итогом этих исследований была работа в журнале Fundamenta Mathematicae [80], которая принесла А. Тарскому широкую известность. Альфред Тарски Напомним, что в Польше докторская диссертация соответствует кандидатской диссертации в России, а следующая диссертация называется хабилитацией.

В 1933 г. на польском, а в 1936 г. – на немецком языках выходит его знаменитая работа «Понятие истинности в формализируемых языках» [81]. В 1937 г. в Вене (Vienna) в издательстве «Julius Springer» выходит книга «Einfrung in die mathematische Logik und in die Methodologie der Mathematik», сразу поставившая А. Тарского в число ведущих логиков мира. Но в самой Польше отношение к Тарскому было иным. Все попытки (их было 5) получить должность профессора оказались безуспешными. Причиной был антисемитизм польских властей на государственном уровне, воцарившийся в Польше с 1936 г. после смерти Юзефа Пилсудского (Jzef Pisudski: 1867–1935). В августе 1939 г.

А. Тарски покинул Польшу и эмигрировал в США. Во время II Мировой войны А. Тарски работал в Гарвардском университете, в Городском Колледже Нью-Йорка1, в Институте Перспективных исследований в Принстоне и, наконец, в Университете Беркли (с 1945 до 1983 г.), где им была создана научная школа по логике и основаниям математики и науки в целом.

Среди учеников Альфреда Тарского можно выделить не только Джулию Робинсон, но и Анджея Мостовского (Andrzej Mostowski: 1913–1975), Чень-Чунг Чанга (Chen-Chung Chang:

1930) и Джерома Кейслера (Jerome Howard Keisler: 1936) – сотворцов теории моделей. Д. Кейслер является одним из авторов нестандартного анализа и др. Только диссертаций на степень Ph. D. под руководством А. Тарского было защищено 24 [82].

В 1961 г. этот Колледж стал частью университета города Нью-Йорка.

§ 12. Элементы теории сложности. NP-проблема О сложности алгоритмов и оценке ее численно обычно говорят вне контекста какой-либо вычислимой модели, хотя это и не всегда удобно.

Напомним, что на практике сопоставляют алгоритмы, решающие одну и ту же (массовую) проблему, по двум критериям:

а) время работы (число шагов алгоритма при различных входных данных);

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

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

Иными словами, нас интересует при сравнении двух алгоритмов их поведение при росте объема входных данных.

Напомним, что если f n и g n – две натуральные функции одной переменной n, то говорят, что g мажорирует f и пишут и говорят, что g – наилучшая оценка для f. Очевидно, что отношение (наилучшей оценки) будет отношением эквивалентности.

Аналогично определяются понятия мажорируемости для случая функций нескольких переменных. Разумеется, замена мажорируемой функции f n на мажорирующую функцию g n должна упрощать вычисления.

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

Аналогично можно говорить и о функциях с переменными – длинами выходных данных и длинами промежуточных данных.

Напомним также, что количество знаков в двоичном представлении натурального числа n равно log 2 n 1 1. При этом длина l двоичного представления натурального числа n мажорируется функцией ln n, и это наилучшая оценка.

Наилучшим образом можно оценить и длину l суммы, произведения и степени натуральных чисел:

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

Например, если алгоритмы A1, A2 и A3 имеют сложности порядка f1 n, f 2 n и f3 n соответственно, то в качестве оценки Напомним, что нижняя целая часть числа x max k : k x в отечественной литературе именуется целой частью числа х,.

По оценке сложности алгоритмы разделяют на 4 крупных класса:

10. Алгоритмы сложности, не превосходящей линейную (эти алгоритмы имеют сложность порядка, не большего O n ).

20. Алгоритмы полиномиальной сложности (чаще всего их сложность оценивается как O n, 1).

30. Алгоритмы экспоненциальной сложности (сложность этих алгоритмов мажорируется 2, но не мажоOn рируется никакой степенью n ).

40. Алгоритмы сложности большей, чем экспоненциальная (на практике эти алгоритмы обычно не применяются).

В зависимости от сложности алгоритмов для решения тех или иных массовых проблем, эти проблемы подразделяют на класса сложности: 100, 200, 300 и 400. При этом справедливо:

100 200 300 400.

100. Проблемы сложности не больше линейной.

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

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

(Например, это проблемы генерации объектов, число которых возрастает экспоненциально (подробнее см.

будет ли P = P. Однако это пока не доказано.

Впервые вопрос о равенстве классов был поставлен Стивеном Куком1 (Stephen Cook: 1939) в 1971 г. и независимо ЛеониСтивен Кук родился в Баффало (Buffalo, New York), получил степень бакалавра в 1961 г. в Мичиганском университете, степень магистра в 1962 г. и Ph.

D. в 1966 г. в Гарварде. Далее он работал в Университете Беркли (до 1970 г.), а затем уехал в Торонто, где стал профессором университета по специальностям «Математика» и «Computer Science».

дом Левиным1 (р. 1948) в 1973 г. Не случайно проблему равенства классов P и P называют одной из шести оставшихся «великих» проблем тысячелетия, после доказательства гипотезы Пуанкаре Г. Я. Перельманом (подробнее см. [83–84]).

Упражнения 1. Постарайтесь дать наиболее точную оценку возрастания следующих функций натурального аргумента:

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

3. Пусть f 6 n – количество неориентированных и не изоморфных графов Бержа с петлями и числом вершин, равным n.

Найдите наиболее точную оценку возрастания этой функции.

4. Оцените число битовых операций, необходимых для перевода числа из десятичной системы в шестнадцатеричную.

Леонид Анатольевич Левин родился в Днепропетровске в 1948 г.; окончил механико-математический факультет МГУ им. М. В. Ломоносова в 1970 г.;

там же в 1977 г. защитил кандидатскую диссертацию. Его научным руководителем был А. Н. Колмогоров. Л. А. Левин эмигрировал в США в 1978 г., а в 1979 г. получил Ph. D. в области прикладной математики в Массачусетском Институте Технологии. (В MIT его научным руководителем был профессор Альберт Р. Мейер (Albert R. Meyer: 1941)). В настоящее время Л. Левин – профессор Бостонского университета.

5. Оцените число битовых операций, необходимых для вычисления n-го числа последовательности Фибоначчи.

Оцените число битовых операций для вычисления:

Глава III. История систем искусственного интеллекта Введение Считается, что термин «искусственный интеллект» (Artificial Intelligence) предложил Джон Маккарти (John МсСarthy: 1927) в 1955–1956 гг., вместе с Мэрвином Мински (Marvin Minsky: 1927), Натаниелем Рочестером (Nathaniel Rochester: 1919–2001) и Клодом Шенноном (Claude Elwood Shаnnon: 1916–2001).

Маккарти уже имел к этому времени степень Ph. D., защищенную в 1951 г. в Принстоне под руководством знаменитейшего тополога Соломона Лефшеца (Solomon Lefschetz: 1884–1972)1. Заметим, что мать Д. Маккарти хорошо говорила по-русски, т. к. была еврейкой, эмигрировавшей из Российской Империи (Виленской губернии) [86].

Уже к середине 50-х гг.

Д. Маккарти интересуется программированием, математической логи- Джон Маккарти С. Лефшец был одним из творцов алгебраической топологии. Он родился в Москве. Получив среднее образование во Франции, в 1905 г. в возрасте 21 года эмигрировал в США. Он хотел стать инженером, но в 1907 г. потерял обе кисти рук в результате электроожога. Считая, что только математик может работать без кистей, он становится математиком, а уже в 1911 г. у него – Ph.

D. по алгебраической геометрии. С 1944 г. С. Лефшец стал заниматься дифференциальными уравнениями, а позже динамическими системами.

кой (рекурсивными функциями и нечеткой логикой1), а также эпистемологическими2 проблемами искусственного интеллекта [87].

Первоначально (по Д. Маккарти) под искусственным интеллектом (ИИ) понималась наука и технологии создания интеллектуальных машин и, в частности, интеллектуальных компьютерных программ.

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

В этом смысле системы ИИ включают в себя экспертные системы и робототехнику. С другой стороны, ИИ сам стал частью и философии, и новой науки когнитологии3. В рамках ИИ удалось за прошедшие 50 лет смоделировать основные чувства человека:

зрение, слух (и речь), обоняние, тактильные чувства.

Работы в области создания систем искусственного интеллекта (СИИ) обычно делят на два направления:

1. Нейрокибернетика – аппаратное моделирование структуры и функций человеческого мозга.

2. Кибернетика «черного» ящика – т. е. безотносительно к структуре «ящика» он должен реагировать на внешние воздействия (раздражители), такие как мозг человека.

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

Эпистемология – учение о познаниях. В узком смысле эпистемология изучает происхождение, структуру, границы и значение познания. Этот термин введен в 1854 г. шотландцем Дж. Ферье (Ferrier John: 1782–1854).

Когнитология (от лат. {cognitio = познание} + от греч. {logos = учение}) – 1) наука о знаниях; 2) система методов и приемов (технологий) получения, обработки, хранения и использования человеческого знания.

«лабиринтного» поиска. В итоге на основе эвристического подхода появилось понятие экспертной системы (ЭС) или системы, основанной на знаниях.

Пока разработка и создание ЭС является основным направлением в изучении СИИ.

Другим направлением в СИИ является создание и анализ существующих игр (шахматных, карточных, командных и т. д.).

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

§ 13. Представление знаний в интеллектуальных системах Напомним, что в математической логике предпочтительной формой записи является префиксная форма записи. Основная теорема префиксной формы записи звучит так:

Последовательность S символов является правильно построенной в форме польской префиксной записи, если и только если:

2) ранг (подпоследовательности слева от S) 0, при этом ранг (оператора) = вес (оператора) – 1, ранг (пустой последовательности) = 0, ранг (n-го символа) = n-1, ранг (переменной) = ранг (константы) – 1, ранг (S1 соединенный с S2) = ранг(S1) + ранг (S2) [89, с. 43].

Пример:

а) выражение p q p, записанное в инфиксной форме, в префиксной форме будет иметь вид:

б) выражение: log y y2 b /sin x будет выглядеть:

Кроме записи, для представления знаний в СИИ особую роль играет понятие формальной системы. Напомним, что формальная система – это совокупность чисто абстрактных объектов, не связанных с внешним миром, в которой представлены правила оперирования множеством символов в чисто синтаксической трактовке без учета смыслового содержания (т. е. семантики).

Говорят, что формальная система определена, если:

10. Задан конечный алфавит (т. е. конечное множество символов).

20. Определена процедура построения формул (или слов) формальной системы.

30. Выделено некоторое множество формул, называемых аксиомами.

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

Формальную систему иногда называют также аксиоматикой (или формальной теорией) или даже просто множеством формул.

Самой известной формальной системой является логика высказываний (или пропозициональная логика).

Напомним для нее п. 10 – 40. (Их назовем 100 – 400.) 100. Алфавит:

пропозициональные буквы p, q, r, s, t,…;

два логических оператора:, («не» и «следует»);

200. Построение формул (или пропозициональных форм):

любая пропозициональная буква суть формула;

если m есть формула, то (m) – также формула;

если m есть формула, то m – также формула;

если m1 и m2 формулы, то m1 m2 – тоже формула.

300. Аксиомы:

(здесь m1, m2, m3 – формулы).

4 00. Одно правило вывода (правило модус ноненс, или правило отделения):

если m1 и ( m1 m2 ) суть теоремы, то m2 есть следствие m1.

Запись:

Кроме вышеуказанной логики высказываний напомним формальную систему Аристотеля1, отражающую законы дедуктивного мышления. В этой системе три закона Аристотеля являются строго доказуемыми. Сформулируем их:

– закон тождества (т. е. (р р));

– закон исключенного третьего, или (р р);

– закон противоречия, или (р р).

Фактически закон противоречия означает, что никакая теорема не может одновременно быть и теоремой, и не-теоремой.

Возвращаясь к логике высказываний, нельзя не напомнить о теореме Поста (1921) [110]:

Аристотель – величайший ученый Древней Греции (384, 322 гг. до н. э.), ученик Платона (427, 347 гг. до н. э.).

Формула F доказуема в исчислении высказываний, если и только если она является тождественно-истинной, т. е. истинной при всех интерпретациях исчисления высказываний.

Из этой теоремы следует для исчисления высказываний:

а) непротиворечивость (т. е. t и t не могут быть одновременно выводами);

б) полнота, т. е. теоремы точно соответствуют тождественно-истинным формулам;

в) разрешимостью (т. е. существованием процедуры решения).

Для исчисления предикатов1 первого порядка имеет место аналог теоремы Поста – Первая теорема Геделя (1930):

Все теоремы являются логически общезначимыми формулами, т. е. являются истинными во всех интерпретациях [33].

Исчисление предикатов первого порядка определяется так:

1. Алфавит:

константы a, b, c, d,…;

индивидуальные переменные;

предикаты A, B, C, D, …;

логические операторы:, ;

квантор всеобщности («каково бы ни было»).

2. Построение формул:

формулы исчисления предикатов образуются аналогично формулам исчисления высказываний;

каждому предикату приписывается вес k; выражение А(х1,…,хк) является формулой тогда и только тогда, когда вес А равен k;

выражение (( х1) А(х1,…,хк)) представляет собой формулу, в которой х1 – связанная переменная, а хi – свободная переменная (i 2).

3. Аксиомы включают три аксиомы исчисления высказываний: (А1), (А2), (А3) + (А4): (( t) B(t) B(u)) («спецификации») (т. е. переменная «t» не содержится свободно в переменной «u») (А5): (( t) ( m1 m2 ) ( m1 (t) m2 ), где m1 и m2 суть формулы, а t не является свободной переменной в m1.

4. Правило словообразования:

( m1 ) и ( m1 m2 ) m2 (модус поненс) m1 ( t) m1 (обобщение), где t – свободная переменная в m1.

К сожалению, первая теорема Геделя (в отличие от теоремы Поста) не приводит к эффективной процедуре решения.

Четвертой формальной системой (и одной из важнейших для Computer Science) оказалась формальная арифметика Джузеппе Пеано (Guiseppe Peano: 1858–1932), представленная им в 1889 г., когда он был представлен к должности профессора математики первого класса в Королевской Военной Академии [90].

Напомним, что в формальной арифметике по сравнению со счислением предикатов дополнительно вводятся:

– одна константа 0 (нуль);

– 4 оператора:

а) оператор «S» – «непосредственно следующий»

(например, S(0) = 1, S(2) = 3) б) операция сложения «+»

в) операция умножения на «*»

г) оператор равенства = оператор S имеет вес, равный 1, а остальные 3 имеют вес 2;

– 9 новых аксиом:

(А,9) ( х) ( у) (х + S(у)) = S(х + у) (А,10) ( х) ( у) х*S(у) = х*у + х (А,11) ( х) ( у) ( S(х) = S(у)) (х = у) (А,12) ( х) ( у) (х = у) ( S(х) = S(у)) (А,14) (А(0) и ( u) (A(u) A(S(u))) ( u)A(u) для всякой формулы A(u) данной формальной системы1.

Аксиома (А,14) носит название аксиомы математической индукции.

Заметим, что аксиомы Пеано воспроизводят фактически аксиомы работы (1861) Германа Грассмана (German Grassmann:

1809–1877) [91].

В 1931 г. в работе [33] К. Геделя появилась теорема, названная Второй теоремой Геделя о неполноте арифметики: «В формальной арифметике существуют формулы m, такие, что ни m, ни m не являются доказуемыми».

Равносильная формулировка этой теоремы звучит так: «Если формальная арифметика непротиворечива, то она неполна».

В 1936 г. Герхардом Генценом (Gerhard Karl Gentzen:1909– 1945) была доказана2 непротиворечивость формальной арифметики [107]. Тем самым в силу результата Геделя формальная арифметика неполна.

Еще две теоремы дополняют этот результат: Тарского (1935) и Черча (1936):

В оригинальной работе Пеано вместо (А,8), (А,11), (А,12) и (А,13) были следующие аксиомы:

1. 1 («1 есть натуральное число»);

2. (х ) (S(х) ) («следующее за натуральным числом будет натуральным числом»);

3. 1 не следует ни за каким натуральным числом;

4. ((S(в)=а) ((S(с)=а)) (в=с)), т. е. всякое натуральное число следует только за одним натуральным числом.

Г. Генцен – немецкий математик и логик, получил степень Ph. D. в 1933 г.

Его научными руководителями были: формально – Герман Вейль (Hermann Weyl: 1885–1955), фактически – Пауль Бернайс (Paul Isaak Bernays: 1888– 1977).

Теорема Тарского [92]:

Существуют формальные системы, для которых всякая интерпретация приводит к выражениям одновременно истинным и недоказуемым.

Более подробно эта теорема утверждает, что в каждой интерпретации (данной системы) существует, по крайней мере, одна формула, всегда интерпретируемая как ИСТИНА, которая, тем не менее, не является теоремой данной формальной системы.

Теорема Черча [93]:

Исчисление предикатов первого порядка неразрешимо.

Иными словами существуют формальные системы, для которых нельзя построить системы процедур, позволяющих отличать теоремы от не-теорем. Эти системы, как говорят, не являются рекурсивно перечислимыми (или кратко – неразрешимыми).

А. Тарски показал [92], что теории групп, колец и тел являются неразрешимыми (но проективная геометрия (в пространстве вещественных чисел) и теория вещественных замкнутых тел – разрешимые), неразрешима и проблема «останова» программы, выполненной на машине Тьюринга.

Напомним, что вторую теорему Геделя, теорему Тарского (1935) и Черча (1936) принято называть теоремами ограничения.

Существенный прогресс в установлении выводимости после работ А. Тарского в 1930–40-е гг. наступил в работе [94] С. Ю. Маслова (см. гл. II, § 11), в которой впервые был предложен метод автоматического поиска доказательства теорем в исчислении предикатов.

Нами не случайно уделено столько времени формальным системам. Дело в том, что системы ИИ характеризуются (в отличие от обычных компьютеров) базами знаний. Именно базы знаний (при наличии баз данных) являются в ИИ основным объектом формирования, обработки и исследования.

Для баз знаний в ИИ существует два типа методов представления знаний (ПЗ) [98]:

1. Формальные модели ПЗ.

2. Неформальные модели ПЗ (семантические, реляционные).

Напомним, что знания характеризуются:

1) внутренней интерпретируемостью;

2) структурируемостью;

3) связностью, т. е. наличием иерархической сети, в вершинах которой находятся информационные единицы;

4) семантической метрикой (характеризует ситуационную близость информационных единиц или, иначе, отношение «релевантности»);

5) активностью (появление в базе знаний фактов или описание событий, или установление связей может стать источником активности системы).

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

а) Логические модели. Эти модели основаны на формальной системе, как правило, задаваемой четверкой M T, P, A, B, где:

– Т – множество базовых элементов, например слов из ограниченного словаря. При этом существует процедура П(Т) проверки принадлежности или непринадлежности произвольного элемента к Т.

Подробнее о семантике см. гл. IV, с. 164.

– Р – множество семантических правил, с помощью которых строятся из элементов Т синтаксически правильные совокупности. При этом должна существовать процедура П(Р), с помощью которой за конечное число шагов можно получить ответ на вопрос: будет ли совокупность Х синтаксически правильной?

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

– Наконец, множество В, называемое правилами вывода, применяется к элементам из А, и в результате получают новые синтаксически правильные совокупности, к которым вновь можно применять правило из В, и которые образуют множество выводимых в данной формальной системе совокупностей.

Напомним, что если существует процедура П(В), с помощью которой можно определить, является ли любая синтаксически правильная совокупность выводимой, то соответствующая формальная система называется разрешимой.

На практике достаточно хранить в базе знаний лишь А, а остальные знания получать из них по правилам вывода [97].

б) Сетевые модели.

В основе моделей этого типа лежит семантическая сеть, т. е.

H I, C1,..., Cn, Г, где I – множество информационных единиц, К={C1, C2,…,Cn} – множество типов связей между информационными единицами, а Г – отображение: I К.

Сети, как правило, используются в ИИ трех типов: классифицирующие сети, функциональные сети (включая и нейронные сети) и сценарии.

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

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

[75, § 28]).

В сценариях, как известно, используются казуальные отношения, а также отношения типа «средство-результат» и др.

Преимущество сетей: 1) модель позволяет работать с не полностью определенными знаниями; 2) модель (зачастую более адекватно (по сравнению с логической моделью) отображает реальность.

Недостаток сетевой модели кроется в сложности реального явления или процесса, для которого строится сетевая модель: чем больше сеть, тем труднее поиск [98].

в) Продукционные модели.

Эти модели – синтез элементов логической и сетевой моделей. Из логических моделей заимствована идея правил вывода (называемых в этой модели продукциями), а из сетевых моделей – описание знаний в виде семантической сети. В продукционных моделях процедурная информация явно выделена и по описанию отличается от декларативной информации. Особенностью этих моделей является вывод на знаниях (вместо логического вывода в логических моделях) [103].

В общем случае продукционную модель можно представить в виде четверки: S, L; A B ; Q, где S – описание класса ситуаций;

L – условие, при котором продукция активируется;

Q – постусловие проекционного правила.

Коротко – проекционная модель позволяет представить знание в виде предложения: Если (А = условие), то (В = действие) [89].

Преимущества модели: 1) простота основной единицы – продукции; 2) легкость модификации базы знаний (БЗ); 3) строгость механизма логического вывода.

Недостатки: 1) малая степень структуризации БЗ; 2) неуниверсальность; 3) при большом числе единиц возможны противоречия в сети.

Среди языков, реализующих продукционные модели, пока наиболее известен ПРОЛОГ [95] – язык и система логического программирования, основанные на языке предикатов дизъюнктов1 Альфреда Хорна (Alfred Horn: 1918–2001).

г) Фреймовые модели.

В отличие от сетевых и продукционных моделей фреймовые модели имеют точного автора и время появления. Автор, называемый «отцом» ИИ, – Мэрвин Мински (Marvin Minsky: 1927).

Время – рубеж 60–70-х гг. XX в. Напомним, под фреймом понимается абстрактный образ или ситуация. Формализованная модель для отображения образа или ситуации также носит название фрейма.

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

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

Эти дизъюнкты и их применение изучались в работе А. Хорна, 1951 г. [96].

Minsky M. Semantic Information Processing. – Cambridge, MA: MIT Press, 1969.

Слот – элемент фрейма. Обычно один фрейм может содержать множество слотов.

Нью-Йорке в еврейской семье выходцев из Российской Империи – врача Генри Минского (Henry Minsky) и Мэрвин Мински Маккарти в 1959 г. основывает при MIT Лабораторию ИИ. Уже в 1951 г. М. Мински сконструировал первую обучающую машину со случайно связанной нейросетью – SNARC. Его диссертация в Принстоне «Neural Nets and the Brain Model Problem» 1954 г. содержала необходимую теорию об обучении системы, содержащей нейросеть. В 1957 г. Фрэнк Розенблатт (Frank Rosenblatt: 1928– 1971) предложил математическую и компьютерную модель восприятия информации мозгом, названную персептроном1.

В 1969 г. вместе с Сеймуром Пейпертом (Seymour Papert:

1928) М. Мински выпускает работу «Персептрон», в которой теория элементарного перцептрона переизложена на языке предикатов. Кроме строгости, это позволило выявить принципиальные ограничения персептронов (при, например, параллельных вычислениях) [99].

В 1972 г. (также в соавторстве с С. Пейпертом) вышла книга «Искусственный интеллект», получившая всемирную известПерцептрон (или персептрон) (англ. perceptron) от лат. perception – восприятие.

ность [100]. Широкую популярность имели и работы М. Минского, посвященные робототехнике1. Не случайно за эту работу в 1990 г. М. Мински был удостоен премии Японии. М. Мински известен как автор первого конфокального сканирующего микроскопа (1956).

Выше был упомянут Фрэнк Розенблатт. Он также как и М. Мински родился в Нью-Йорке (в 1928 г.). Закончил в 1946 г.

ту же среднюю школу в Бронксе, что и М. Мински (с научным профилем). А вот затем пути М. Мински и Ф. Розенблатта были разными. Ф. Розенблатт поступил в Корнельский университет на специальность «Психология». После окончания университета (1950–1955) он работает в Национальной корпорации здравоохранения и исследовательском центре социальных наук. С 1956 г.

Ф. Розенблатт – сотрудник Корнелльской аэронавтической Лаборатории, где возглавляет с 1959 г. программу по проблеме распознавания образов. Под его руководством в 1958–1960 гг. строится вычислительная система, имитирующая глаз человека «Марк 1».

Это был первый нейрокомпьютер, способный обучаться, основанный на идее персептрона, предложенной Ф. Розенблаттом в 1957 г. Широкую известность принес Ф. Розенблатту курс лекций для будущих бакалавров психологии «Теория механизмов мозга» [101].

Ф. Розенблатт трагически погиб в 1971 г. во время прогулки на яхте.

Minsky M. Robotics. – Doubleday, 1986.

Ph. D. в Университете города Витватерсранд (Witwatersrand) по математике. Изза активной борьбы С. Пейперта против Кембриджском университете. Там же поСеймур Пейперт лучил степень Ph. D. (1959).

Женеву, где в течение пяти лет преподает в Женевском университете, сотрудничает с Жаном Пиаже (Jean Piaget: 1896–1980) – одним из крупнейших психологов первой половины XX века.

В 1963 г. С. Пейперт начинает работать исследователем в MIT. В 1967 г. он получает звание профессора прикладной математики и становится Директором Лаборатории искусственного интеллекта при MIT2. Позже С. Пейперт уделяет основное свое внимание развитию и обучению детей. (В 1988 г. специально для С. Пейперта при MIT была для этих целей создана кафедра.) Еще в Женеве С. Пейперт создал язык LOGO, который, по замыслу С. Пейперта и Ж. Пиаже, должен был открыть путь детям к овладению компьютерными технологиями3. Вместе с М. Мински Сеймур Пейперт принадлежит к первым творцам систем ИИ [102].

В годы учебы в Кембридже С. Пейперт – активный участник «Социалистического обозрения».

На этой должности он пробыл до 1981 г.

В России нашлось немало его последователей. Не случайно С. Пейперт неоднократно приезжал в 2000-е гг. в Москву и Санкт-Петербург. Среди его последователей в России отметим С. И. Горлицкую (р. 1947) (см., например, [111]). Жена С. Пейперта – искусствовед из России.

Упражнения 1. Запишите в префиксной форме выражения:

2. Приведите пример сетевой модели, граф которой имеет вид:

3. Приведите пример продукционной модели.

4. Приведите пример фреймовой модели.

5. Дайте описание языка LOGO.

§ 14. Экспертные системы В настоящее время экспертные системы образуют ядро интеллектуальных искусственных систем.

Напомним, что типичная экспертная система имеет вид (архитектуру), представленный на рис. 14.1 [104, с. 16].

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

Так, уже в сентябре 1943 г. немецкая подводная лодка стала использовать самонаводящиеся акустические торпеды «Zaunknig»1. Т. 5. Головные части известных немецких ракет «Фау 2»

были снабжены компьютером К. Цузе «Z-3», позволявшим уточнять координаты цели по скорости ракеты и времени полета.

= Троглодит.

В 1943 г. Норбертом Винером (Norbert Wiener: 1894–1964) в короткой заметке, написанной вместе с Артуром Розенблатом (Arturo Rosenblueth: 1900–1970) и Джулиан Бигелов (Julian Bigelow: 1913–2003) «Поведение, цель и телеология»1 [105], впервые в науке обозначена проблема перенесения на неживые системы черт поведения «homo sapience», в частности умению обучаться и принимать адекватные решения.

В 1948 г. Н. Винер издает свою знаменитейшую книгу «Кибернетика или...» [106], в которой законы кибернетики объявляются универсальными для живой и неживой природы. При этом нейронные сети должны были стать одним из классов использования «Computational Intelligence» и при этом использования, так называемой «зашумленной», числовой информации при применении различных стохастических алгоритмов.