The reason
Table of contents
Share
Metrics
The reason
Annotation
PII
S207751800000010-0-3
DOI
10.18254/S0000010-0-3
Publication type
Article
Статус публикации
Published
Authors
Timur Gataullin 
Abstract
This article represents the short review of Ignasi Beld's book «Reason, machines and mathematics. Artificial intelligence and its tasks» / translation from Spanish. - Moscow: De Agostini, 2014. Follows from the name of the book that the book is devoted to the «Reason» concept, but what is it - remained unknown after acquaintance to this book. This work is popular introduction to a subject of artificial intelligence. In Russia there are many experts (we call only V. L. Makarov and D. V. Pospelov), who could write similar introduction not worse, and, perhaps, more better. This book contains a short list and the description of the main objectives and methods of artificial intelligence. However in these descriptions some important points are missed. This descriptions are stated in the books published in Soviet period and will be hardly republished. In this article we briefly will stop on some of them.
Keywords
Reason, machines, an artificial intelligence, complexity of algorithms according to A. N. Kolmogorov, the Turing machine, cryptography protocols
Received
25.10.2016
Date of publication
29.12.2016
Number of characters
10079
Number of purchasers
8
Views
1632
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

1

«Пильман: - Да. И все было бы хорошо, если бы мы знали, что такое разум. Нунан: - А разве мы не знаем?» Из беседы Нобелевского лауреата В.Пильмана с рядовым чиновником Р. Нунаном из Международного института в «Пикнике на обочине» Стругацких.

2

Из названия книги «Разум, машины и математика» [1] следует, что она посвящена в том числе «разуму», но что это такое - осталось неизвестным и эпиграф свидетельствует, что не только автору данной заметки. Приведем оглавление книги:

3

Глава 1. Что такое искусственный интеллект 


4

Глава 2. Поиск


5

Глава 3. Машинное обучение


6

Глава 4. Автоматическое планирование и принятие решений.

7

Глава 5. Анализ данных 


8

Глава 6. Искусственная жизнь


9

Книга представляет собой популярное введение в тему искусственного интеллекта. У нас в России есть немало специалистов (например, В. Л. Макаров и Д. А. Поспелов), которые могли бы написать подобное введение не хуже, а, пожалуй, даже лучше. Приведенное выше содержание книги содержит вкратце перечень и описание важнейших методов и задач искусственного интеллекта. Однако в этих описаниях некоторые важные моменты упущены. Они содержатся в книгах, изданных еще в советское время, и вряд ли эти книги будут переизданы. В этой заметке мы кратко остановимся на некоторых из них. Так, в первой главе много внимания уделено тесту Тьюринга, который должна пройти машина, чтобы беседующий с ней живой человек согласился считать эту машину разумной. Сам Тьюринг придумал этот свой тест еще до второй мировой войны, но затем было найдено много контрдоводов против этого теста. Основа всех этих доводов - уход активной стороны от содержательной основы беседы в чисто формальную переделку вопросов и ответов беседы. Пример подобной переделки приведен в одной из книг Д. А. Поспелова [2]. В рецензируемой книге описана «китайская комната» - мыслимый эксперимент, предложенный Д. Серлем в 1980 г. в известной статье «Minds, Brains, and Programs», который, в частности, является критикой теста Тьюринга. Тематика проблем, связанная с тестом Тьюринга до сих пор привлекает к себе внимание исследователей. В этой связи отметим лишь диссертацию А. Ю. Алексеева на соискание ученой степени доктора философских наук «Философия искусственного интеллекта: концептуальный статус комплексного теста Тьюринга» [3]. И еще одно замечание, относящееся ко всем материалам книги по искусственному интеллекту. Оно связано со сложностью рассматриваемых алгоритмов. Это понятие и основные утверждения о сложности были впервые введены и рассмотрены нашим великим соотечественником А. Н. Колмогоровым [4]. Эти вопросы достаточно сложны. Один из ведущих математиков мира С. Смейл, который по просьбе В. Арнольда, занимавшего в то время пост Президента международного математического союза, составил список из 18 нерешенных математических проблем, включил данный вопрос в число важнейших нерешенных проблем XXI века [5]. Например, необходимо ответить на вопрос, есть ли у данного многочлена с целыми коэффициентами целый корень? Оказывается (и это доказал наш российский математик Ю. В. Матиясевич в 1969 г., когда он нашел оригинальное решение, использующее свойства чисел Фиббоначчи, 10-й проблемы Гильберта [6]), что не существует алгоритма (компьютерной программы), который бы по целочисленному вектору коэффициентов многочлена давал однозначный ответ «да» или «нет». Таким образом, все попытки запрограммировать решение данной задачи с помощью компьютеров потерпят крах. Или, например, пусть даны три целых числа а,b,с. Имеет ли квадратное уравнение целый корень? Нетрудно запрограммировать эту задачу на компьютере. Записывая указанные числа через запятую, можем считать, что на вход компьютера подается число длиной п символов. Ясно, что чем больше длина этого слова, тем дольше будет работать компьютер над решением конкретного уравнения. Но как долго? В теории сложности вычислений говорят, что алгоритм является полиномиальным, если существует константа d, такая, что время работы алгоритма не более чем .

10

Для рассматриваемой задачи подобный полиномиальный алгоритм существует. Но стоит чуть изменить задачу, и вопрос о существовании решающего полиномиального алгоритма становится нерешенной научной проблемой. Именно так обстоит дело с задачей, сформулированной следующим образом: «Дана система линейных неравенств с целыми коэффициентами. Есть ли у этой системы целочисленное решение?» Интересно, что ответ положителен для очень похожей задачи: «Дана система линейных неравенств с рациональными коэффициентами. Является ли данная система совместной?» Рассмотрим задачу разложения натурального числа на простые множители. Это типичная задача дискретного программирования. Имеется алгоритм ее решения. Он очень прост: чтобы узнать, является ли число х простым, необходимо последовательно разделить х на каждое натуральное число, не большее .

11

Если х записать в виде двоичного числа из n символов, то потребуется примерно делений. Этот алгоритм явно не полиномиальный. Так, для разложения на простые множители числа х, записываемого с 200 двоичными знаками, потребуется около делений. Это приблизительно соответствует десятичному числу, содержащему 30 знаков. Для современных суперкомпьютеров данная процедура займет примерно 25 млн. лет непрерывной работы (числа примерно такого же размера используются в криптографии для шифрования важных сообщений - и чтобы разгадать такой шифр, это число нужно разложить на простые множители). А для разложения на простые множители 1000- значного числа современным компьютерам, если они будут работать по указанному алгоритму, не хватит всего времени существования Вселенной около лет.

12

До сих пор неизвестно, существует ли полиномиальный алгоритм для разложения натуральных чисел на простые множители. Однако в последние 10-20 лет в этом направлении забрезжила надежда на решение многих задач за приемлемое время, и связана она с так называемыми квантовыми компьютерами. Теория этих компьютеров достаточно сложна. В своей работе они используют принципы квантовой механики и обещают очень многое. Так, доказано, что квантовые компьютеры (если удастся их построить) могут разложить 1000-значное число на простые множители всего за несколько часов. Однако специалисты предупреждают, что, хотя принципиальных трудностей для создания квантовых компьютеров вроде бы и не существует, технических трудностей здесь не меньше, чем в проблеме построения реактора термоядерного синтеза, над которой ведущие физики и конструкторы всего мира бьются уже свыше 50 лет. Оптимизм вселяет то, что спецслужбы мира готовы потратить на соответствующие исследования миллиарды долларов - ведь в случае успеха они получат возможность расшифровать многие перехваченные сообщения, которые десятилетиями лежат нерасшифрованными. Огромное количество используемых в математике алгоритмов полиномиальны и гипотеза существования не полиномиальных алгоритмов называется P NP гипотезой. В наступившем тысячелетии она является одной из важнейших. Во всем мире к понятию сложности алгоритмов по Колмогорову проявляется огромный внимание и очень жаль, что ей не уделено соответствующего внимания в книге. И еще одно важное замечание. В книге совершенно не уделено внимания криптографическим протоколам. А ведь это - средство взаимодействия человека и компьютера. В работе М. Н. Аршинова и Л. Е. Садовского [7] утверждалось, что «... приемов тайнописи - великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое». Бурное развитие криптографических протоколов, а также новые направления в математике, получили в 1976 году с выходом в свет работы американских математиков У. Диффи и М. Э. Хеллмана «Новые направления в криптографии» [8].

13

Новым и центральным объектом в криптографии стало понятие «односторонней функции». Односторонней называется функция F(x) из X в Y, обладающая двумя свойствами: а) существует полиномиальный алгоритм вычисления значений функции F(x); б) не существует полиномиального алгоритма инвертирования функции F. Заметим, что пункт б) может быть немного уточнен. Похожим на понятие односторонней функции является понятие функции с секретом. Так называется функция двух переменных F(K,x), некоторое значение параметра K которой и называется секретом. Остальные значения параметра секретом не являются. Хорошим примером функции с секретом является банковская карточка, в которой секретом является пин-код. Начиная с 1976 года тема, криптографических протоколов интенсивно развивается. Перечислим лишь некоторые криптографические протоколы: - протокол аутентификации - звонящий в банк с помощью этого протокола должен убедить банковский компьютер или банковского служащего, что он именно тот, за кого он себя выдает; - протокол электронной подписи - что это такое - уже достаточно хорошо известно; - протокол бросания жребия;
- протокол проверки корректности доказательства с нулевым разглашением;
- протокол византийских генералов; - и т.д. Предполагается, что криптографические протоколы в ближайшее время станут одним из важнейших предметов в вузах и вызывает только сожаление, что в достаточно хорошей и интересной рецензируемой книге о них ничего не сказано.

References



Additional sources and materials

1. Ignasi Beld. Razum, mashiny i matematika. Iskusstvennyj intellekt i ego zadachi» / per. s ispanskogo. - M.: De Agostini. 2014. 2. Pospelov D. A. Modelirovanie rassuzhdenij. Opyt analiza myslitel'nykh aktov. – M.: Radio i svyaz', 1989, - 184 s. 3. Alekseev A. Yu. «Filosofiya iskusstvennogo intellekta: kontseptual'nyj status kompleksnogo testa T'yuringa». Dissertatsiya na soiskanie uchenoj stepeni doktora filosofskikh nauk. – M.: 2015. 4. Kolmogorov A. N. Tri podkhoda k opredeleniyu ponyatiya «Kolichestvo informatsii» // Problemy peredachi informatsii. - 1965. - T.1. No1. - S. 3-11. 5. Steve Smale. Mathematical problems for the next century. Mathematics: frontiers and perspectives // American Mathematics Society: 2000. - p. 271-294. 6. Matiyasevich Yu. V. Diofantovost' perechislimykh mnozhestv // Doklady Akademii nauk SSSR. – M.: - 1970. - T.191, No2. - S.279-282. 7. Arshinov M. N., Sadovskij L. E. Kody i matematika (Rasskazy o kodirovanii) // Bibliotechka «Kvant», vyp.30/ - M.: Nauka,1983. – 144 s. 8. W. Diffie, M. E. Hellman. New Directions in Criptography. IEEE transactions on information theory, VOL/IT-22 No6, November 1976.