ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ
МОСКВА 1968
ЛИТЕРАТУРЫ
6П2Л54
А79
УДК 519.95
Brains, Machines
and Mathematics
Michael A. Arbib
McGraw
Hill Book Company
New York San Francisco Toronto
London
Майкл А, Арбиб
Мозг,
машина и математика
М., 1968 г., 224 стр.
с илл.
Редактор Д. С. Фурманов
Техн. редактор И. Ш. Аксельрод
Корректор О. А. Сигал
Сдано
в
набор 25/1 1968
г.
Подписано к печати
Бумага 84х1087з2« Физ. печ. л.
Уч.-изд. л. 10,53. Тира** 50000
7.
8/VII 1968
Условн. печ. л.
экз.
Цена книги
г.
11,76.
55 коп.
Заказ № 1093.
Издательство «Наука»
Главная редакция
физико-математической литературы.
Москва, В-71, Ленинский проспект, 15.
Ленинградская типография № 2 имени Евгения Соколовой
Главполиграфпрома Комитета по печати
при Совете
Министров СССР. Измайловский пр., 29.
3-3-14
235-67
Оглавление
От редактора русского перевода
Предисловие автора
Предисловие
Глава
к
......
русскому
изданию
5
7
9
1
Нервные сети, конечные автоматы
и
машины
Тьюринга
15
§ 1.1. Краткие сведения из нейрофизиологии
Питтса
§ 1.2. Модель Маккадлока
§ 1.3. Конечные автоматы
§ 1.4, Конечные автоматы
19
22
модульные сети
и
и
цифровые
вычислительные
25
машины
§ 1.5. Машины Тьюринга
§ 1.6. Рекурсивные множества
30
и
тезис
Тьюринга
§ 1.7. Регулярные и представимые события
§ 1.8. Еще некоторые сведения из теории
...
конечных
48
56
автоматов
§ 1.9. Самовоспроизводящиеся
36
42
автоматы
Глава 2
Структура
и
случайность
§ 2.1. Зрительная
67
78
85
система
лягушки
§ 2.2. Персептрон
§ 2.3. Структура против случайности
Глава 3
Исправление ошибок при передаче
§ 3.1. Надежный
мозг
§ 3.2. Многократные
из
и
вычислениях
нейронов
фон Неймана
ненадежных
схемы
§ 3.3. Шенноновская теория
88
94
98
119
связи
§ 3.4. Теория связи и автоматы
§ 3.5. Теория надежных автоматов
...
Винограда
Кована 124
ОГЛАВЛЕНИЕ
4
Глава 4
Кибернетика
§
§
§
§
§
4.1.
4.2.
4.3.
4.4.
4.5.
135
142
150
153
159
Обратная связь и колебания
Резонансные частоты в нервных сетях
Протезирование и гомеостазис
.
.
.
Образы и понятия
Некоторые другие направления
Глава 5
Теорема
Гёделя
о
неполноте
§ 5.1. Основания
§
§
§
§
§
5.2.
5.3.
5.4.
5.5.
5.6.
математики
Некоторые факты из теории рекурсивных функций
Рекурсивные логики
Арифметические логики
Доказательство теоремы Гёделя о неполноте
Мозг и машина
.
.
183
185
188
Заключение
Приложение
165
168
170
175
1. Основные
Приложение 2. Основные
понятия
понятия
Приложение 3. Математика
Библиография
Литература, добавленная
в
теории
множеств
алгебры
биологии.
.
.
192
194
Эдвард Мур 196
217
редактором перевода
220
От редактора русского перевода
книга
Предлагаемая вниманию советского читателя
М. Арбиба «Мозг, машина и математика»
относится к разряду промежуточному между
научно-популярными и научными книгами. Своеобразие ее в
том, что она допускает несколько уровней изучения.
Читатель, не интересующийся глубоко
проблематикой кибернетики, постарается разобраться только в
определениях и теоремах, содержащихся в этой книге
(не вникая в их доказательства), и понять суть
рассматриваемых моделей. Для такой категории
читателей книга может служить прекрасным
научно-популярным руководством по кибернетике.
Значительно больше информации получит читатель,
пытающийся самостоятельно воспроизвести полные
доказательства
в
тех
местах,
где
даются
их
только
При таком подходе рассматривать эту книгу
научно-популярную могут только достаточно
наметки.
как
подготовленные в математическом отношении читатели
научные сотрудники, инженеры, учителя, аспиранты и
студенты вузов.
И, наконец, книга может служить' хорошим
пособием для читателей, желающих глубоко изучить со*
держащийся в ней материал. Получив при первом
беглом чтении книги общую картину развития
соответствующих разделов
кибернетики, такие читатели
найдут многочисленные ссылки на работы других
автбров, и захотят изучить их. Приводимая в книге
краткая характеристика содержания этих работ,
авторские комментарии и замечания помогут им в этом.
г-
Следует отметить, что книга написана очень
неровно. Некоторые разделы изложены достаточно
значительно менее подробно,
подробно, ряд других
того
хотелось
бы*.
Возникает впечатление,
что
чем
автор
ОТ РЕДАКТОРА РУССКОГО ПЕРЕВОДА
6
сознательно
даже
темы
в
включил
в
не
излагаются
побольше
материала,
изложения.
Некоторые
книгу
ущерб подробности
совсем
во
многих
случаях
решение (например, почти
все, что касается самовоспроизводящихся автоматов,
многие места из главы «Кибернетика» и др.)- В этих
даются
только
наметки
читатель
случаях
четко,
на
отсылается
литературе, которая приводится
к
как в
специальной
сносках, так
и
в
рекомендованной литературы.
Специально для русского издания автор прислал
два дополнительных параграфа к первой главе (§§ 1.8
и 1.9). Поскольку в одном из них используются
некоторые алгебраические понятия, оказалось
целесообразным разъяснить их (приложение 2 написано
редактором русского перевода).
Оригинал был рассчитан на американского
читателя, и поэтому в нем почти нет ссылок на работы
списке
авторов. Во всех тех случаях, когда имеются
переводы цитированных работ на русский язык или
равноценные книги советских авторов, сделаны
специальные примечания. Кроме того, в конце книги
советских
список
приводится
литературы,
составленный
из
работ
переведенных на русский
язык. Этот список был частично составлен автором
для русского издания его книги и значительно
дополнен переводчиком и редактором перевода. Список ни
советских
в
коем
авторов
случае
работ,
и
претендует на полноту и составлен
выше трех категорий читателей),
научных работ, хотя в нем и
не
(с учетом указанных
в
основном
встречаются
В
Э.
из
работы научно-популярного характера.
виде приложения
«Математика в
Мура
посвященная
читается
проблемам
легче,
чем
к
книге
биологии»,
приводится
самовоспроизведения. Эта
книга,
и
статья
в основном
может
статья
рассматриваться
своеобразное введение в книгу.
При редактировании мне большую
как
помощь
оказали многие товарищи, в первую очередь А.
Колотов,
В. Лозовский и П. Твердохлеб. Приношу ий свою
глубокую благодарность.
Новосибирск
М. Кратко
Ноябрь 1967 г.
Предисловие автора
к
русскому изданию
Проведя богатый событиями октябрь 1964 г. в
Союзе, я с большим удовольствием
пользуюсь случаем предоставить настоящий перевод моей
Советском
книги для усиления контактов с советскими учеными.
Эта
время, когда я был в Масинституте и находился
под сильным влиянием Уоррена Маккаллока и Норберта Винера, у которых я тогда учился. Освещение
тематики является достаточно широким, чтобы дать
возможность войти в область кибернетики.
Во время работы над книгой я не считал себя
книга написана в то
технологическом
сачусетском
во многих вопросах и поэтому мог лишь
бегло упомянуть об искусственном интеллекте и
эвристическом программировании (§ 4.5). Так как на
русский язык переводится сборник «Вычислительные
компетентным
машины
и
баума
Дж. Фельдмана,
этот
и
мышление»
сборник
под
превосходных
а не беглое изложение
издании моей книги.
К первой
новых
главе
редакцией Е. А. Фейген-
то
я
этих
по
данной тематике,
вопросов
русского издания
параграфа. Один
из
них
читателю
рекомендую
работ
в
я
русском
добавил
посвящен
два
последним
в теории конечных автоматов, а
самовоспроизводящимся автоматам.
Сжатые сроки работы над книгой не. дали
возможности включить в эту книгу исследования
достижениям
другой
русских ученых и
дополнительной
читателя
литературы.
в
поэтому
я
ограничиваюсь списком
литературы,
курс
мне
которая
отечественной
введет
русского
кибернетической
ПРЕДИСЛОВИЕ АВТОРА К РУССКОМУ ИЗДАНИЮ
8
преподаватели предпочитают излагать
математическую науку и поэтому
ограничиваются изучением некоторых полностью
формализованных разделов математики, которые можно
Некоторые
кибернетику
как
рассматривать
в этом случае
как
основы
кибернетики. Выбор
тем
такими, без сомнения,
интересными исследованиями, как теория автоматов/
самоорганизующиеся системы и теория алгоритмов.
обусловлен
Эти педагоги понимают, что
и
мозга как
изучение
искусственный
машины
п.
и т.
интеллект
представляют
огромный интерес, но считают эти разделы еще
недостаточно формализованными для математически
слящих
Я
людей, изучающих кибернетику.
нужным особенно подчеркнуть,
всей важности таких направлений, как теория
автоматов и теория алгоритмов, они не могут быть
считаю
введением
сомнений
установления
мы*-
в
связи
что
полным
общую кибернетику. Много тревог
кибернетике вызывает проблема
в
между
математическими
биологическими
Существенно, что
вычислительными
моделями
и
и
машинами
сложными
при
или
реальными
физиологическими системами.
кибернетические модели имеют
и
биологическую «основу» и эта «основа» не может быть
развита посредством изучения систем, которые уже
полностью формализованы.
машина
Я
представляю
новое издание
и
математика»
с
надеждой,
книги
что
настоящему «прочувствуют» реальные
Станфордский университет,
Станфорд, Калифорния, США
Март 1966 г.
«Мозг,
мои
читатели
по
системы.
Майкл
Арбиб
Посвящается
Фреду Поллоку,
мастеру образного,
остроумного и мудрого
преподавания
математики
Предисловие
Эта
общую
книга является введением в
тему «мозг,
машины и математика», где математика используется
для
аналогий
установления
Она
и
связь.
в
некоторой
теорема Гёделя,
с
тем,
с
и желает знать
что
литературе. Здесь
знаком
кибернетика,
как
направлениями,
сравнению
управление,
предназначена для
степени
он
может
читатель
работой
между
такими аспектами машин, как
Эта
книга имеет
на
это,
который
в
ней освещены
желает
найти
найдет
будет
требуется
как
и
какими
они
полу*
так что для
Несмотря
вечеров.
вопросы, и% читатель,
многие
Для подробного
в
некоторой
университетского
(или
зрелость»). Однако
понятна
степени
биологии
и
обучения
всей
книги
один
подготовка
по
вычислительной
эквивалентная «математическая
большая
читателю,
доказательства
чтения
математическая
средняя
математике
ми
несколько
дальше,
популярной
в
не только то,
подготовлен для серьезного чтения специальной,
литературы.
курс
идти
модными
теория информации,
о них больше по
небольшой объем,
потребуется
и
читателя, который
такими
являются некоторые результаты, но
чаются.
первого чтения
мозга
вычисление
часть
книги
который опускает
предварительно
должна
быть
математические
незнаком
или вычислительных машин.
с
основа-»
10
ПРЕДИСЛОВИЕ
Прежде
должен
чем
сказать
содержании книги,
слов
нейрофизиологии
в
дел
о
говорить
несколько
и
об
истинном
природе
я
положении
разрабатываемых
моделей. Использование микроэлектродов,
электронных микроскопов и радиоактивных индикаторов
в
течение
позволило
последних десятилетий
нами
значительно
расширить наши познания в нейрофизиологии.
такой многотомный труд, как «Справочник по
Даже
нейрофизиологии» j(.«Handbook of Neurophysiology»)
не может полностью охватить все факты. Многие
нейрофизиологические теории, какими бы общими они не
были, с применением все более сложных приборов
обнаруживают более
структуры и более сложные
Это
клеточные
механизмы.
тонкие
химико-электрические
что
означает,
описываемые
в
упрощенном
книге,
взгляде
систему. Читатель
таких
систем
хоть
на
какое-то
неопределенность,
отдельных
мозг
и
центральную нервную
удивиться,
Между
память,
надежность
компонентах,
из
состоит одна
к
мы
основных
ним.
что
изучение
или
иметь
Исходя
тем
имеется
много
вычисление,
при
которые,
отнести к «чистым механизмам».
внимания
весьма
представлять интерес
значение.
как
модели,
на
основываются
может
может
свойств таких,
в
математические
наши
этой
йричин
обучение,
ошибок
наличии
видимо,
Однако
нашего
трудно
в этом и
пристального
нз математических
моделей,
существование электромеханических
которые обладают указанными
доказываем
механизмов,
свойствами.
Другими
словами,
мы
стараемся
«отделить
душу от машин». Мы еще не можем создавать такие
механизмы, которые имеются в мозгу, но у нас есть
по
мере модели возможных на этот счет
которые сами по себе представляют
крайней
механизмов,
большой
шаг
вперед.
ПРЕДИСЛОВИЕ
11
Имеется и другая причина такого изучения,
с течением
которая
становится
времени
все более
значительной.
Прогресс
связан
применением математико-дедуктивэкспериментального методов.- За последние
математика все более широко используется
с
ного
300
в
а
в
физической науке
широким
и
лет
физике:
математика
косвенно.
на то, что до сих
указать
служит
прикладная
математика
чистая
физике
мозга и его
и
непосредственно,
Здесь
проникает
медленно
вынуждены
в
исследования
аналогов.
электромеханических
развитие биологической
наблюдаться
Возможно,
математики
до тех пор, пока не разовьются
новые захватывающие разделы
Здесь,
мы
математика в основном
пор
что медленное
будет
в основном
чистой
математики.
однако, мы применяем математику для
получения общих выводов, вытекающих из имеющихся
предпосылок. Мы можем проверить адекватность
модели
описывая
мозга,
и
терминах
используя
для доказательства
любых
к
нашим
образом
и
экспериментами,
более
В дальнейшем
в
том,
хорошим
математических
аппарат
В
глубокого
такие
можем
их
и
он
наших
позволяет
моделей
вернуться
работы
понимания
теории помогут
нам
и сложные машины.
нам
и, таким
образом,
рассчитывать на то,
системы
обычно
намного
общие
является
при изучении моделей
переносном смысле.
прямом,
Биологические
физических
состоит
устанавливать
помощником
так и в
свете
этими
таким
математико-дедуктивного метода
что
свойства
мы
изменить
построить более «способные»
Польза
точных
математический
обнаруженных между
предпосылкам,
добиться
мозга.
в
математических теорем.
противоречий,
теоремами
ее
наш
как
в
сложнее
систем, так что мы не можем
что даже через
несколько лет появится
ПРЕДИСЛОВИЕ
12
-вполне
удовлетворительная биологическая
математика. Однако поиск такой математики является вполне
реальным
и
результаты,
будут
Я
тем
не
читатель
которые
для него интересными.
небольшую
только очень
но
внимания.
заслуживает
не
и
менее
верю,
с
что
это
Я
в
найдет
Конечно,
надеюсь,
этой
что
книге,
они составляют
часть того, что
является
применением
уже получено,
хорошим началом.
математики удастся
все наши физиологические и
проблемы. Однако считаю, что математико-дедук-
разрешить
психологические
тивный метод должен занимать важное место наряду
с экспериментами и клиническим изучением
нейрофизиологов и психологов; он должен помочь нам понять
мозг так же, как он уже помог инженерам-электрикам
в
хотя
которые
вычислительных
электронных
построении
и
намного
проще
машин,
биологических
организмов, но тем не менее имеют очень много аналогий
с мозгом.
Теперь
мы
Сначала
можем
дать
краткий обзор
этой
книги.
беглый
приведем
обзор
нейрофизиологии и, исходя из него, опишем нашу первую
грубую модель мозга в виде сети, компонентами
Питтса. Мы
которой являются нейроны Маккаллока
убедимся в том, что все, что может делать цифровая
мы
очень
вычислительная машина, может делать и такая сеть.
выясним
взаимосвязь этих
автоматами и машинами
сложной организации
сетей
Тьюринга.
В
Мы
с конечными
качестве
примера
краткий обзор работ,
посвященных изучению зрительной системы лягушки,
и разберем персептрон
(машину, которая «учится»).
Затем приведем краткие нейрологические сведения об
ошибках в нейронах. Из этих сведений будет видна
потребность в выяснении того, каким образом надо
строить
сети,
мозга
приведем
которые
надежно
функционируют,
не-
ПРЕДИСЛОВИЕ
работу
смотря на неправильную
компонентов.
После
Неймана
беглого
мы
13
отдельных
одной
рассмотрения
изучим теорию
работы фон
Шеннона. Затем
связи
мы
рассмотрим решение проблемы построения надежных
Виноградом и Кованом.
изучению кибернетики Нор-
устройств, предложенное
После
этого
мы
берта Винера
изучим управление и связь в
Мы рассмотрим основное понятие
и
животных и машинах.
обратной
связи, что позволит нам лучше
функционировании
нервной
сети
поспешного
в
мы
схему резонансных частот
предостережения
реального
Питтса. После
отождествления
от
слишком
мозга
с
нервной
обсуждения
го-
вернемся
образам
протезирования
распознаванию общих понятий: каким способом мы
меостазиса
и
для
Грином
Маккаллока
сетью
разобраться
нервных сетей. Затем
рассмотрим предложенную
в
к
вернемся
постигаем
главу
и
звуковые
и
дадим исторический обзор
мысли,
формы. Последнюю
зрительные
теореме Гёделя
мы посвящаем
математической
к
мы
которые
привели
докажем теорему,
обсудим
ее
философские последствия
для
наконец,
вернемся
к
Мы
драматические
оснований
спору
о неполноте.
направлений
к работе Гёделя,
тех
математики
о соотношении
и,
между машиной
и мозгом.
Эта
книга является
в
прочитанных
июне
обработкой
августе
1962
Нового Южного Уэльса, Сидней,
жаю
меня
лекций,
Университете
Австралия. Я выра*
г.
в
благодарность Джону Блэтту, пригласившему
Дерека Бруда за приглашение
прочесть лекции,
прочесть эти
превосходные
лекции
по
радио
я
лаборатории электроники
при
и
машинописные копии
Последние два года
отделении
цикла
Массачусетском
провел
и
Джойс Кин
за
прочитанных лекций.
в
исследовательской
математическом
технологическом
институте
14
ПРЕДИСЛОВИЕ
в качестве ассистента
(работа финансировалась
Министерством обороны США
институтом
здравоохранения). Я
и
Национальным
благодарить
должен
так
людей,
могу здесь этого сделать. Однако
особенно благодарен Уоррену Маккаллоку за его
постоянную помощь, Джорджу В Цопфу, который
много
что не
я
первый настоял
мер сделал
на
опубликовании лекций.
Билл Киль-
критические замечания после
прочтения оригинальных лекций. Годами я вынашивал
надежду в этом месте сказать: «Только один он несет
ответственность
было бы
искренней
и
полезные
за
неудачным
благодарности
традиции, заявляю,
оставшиеся
ошибки». Однако
выражением
ему,
и
что
за
я,
это
моей самой
следуя установившейся
ошибки несу
все
ответственность только я.
Наконец,
на
работы
безно
я
должен
которых
я
благодарить
ссылался,
и
всех тех
их
позволивших использовать эти
авторов,
издателей,
лю«
материалы.
Майкл А.
Арбиб
1
Глава
Нервные сети, конечные автоматы
и машины Тьюринга
§1.1. Краткие
Я
сведения из
нейрофизиологии
беглого обзора
бы послужить основанием для
нашей первой математической модели. Нервную систему
человека можно представить себе как
трехступенчатую систему, показанную на рис/ 1.1 *). Основной
гипотезой при создании модели будет предположение,
хочу
нейрофизиологии,
начать с очень
который
мог
\Рецепторь\^
раздражитель
Реакция
Нервная
система
\на внешний
мир
Рис. 1.1. Нервная
система человека,
рассматриваемая
трехступенчатая система.
как
что относящееся к нашему рассмотрению
функционирование нервной системы полностью определяется
прохождением электрических импульсов по клеткам,
которые мы называем нейронами,
В действительности мозг человека содержит
больше глиальных**) клеток, чем нейронов. До недавнего
времени в нейрофизиологии считалось общепринятым,
что назначение глиальных клеток состоит лишь в том,
чтобы
обслуживать,
носится
к
последние
15
теме
лет
питать
нейроны. Тогда
это не от*
рассмотрения. Однако за
высказывается все больше доводов
нашего
в
*) Назначение стрелок, направленных влево, станет ясным
обратной связи в § 4.1.
ткань, сопровождающая нейроны и их отростки.
**) Глин
из рассмотрения
(Прим. перев.)
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
16
[ГЛ. I
пользу того, что глиальные клетки в действительности
выполняют и другие функции, такие, например, как
память, которые уже представляют для Had интерес.
Тем не менее на протяжении этой книги мы rie будем
рассматривать подобные функции глиальных клеток.
Мы также не будем рассматривать такие проявления
взаимодействия нейронов, как постоянно меняющиеся
потенциалы и обмен гормонами. Для нашего
возможных
рассмотрения
будет
нервной деятельности
импульсной активности
механизмов
вполне достаточно
В дальнейшем, бесспорно, потребуется уделять
больше внимания, чем сейчас, остальным
нейронов.
гораздо
нейрофизиологическим,
механизмам,
а
возможно,
и
глии.
В свете
принятой
нами
основной
гипотезы
мы
нервную систему как обширную
сеть нейронов, имеющую сложную структуру и
исключительно сложные внутренние соединения. Эта сеть
воспринимает информацию от большого числа
рецепторов: палочек и колбочек глаз, тактильных
рецепторов кожи, температурных рецепторов и т. д., которые
нреобразуют возбуждения, поступающие из внешней
будем
рассматривать
внутри тела человека, во
электрических импульсов, посредством
которых информация передается в сеть. Эти импульсы
взаимодействуют с чрезвычайно сложными
«картинами» импульсов, которые циркулировали до этого
среды
или возникающие
множество
в
нейронах (установлено,
человеческого
мозга
что
в
нервной
содержится порядка 1010
сети
нейронов!),
в
результате чего на выходе сети появляются импульсы,
управляющие эффекторами, например мускулами или
железами. В этом и выражается
реакция нашего
организма на раздражение. Таким
образом, нервную
систему человека можно условно разделить на три
основные подсистемы: рецепторы, нервная сеть и
эффекторы.
Здесь мы не собираемся создавать модели
рецепторов или эффекторов; нас интересует модель нервной
сети.
Для
модель
весьма
этого
необходимо предварительно
создать
нейрона. Нейроны нашей нервной системы
разнообразны по форме, но мы ограничимся
КРАТКИЕ СВЕДЕНИЯ ИЗ НЕЙРОФИЗИОЛОГИИ
§ 1.1]
нейронов,
рассмотрением
на рис. 1.2.
Нейрон,
содержащееся
в
как
соме
и
или
все
имеющих
клетки,
теле
вид,
имеет
17
показанный
ядро,
Дендриты *) можно
чрезвычайно разветвленного
клетки.
представлять себе в виде
куста, каждое волокно которого тоньше аксона, а сам
аксон представляет собой длинный и тонкий цилиндр,
Рис. 1.2. Схематическое изображение нейрона.
передающий импульсы от сомы к другим клеткам.
Аксон переходит в густое древовидное разветвление,
ветви которого заканчиваются маленькими
пластинками (бляшками),
которые почти касаются дендритов
нейрона. Такой участок близкого контакта называется
синапсом**). Достигающие синапса импульсы
вызывают
переменный электрический сигнал в дендритах***), примыкающих к данному синапсу. Передача
сигналов осуществляется иногда электрическими
импульсами, иногда путем химической диффузии.
Нейрон выдает импульс (поступающий на аксон) лишь
*) Дендрит проводит нервный импульс с периферии к телу
(Прим. перев.)
**) Синапсы
образования, в ^которых происходит контакт
клетки.
нервных клеток друг с другом. Ш синапсу возбуждение
передается только в одном направлении (как правило, лишь с
окончаний аксона одного нейрона на дендриты другого). (Прим.
перев.)
***) Возможен также синапсический переход на другой
аксон. Это «афферентное взаимодействие» рассматривается в § 3 1.
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
18
[ГЛ. I
в том случае, когда на концевые
бляшки, находящиеся
дендритов, поступает достаточное число
импульсов в очень малый промежуток времени, назьь
ваемый периодом латентного накопления. В
у
его
эти импульсы могут либо способствовать,
либо препятствовать возбуждению нейрона и
соответственно называются возбуждающими или тормозящие
ми. Условие выдачи импульса нейроном заключается
в
чтобы возбуждение превосходило
том,
торможение на некоторую критическую величину, называемую
Если каждому возбуждающему
порогом нейрона.
синапсу приписать подходящий положительный вес,
а каждому тормозящему синапсу
подходящий
действительности
отрицательный вес,
то
можно
сказать,
что
нейрон возбуждается тогда и только тогда,
когда сумма весов синапсов, на которые поступают
импульсы
в
период
латентного
накопления,
превышает порог
Предположение
суммировании
о
опять-таки
Таком
простом
является
очень
нейрона. (1.1.1)
линейном
сильным
Далее, порог представляет собой параметр,
меняющийся во времени; однако это изменение редко
упрощением.
моделировании формального
рассматривается при
нейрона и не учитывается в моделях, которые будут
рассматриваться ниже. Читателю, готовому впасть в
отчаяние при виде все возрастающего разрыва с
действительностью, можно рекомендовать для поднятия
духа перечитать предисловие.
Между периодом латентного накопления и
прохождением соответствующего импульса по аксону и
концевым бляшкам существует небольшое время задерж*
ки, так что поступление импульсов на дендриты
нейрона повлечет появление импульса на его аксоне лишь
через некоторое время.
После того как по аксону прошел импульс,
наступает период рефрактерности, в течение которого аксон
не способен передавать импульсы. Следовательно, за
период времени, равный одному периоду
рефрактерности, по аксону может быть передан не более чем
один
импульс.
Выбрав
в качестве единицы
измерения
МОДЕЛЬ МАККАЛЛОКА
§1.2]
времени период
описать
поведение
интервала
времени,
ПИТТСА
-
19
рефрактерности нейрона, можно
нейрона, указав для каждого
когда нейрон возбужден, а когда
возбужден.
Таким образом, мы ввели упрощающее
предположение
(еще более удаляющее нас от
действительности), что наш нейрон может возбуждаться
в моменты
времени /=1, 2, 3, 4,
...
при
не
только
наличии
условий. Наконец, введем еще одно
будем использовать единую
дискретную шкалу времени для всех нейронов сети,
т. е. будем считать, что любое возбуждение нашей
сети полностью определяется картиной возбуждения
отдельных нейронов в дискретные моменты времени
подходящих
упрощающее предположение:
В связи с этим мы полагаем, что выдача
/=1, 2, 3,
импульса на аксон в данный момент времени
полностью определяется возбуждением синапсических
входов этого нейрона в предыдущий момент времени.
...
§ 1.2. Модель Маккаллока
Питтса
Исходя из весьма упрощенных
рассмотрений предыдущего параграфа, введем
модель нейрона (или модуля), которая
впервые была предложена Маккаллоком и Питтсрм.
Определение 1.2.1. Модулем (формальным
нейроном) называется элемент с m входами хи
нейрофизиологических
следующую
(т>1) и одним выходом d. Он
характеризуется m+l числом: порогом 0 и весами coi, ..., comКаждому входу лгг- (1 6.
(синапс)
на то, что 1-й вход
а
®i*i
положительный вес
что
Заметим,
когда
отрицательный
о>гг>0'указывает
возбуждающим,
является
что i-й вход
входом.
этой
крайне упрощенной моделью
нервной сети.
Определение 1.2.2. Модульной сетью
(абстрактной нервной сетью) называется множество модулей,
Пользуясь
нейрона, определим теперь модель
соединенных между собой так, что выход каждого
модуля ветвится на подходящее число линий, каждая из
которых присоединяется к некоторому входу какоголибо модуля. Выход каждого модуля может быть
соединен с любым числом входов, но каждый вход не
может быть соединен более чем с одним выходом. Все
модули сети
работают
одной
в
и
той
же
шкале
времени.
4
Входными
Jo, hf
к выходам
называются
которые
В
линиями
/m_i модулей
...,
модулей*).
те
линии
сети
называются
роу
Выходными
Ри
.,
входные и четыре выходные линии.
идти
линиями,
/m-i
не
в
совсем
модулей.
линии не
соединен
в
сети
Свободные
точно.
действительности
присоединяются
входов
образом,
сети
модулей,
1.3, имеются три
Отметим, что входные
могут ветвиться, а выходные
различных модулей.
Это
...,
а
входы
обязаны
от
*)
/t,
линиями
рт-\ выходов
не соединены со входами
сети, показанной на рис.
линии
те
сети, которые не подсоединены
в
к
имеется
не
5,
входы
являются
нейронов /о,
входными
линиям сети. Каждый из этих
одной входной линией. Таким
входным
точности
где свободных входов
не
с
более
а
m
линий (см. рис. 1.8,
линий). (Прим. ред.)
входных
входных
ПИТТСА
МОДЕЛЬ МАККАЛЛОКА
§1.2]
Читателю, который представляет себе
,
21
модель как
реальную схему с проводами и транзисторами, может
показаться несколько странным употребление нами
слова «модель». Поэтому позвольте обратить
внимание
на
то,
говорит,
чески
что
только
используется
в
в
этой книге
слово
«модель»
Инженер
факта-»
который будет работать так
математическом
смысле.
что он имеет модель системы, если он
построил аппарат,
Рис.
1.3.
Простая модульная
сеть.
же, как и первоначальная система. Математик же гоьорит, что он построил модель системы, если он свы«
разил» некоторые свойства этой системы в точных
определений и аксиом тая,
терминах математических
что он может дедуктивно
свойства этой «формальной»
модели,
которые, как он
свойства оригинальной
вывести
(т.
е.
новые
объяснят известные
ожидает,
системы
такие
математической)
и
предскажут
новые,
неизвестные
свойства.
Понятие
ранее
«модульная
сеть» определено в точных математических терминах
(в следующих параграфах будут
о модульных
смысле
мы
Прежде
доказаны
теоремы
сетях),
поэтому в этом математическом
и рассматриваем ее как модель мозга.
чем приступить к изучению этой модели,
укажем на то, что она получена при следующих весьсущественных ограничениях: а) предполагалось,
что все нейроны работают синхронно; б)
предполагалось, что порог и вес каждого нейрона не меняются
с течением времени; в) мы не учитывали химических
ма
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
22
(например, алкоголя)
и
нов на изменение поведения мозга;
г)
воздействий
всеми
с
{ГЛ. Т
влияния
мы
гормо*
пренебрегли
взаимодействиями между нейронами (например,
помощью
электрического поля, возникающего
кроме синапсических; д)
импульсов),
результате
в
нами
игнорировались глиальные клетки.
Этот список
сюда следует,
ограничений можно продолжить. От*
предложенная модель является
что
только
для
отправным пунктом
Оалека от окончательной.
изучения
Несмотря
на
и,
конечно,
принятые
нашу модель,
это,
ограничения не обесценили полностью
ибо модульные сети могут хранить информацию и
Эти возможности модульных
вычисления.
производить
сетей будут продемонстрированы в § 1.4 при рассмо*
трении цифровых вычислительных машин как модуль*
ных сетей. Но сначала в § 1.3 мы введем понятие «ко*
нечный автомат» и выясним его взаимосвязь с мо*
сетью. Кроме того, в § 1.7 мы рассмотрим
одну простейшую модель восприятия, которая
задается в точных математических терминах входных
последовательностей конечного автомата.
дульной
§ 1.3. Конечные
автоматы и
модульные
сети
Понятие конечного автомата мы введем так, чтобы
было очевидно, что любая модульная сеть является
конечным
ключаться
Тогда
автоматом.
в
установлении
основная
цель
факта,
того
что
будет
выход» любого конечного автомата
можно воспроизвести на подходящим образом
«вход
построенной
намного
для
легче,
всегда
Так
как построение конечного
определенных целей, вообще говоря,
чем построение соответствующей мо*
модульной
автомата
за*
поведение
сети.
сети, то этот результат позволяет судить
том, что могут делать модульные сети (см. § 1.4).
дульной
Пусть модульная
сеть
/V
состоит
имеет m входных и г выходных
Будем
известно,
говорить,
какие
что
g
модулей,
линий.
вход сети
Л/, если
возбуждены, а какие
значения «возбужден» и «не
задан
входные линии
возбуждены. Так как
возбужден» m входным линиям
не
из
о
можно
приписать 2Ш
§
КОНЕЧНЫЕ АВТОМАТЫ И МОДУЛЬНЫЕ СЕТИ
1.3]
23
различными способами, то в сети N имеется
дов. Аналогично в ней имеется *2Г выходов.
Будем
момент
t,
говорить,
если
N
что задано состояние сети
какие
известно,
возбуждены,
состояний.
Обозначим через Q
в
модули
этот
Таким
возбуждены.
какие не
а
2т
N
вхо*
в
момент
образом,
имеет 2#
X
множество
и
входов
множество
через У
состояний,
через
множество
N. Возбуждение любого модуля сети N в
/+1 определяется тем, какие входы этого модуля
выходов сети
момент
возбуждены в момент t и, следовательно, определяется
состоянием и входом всей сети N в момент t. Но это
означает, что вход и состояние сети в момент t
однозначно
определяют выход
и
сети
состояние
t+1. Следовательно, конечный
в
момент
теперь можно
определить как простое обобщение модульной сети.
В дальнейшем конечный автомат будем
автомат
как «черный ящик» с конечным числом входов,
конечным числом «внутренних состояний» (это могут
рассматривать
быть либо состояния
зубцов
модульной сети, либо позиции
п.) и конечным числом
часового механизма и т.
Как
выходов.
в
состояние
и
выше,
t
момент
мы предполагаем,
определяют выход
что
и
вход
и
состояние
момент *+1.
Более точно эти требования можно
сформулировать следующим образом.
Определение 1.3.1. Конечным автоматом
в
называется пятерка
А
=
(Х, Y, Q, К 6),
(множество входов),
(множество выходов), Q
конечное множество
(множество внутренних
состояний), К: QXX-+Q
функция перехода*), d:QXX-+
~+Y
функция выхода. Предполагается, что А
работает в дискретной шкале времени так, что если в
X
где
У
конечное
конечное
момент
t- он
вход а,
Я(q, а),
находился
то
a
в
момент
6(q, а) будет
*) Объяснение
найдет в
множество
множество
Приложении
в
состоянии
t+l
q
и
перейдет
воспринимал
в
состояние
его выходом.
этих и ряда
1.
он
следующих понятий читатель
[ГЛ. Г
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
24
Легко видеть, что любая модульная сеть является
автоматом. Более неожиданным является
конечным
тот
факт,
заменить
что
любой конечный
подходящей модульной
Так
можно
как
привлечения никаких
большого значения для
требует
доказательство этого
факта
глубоких идей
и не имеет
не
автомат
сетью.
последующего изложения, то читатель, который
интересуется им, сразу может переходить к § 1.4.
Действительно, пусть конечный
т
возможных
входов
выходов уоу у и
N
.
.
.
,
автомат
А
имеет
#w_i и г возможных
Уг-х- Сопоставим этому автомату
т входными линиями Л0, Аь
что N, таким образом, имеет 2м
...,
сеть
модульную
Xiy
Х0,
не
с
...,Ат_! (заметим,
входов) и Г ВЫХОДНЫМИ
ЛИНИЯМИ /?о, ри
Рг-1. Вход
Xj автомата А сопоставим такому входу Xj сети Nt в
котором возбуждена только Aj-я входная линия.
...,
Аналогично определим выход yj сети N. Искомая сеть N
состоит из тп+г модулей*): тп модулей
сопоставляются возможным
парам «вход
состояние»
выходам А. Модуль,
Л, а остальные г модулей
и /-му входу
состоянию
соответствующий А-му
автомата Л, обозначим (А, у), а модуль, который
соответствует А-му выходу, обозначим (А). Выходная линия
pk нашей сети N подсоединена к модулю (А).
Модули соединим таким образом, чтобы модуль
(А, /) возбуждался в момент t+l тогда и только
автомата
тогда, когда автомат А в момент / имеет вход Xj и
в А-м состоянии; модуль (А) возбуждается
находится
в момент
/+1 тогда
в момент
/ дает выход ук.
Пусть {Аь А2,
множество
переводят
(А,
/)
...,
и только тогда,
когда
автомат
An(ft)}={(/, /) \X(iy /)=А},
таких
пар
автомат
А
вход»,
«состояние
в
состояние
А.
Тогда
т.
е.
это
которые
модуль
возбужден в момент /+1 тогда
тогда, когда **)
V Ал (*)(*)Ь
M0AIM0V
должен быть
только
А
и
...
*)Предполагается, что автомат А имеет п внутренних
(Прим. ред.)
**) А обозначает логическое «и», а V логическое «или».
состояний.
Заметим,
что
момент /» и т, д.
запись
ki(t)
надо
читать
«&А возбуждено
в
ЦИФРОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ
$ I.4J
25
т. е. тогда и только тогда, когда автомат А в момент t
находится в k-м состоянии и имеет 1-й вход.
,
Пусть
[kv k2,
km
Тогда существуют модульная сеть N
входов {хо,
£m-i}« выходов
ее
...,
состояний
{q0,
...,
qn-\)
действием
входа xj,
...,
Xjs
в
(возможно
любой
выход»
входов
с
автомат
можно
Xj
,
единичной
с
...,
xj
заменить
в
...»
...,
выдает
и
Л,
q^ под
то сеть
Уи$>
...,
«вход
модульной
сетью
с тем же поведением.
§ 1.4. Конечные автоматы
и цифровые вычислительные
Исходя
конечный
из того
автомат
машины
(показано
можно
в
§ 1.3), что любой
модульной сетью,
заменить
нетрудно убедиться в том, что модульные
способны хранить информацию и производить
вычисления. Для этого достаточно показать, что любая
теперь
1964 г., является, конечно, менее «интеллектуальным»
объектом**), нежели мозг, получивший лучшее
образование
1964
Здесь
г.
мы
же
что наша модель мозга, как
относится к
категории
хотим
показать,
она ни
была,
только
бы
груба
вычислительных машин.
цифровая вычислительная машина обычно
устройств: устройства ввода и
вывода, устройства памяти, устройства управления и
арифметического устройства. Устройство ввода и
Любая
состоит из четырех
вывода служит для чтения команд и исходных данных
с входной ленты и их пересылки в устройство памяти
и,
наоборот,
для вывода из
вычислений
результатов
памяти
состоит
из
на
устройства
выходную ленту.
конечного
числа
памяти
Устройство
«ячеек»,
каждая
из
свой адрес и вмещает одно «слово»,
где «слово» может быть как числом
(исходные
данные, промежуточный или окончательный результат),
имеет
которых
так
и
по
командой. Устройство управления
работы
такт
выбирает
машины
одной команде
и
выполняет
каждый
в
устройства
из
ее.
Если
эта
памяти
команда
операцией ввода или вывода или операцией
обращения к устройству памяти, то устройство
является
управления
в
приводит
вывода,
является
действие либо устройство
ввода
и
либо
устройство памяти; если команда
арифметической операцией, то устройство
управления
устройство;
действие арифметическое
приводит в
условным переходом, то оно осущест-
если
*) Имеется два основных типа вычислительных машин
и цифровые. Здесь обсуждаются только цифровые
аналоговые
вычислительные машины.
**) Однако уже
позволяют
производить
сторон
из них
имеются
вычисления
«интеллектуального»
приводится
в
§ 4.5.
такие
с
программы,
целью
поведения;
которые
демонстрации
краткое
различных
описание
двух
ЦИФРОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ
§ 1.4]
вляет
о
необходимую проверку и принимает
следующей команды.
27
решение
выполнении
Для определенности рассмотрим вычислительную
машину, команды которой состоят из кода
выполняемой операции
и
ОП
1-го
адрес
По первому
трех адресов
адрес 2-го числа
адрес следующей команды.
числа
и
памяти:
второму адресам
устройство
управления отыскивает данные, которые нужны для выпол*
нения ОП
а последний адрес указывает,
(операции),
где найти следующую команду. Например, команда
должна
сложить
памяти)
выполнению
быть
числа,
с
истолкована
находящиеся
образом:
(устройства
перейти к
следующим
в
ячейках
адресами 3275
команды,
4006
3119
3275
Сл.
и 3119, и
находящейся в ячейке
Вход
с
адресом 4006.
Устройство
*
_
памяти
Рис. 1.4. Автомат «устройство памяти».
Теперь
памяти».
опишем
Состояние
конечный
устройства
автомат
памяти
«устройство
(рис. 1.4), когда
оно содержит слова хи х2, ..., хп в своих п «ячейках»,
(хи *2, .-., хп). Его входы имеют вид
(т, 6, 0) и (т, 0, d). Если входом является (т, 6, 0),
обозначим
в m-ю ячейку устройства
хт-и хт, хт+и
хп)
(хи
заменяется состоянием (хи
хт-и Ьу хт+и
хп),
а выход отсутствует. Устройство памяти имеет
четыре
то
слово
b
памяти, т. е.
поступает
состояние
...,
...,
...,
выходные линии, две
из
...,
которых а\
и
а2 связаны
с
с входарифметическим устройством, одна вх/вых
и
с устройством
выходным устройством
одну упр
управления. Если входом
является
(т, 0, d),
то слово,
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
28
[ГЛ. I
находящееся в ячейке с адресом т, отсылается по
выходной линии d (где d есть al, a2, вх/вых или упр)
в
соответствующее устройство,
..,
Хт>
...,
на выход
конечным
*п)
остается
d. Ясно,
что
т.
е.
устройство
(хь
состояние
неизменным,
а хт
памяти
...
поступает
является
автоматом.
Арифметическое устройство (рис. 1.5) имеет три
входные линии: одну (ОП) из устройства управления
al
а2
_u_
Арифмети- Вустройстбо
чеспое
памяти
\цстройспг6о
on
Рис. 1.5. Автомат
«арифметическое
устройство».
а2)
и две
(al
двух
регистров,
(Ви B2)t
содержимое
и
где
устройства
из
а
Bt
второго
его
памяти.
состоянием
Оно
содержимое первого,
Входами
регистра.
состоит из
является
а
пара
^
арифметического
тройки вида (0/7, al, a2). Если
входом является тройка (0, a 1, 0), то a 1 записывается
в первый регистр: состояние (Ви В2) переходит в
состояние
(al, В2), а на выход ничего не поступает.
Аналогично вход (0, 0, а2) состояние (Ви В2)
переводит в состояние (Ви а2). В случае входа (0/7, 0, 0)
над (Ви В2) производится ОП, вычисляется результат
С, некоторый промежуточный результат D, и
арифметическое устройство переходит в состояние
(С, D).
устройства
являются
В случае входа (Пам, al, 0) арифметическое
результат вычислений в ячейку
устройство отсылает
al,
т. е. состояние
выход
(С, D)
памяти
остается неизменным, а
(al, С, 0) поступает в память. Ясно, что
устройство является конечным автоматом
арифметическое
оно
по-разному реагирует
на
каждую пару «вход
состояние», число которых конечно.
Входами
являются
устройства
команды
управления
1.6)
(рис.
программы, находящейся
в
устрой-
ЦИФРОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ
§ 1.4]
Вход ОПаЬс переводит
стве памяти.
29
в
его
состояние
(0/7, а, Ь, с). Если ОП является кодом некоторой
функции, то на выход устройства управления один за
другим выдаются четыре значения: (а, 0, al) и (6, О,
й2) поступают в устройство памяти для вызова исход*
ных данных; (0/7, 0, 0) поступает в арифметическое
устройство для выполнения этой операции и, наконец,
_Устройст8о
^
Входы
\
памяти
ство
Аришмети-
^Луправле
Г ния
vec/foe
устройство
Рис. 1.6. Автомат «устройство
управления».
(с, О, упр)
очередной
в
поступает
команды,
устройство
памяти для вызова
выполнять
должно
которую
устройство
управления.
Если ОП является операцией
Пам%
а, 0)
то
возникает два
поступает
в
выхода:
обращения
сначала
к памяти
(Пам,
выход
арифметическое устройство,
а затем
(с, О, упр) в устройство памяти.
является операцией условного перехода
УП (так что УП аЪс означает следующее: надо
выход
Если ОП
проверить
ячейке с
некоторое свойство слова, находящегося в
адресом а; если данное слово обладает этим
свойством,
переходить к
с
адресом Ь,
переходить
к
устройство управления
то
выполнению
в
команды,
противном случае
выполнению
с адресом
с),
то
команды,
должно
находящейся
ячейке
находящейся
в
ячейке
устройство
число шагов должно
управления за конечное
выполнить соответствующую
проверку и в устройство памяти выдать либо
либо (с,0,упр). Так или иначе устройство
является
в
оно должно
конечным
(6,0, упр),
управления
автоматом.
Этого достаточно для построения
вычислительной машины. Правда, здесь не
нашей
рассмотрено
конечный
автомат
как
вывода
устройство ввода
(& также вид соответствующих входов для устройства
-
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
30
управления). Предлагаем
это
читателю
[ГЛ. I
в
качестве
самостоятельного
упражнения.
Читатель, знакомый с устройством
вычислительных
машин, знает, что они представляют собой схемы,
магнитных
элементов:
из
состоящие
десятков тысяч
сердечников,
читателю
транзисторов,
триггеров.
Это
помогает
убедиться, что вычислительная машина
модульной сетью, хотя эти модули и не
в строгом смысле нейронами Маккаллока
является
являются
Питтса. Для новичка, однако, приведенное выше
рассмотрение должно дать некоторую полезную инфор*
мацию сверх того, что вычислительная машина
представляет собой набор радиодеталей. Отметим, что
различные вычислительные машины имеют
неодинаковую
внутреннюю структуру, так что мы лишь обсуждаем
общие идеи, а не конкретные схемы существующих
машин.
i
Закончим
этот параграф двумя ссылками.
объему является доступный труд John von
Neumann «The Computer and the brain»*).
Подробное описание вычислительных машин и
принципов их работы имеется в «Computers and Data
Processing» ed. Grabbe, Ramo and Wooldrige «Hand-»
book of automation, computation and control», v. 2,
Небольшим
по
J. Wiley & Sons, Inc., N. Y., 1958 1961.
§ 1.5. Машины Тьюринга
Из приведенных
любая
цифровая
конечным
вляющей
и
выше
рассуждений
следует,
что
вычислительная машина является
автоматом
или
модульной
сетью,
осущест*
определённые
выходами,
операции над своими входами
причем так, что вход в данный момент
быть не использован, возможно использование
более ранних входов и т. д. Покажем теперь, что
любое вычисление, которое можно выполнить на
может
цифровой
вычислительной
машине,
(используя
конечную
*) Yale University Press, New Haven, Conn., 1958. [Русский
перевод: Джон фон Нейман, Вычислительная машина и
мозг, «Кибернетический сборник», вып. 1, ИЛ, I960.]
31
МАШИНЫ ТЬЮРИНГА
§1.5]
программу), может быть также выполнено на машине
Тьюринга, где
Определение 1.5.1. Машиной Тьюринга Z
называется
конечный
потенциально
бесконечной
автомат
Л, снабженный
лентой, разбитой
по
длине
устройством
на
D для
квадраты (ячейки),
считывания содержимого ячейки ленты в каждый
момент времени, печатания нового символа в этой
(обозреваемой) ячейке и передвижения ленты на одну
и
одинаковые
Монечный
атомат
А
Vc/пройство I): счи-
\ть/бает,лечи/гюетна\
Лента, разбитая на одинанобь/е подлине пдадраты
/
I
)/
Вкаждый момет бремени
(/стройстбо Л обозребает
обиннбадрат ленты
1.7. Машина
Рис.
ячейку
принадлежат
что
влево
или
Тьюринга.
вправо. Символы
ленты
алфавиту X (для удобства считаем,
содержится пустой символ Л, т. е. пустая
конечному
в
X
ячейка ленты либо пуста, либо в ней
только
один символ. В каждый момент
содержится
времени лента содержит только конечное число
непустых символов.
Входом для А (рис. 1.7) в каждый момент времени
ячейка). Каждая
является
символ
из
X, считываемый устройством D.
Выходом Л, который
однозначно определяется по
считываемому символу из X и внутреннему состоянию Л,
U
является элемент из
(стоп)*), где М=
(ХхМ)
=
{«/7, Я, Я}.
Если
выходом
является
*) Напомним (см. Приложение 1),
теоретико-множественное
объединение.
что
U
«стоп»,
означает
то
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
32
1ГЛ. I
машина Z прекращает вычисления. Если выходом
является пара (х, т), то автомат А с помощью
D
устройства
печатает*)
в
и
обозреваемую ячейку символ х
(если т=Л),
месте
(если
перемещается на одну ячейку влево
вправо (если т П) или остается на
=
Н).
Определение 1.5.2. Каждой машине
Тьюринга Z сопоставим функцию Fz(nitri2,
nr) такую,
что если Z в начальном состоянии нет {k')»
=
команда
элемента:
перемещения
если
поступающий
сигнал,
направления Л,
с
равен нулю, то
следующий такт надо
в
выполнять
команду k\ в противном
случае
команду k'\
«перейти
к
k»
элемент
должен
выполнению
перейти к
k (это
команды
можно
рассматривать как
сокращенную форму записи
«Л=0: да (£),
«{A)k\
k'»
нет
(£')»);
в
выполнения
результате
этой команды элементом а
&-го
содержимое
регистра
передается в регистр k' того
который
элемента,
является
ближайшим соседом
направлении Л;
«А
поместить
b»
элемент
должен
в
в
направлении Л
в
свой
поместить
регистр BR величину Ь\
«останов»
эта
команда
выполняется
только
исчезновении
при
сигналов на входах
элемента
до
входы
тех
не
передачи
пор,
пока
поступит
на
его
команда
управления
на
какую-либо другую команду
внутренней программы.
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
64
В
[А]
рис. 1.14,
и
показано,
что
элемент,
[ГЛ. I
изображенный
на
позволяет реализовать команды т, е, +,
нас отсутствует конструирующая головка,
t±(n). У
подобная той, которая была в пункте 1 для КТ-машины (см. рис. 1.13). Вместо этого мы выполняем
конструирования (или печати) только в
квадратах, расположенных над Си а затем
элементы
перемещаем
программным
конструируемые
путем.
3. КТ-машина на любой стадии может быть
описана четверкой: Р
собственная программа; /
выполняемая в данный момент команда программы; Г
состояние конструкционной
состояние ленты; С
операции
двух
области.
Для приведенной
выше конструкции справедливы
Теорема 1. Любая конфигурация вида (Р9 /, Г, С)
эффективно вкладывается в решетку.
Теорема 2. Существует эффективная процедура,
при помощи которой для любого КТ-автомата А
можно получить KJ-автомат с (А)
(«конструктор Л»),.
обладающий следующим свойством. Если в начале
на
управляющую головку с (А) поступает
команда «перейти к /», то он начинает строить
копию
А в трех рядах конструкционной области
непосредственно над собой, а затем передает на
управляющую
головку этой копии команду
«перейти к /».
Так как при выполнении процедуры, подробно
описанной в [Л], на один элемент автомата А приходится
около трех элементов с (А), то по-прежнему может
казаться, что любая машина в состоянии конструи*
ровать лишь более простые машины.
Все конфигурации вида (Р, /, Г, С) эффективно
работы
нумеруемы.
Теорема 3. Существует универсальный
конструктор Миу обладающий тем свойством, что если
ленте записать число п в двоичном коде / , то
строит в своей конструкционной области п-ю
конфигурацию Мп
fn: Mtt->Mn.
на его
он по*
САМОВОСПРОИЗВОДЯЩИЕСЯ АВТОМАТЫ
§ 1.9]
Это
утверждение
обращения
к
можно
либо
путем построения
конструктора Ми.
Почему
«доказать»
модифицированной
же
самовоспроизводящимся? Потому,
«втором поколении»
Ми
что
не
путем
Тьюринга,
универсального
является
/п
хотя
Ми >?,
либо
гипотезе
блок-схемы
65
и
:
Ми
Миу
но
во
воспроизведение
(Элемент, создающий свою койию и не
не является самовоспроизводящимся.)
Следуя Майхиллу, в (22] доказываются две теоремы.
Теорема. Для каждой рекурсивной функции h
существует такая машина Мс, что
прекращается.
создающий генов,
/п: Mc->Mh(n)
(с не зависит
Теорема (фон Нейман). Существует
самовоспроизводящаяся машина.
4. Совершенно ясно, что описанные
от
h).
нами модели
самовоспроизведения могут быть легко выполнены в
виде электронных схем, подчиняющихся законам
квантовой механики. В связи с этим несколько
озадачивают высказывания Вигнера (Wigner, 1961) *), в
которых утверждается невозможность процессов
самовоспроизведения в квантово-механической системе (он
отстаивает точку зрения, что для объяснения многих
биологических процессов, в том числе и сознания,
недостаточно
еще
только
особые
одних
физических законов;
законы**). В
«биотонические»
нужны
шестом
работы [В]***) показывается, в чем, по нашему
мнению, заключается ошибка Вигнера.
пункте
5. Предложенный автомат можно рассматривать
как программу, выполняющую несколько вычислений
параллельно (Холланд, Вагнер). В таком случае с
точки зрения программирования становится
интересным получение воспроизводящейся программы, т. е.
*) Wigner Е. Р, The probability о! the existence of a
self-reproducting unit, «The Logic of Personal Knowledge: Essays
presented to Michael Polanyi», The Free Press, Glencoe, Illinois,
1961, pp. 231-238.
**) Мне кажется, что мы как ученые, не можем утверждать,
что биотонические законы не нужны; просто их необходимость
не следует из доводов Вигнера.
***) См. сноску на стр. 56.
НЕРВНЫЕ СЕТИ, КОНЕЧНЫЕ АВТОМАТЫ
66
[ГЛ. I
программы, выполняющей нужные сдвиги в пределах
решетки, в результате чего производятся
необходимые модификации числовых массивов, и вычисления
продолжаются. К сожалению,
относящиеся к
публикации,
все
подобного рода системам,
являются
Это говорит о том, что мы еще мало
продвинулись в этой области.
6. Пункт 7(6) работы [В] посвящен некоторым
свободным аналогиям с биологией. Мы пользовались
значительно более сложными элементами, чем
элементы фон Неймана, которые имели 29 состояний. По
предварительными.
отношению
к
проблемам биологии
ибо
живая
это
кажется
имеющая
сложную
метаболических путей,
может выполнять любую операцию нашего модуля,
так как в управляющей клетке ДНК, как мы думаем,
содержится больше бит информации, чем в нашем
элементе. Так что мы, возможно, во многом
превосходным,
структуру, включающую
проигрываем,
клетка,
сотни
чрезмерно ограничивая
информационное
содержимое нашего элемента.
Сравнивая
нашу модель с воспроизведением
организмов, мы отмечаем следующее:
1. Наша программа была выполнена в виде
последовательности клеток, в то время как
биологические программы представляют собой
последовательности, хранимые в каждой клетке.
2. Мы используем полное описание, в то время
как «природа использует» неполное описание.
3. Мы используем лишь незначительную долю
вычислительных возможностей нашей модели
живых
(последовательное выполнение
4. Созданные
операций вместо параллельного).
конфигурации пассивны, в то
нами
время как биологические процессы определяются
активным взаимодействием и взаимовлиянием между
отдельными подсистемами.
В [В] показывается, как
модифицировать нашу
модель с учетом п. 1. Учесть пп. 2 4 сложнее, и мы не
стали рассматривать эту задачу, хотя и отметили,
как ее увязать с параллельным способом работы
наших
устройств.
2
Глава
Структура
и
случайность
§ 2.1. Зрительная
В
пример
этом
система
параграфе
структуры
лягушки
обсудим
мы
мозга.
С
этой
один частный
целью
мы
рассмотрим
работы Леттвина (Lettvin), Матурана (Maturana),
Маккаллока и Питтса*). Вместе с ними мы изучим
системы
структуру зрительной
лягушки.
которых они
обнаруживают при помощи зрения. Они ловят только
движущихся насекомых; неподвижные предметы
никогда не привлекают их внимания. Большой
движущийся объект вызывает у них двигательную реакцию
в виде прыжка.
Неподвижный же объект,
Лягушки
по-видимому,
не
опознают
окружающих
питаются
их
изменяет
насекомыми,
особенностей,
как
Скорее
выбирают ее из
поведения.
жертву и
объектов потому, что
свою
она
движение,
контраст и, возможно,
всего
обладает рядом
размер,
определенный
они
таких
определенный
цвет.
Эта
лягушек опознавать свою жертву и ловить
меняется при некоторых изменениях в
способность
ее
не
окружающей
среде,
например
при
изменении
освещения.
Указанные
выше
систему лягушки
с
авторы исследовали зрительную
установления тех свойств
целью
*) «What the Frog's eye tells the Frog's brain», Proc. IRE, 47
(1959), 1940 1951. [Русский перевод: Леттвин Джм
Матурана Г., Маккаллок У. и Питтс У., Что сообщает глаз
В сб. «Электроника и кибернетика в
М, ИЛ, 1963.]
«Physiology and anatomy of vision in the Frog», J. Gen.
Physiol. 43 (Suppl.) (1960), 129 175; «Two remarks on the visual
лягушки
мозгу лягушки.
биологии и медицине»,
system of the Frog», in W. Rosenblith (ed.), «Sensory Communi*
cation», The M. I. T. Press, Cambridge, Mass., 1961, 757 776.
СТРУКТУРА И СЛУЧАЙНОСТЬ
68
[ГЛ. 2
этой системы, которые позволяют лягушке различать
понятия (universals*)): враг и жертва.
На рис. 2.1 изображены: глаза лягушки (£),
идущие от них зрительные нервы (О) (которые затем
Рис.
2.1.
Схематическое
зрительной
пересекаются)
заканчиваются.
и
отдел
системы
мозга
Этот отдел
изображение
лягушки.
(С),
мозга
в
котором
они
называется
верхним
перешейком (superior colliculus) или зрительным
бугром (optic tectum). Остальные указанные на рисунке
отделы мозга здесь не обсуждаются. Стрелки дают
это
*) В Оксфордском словаре говорится, что «universal»
утверждается обо всех индивидуумах или разновидностях
то, что
класса
рассматриваемые
или
как
вида;
абстракция
имеющее
или
основное
абсолютное, образное
существование; основной
термин
или понятие.
понятие,или
номинальное
ЗРИТЕЛЬНАЯ СИСТЕМА ЛЯГУШКИ
§ 2.1]
некоторое
о том,
представление
как
69
зрительные
отображаются в зрительном бугре.
Луч света, проникая в глаз (рис. 2.2),
стимулы
достигает
дна, где он попадает на сетчатку, проходит через
прозрачные ганглии и промежуточные клетки и,
наконец, достигает палочек и колбочек.
Возбужденные
в
достаточной степени светом палочки и колбочки
создают непрерывно меняющуюся разность потенциалов,
Направление
Т
Т
т
т
света
т
т
ооооооооооооо
Волокна зрительных нервов
ооооооооооооо
Ганглиозные клетки
ооооооооооооо
Промежуточные
ооооооооооооо
Палочки.
Рис. 2.2.
U
клетки.
колбочки.
Прохождение луча света через
сетчатку лягушки.
которая через промежуточные
Аксоны
нейроны
вызывает
промежуточных клеток в свою
очередь соприкасаются с дендритами ганглиозных
клеток (нейронов). Волокна зрительных нервов
это
аксоны
Эти волокна проходят
ганглиозных
клеток.
через сетчатку и, собравшись вместе, образуют
идущий к мозгу пучок, называемый зрительным нервом.
Место выхода нерва из глаза называется слепым пят*
импульсы.
этих
ном.
У лягушки
(палочек
и
имеется
колбочек),
промежуточных нейронов
клеток.
Ввиду
и
2,5
3,5
полмиллиона
рецепторов
миллионов
ганглиозных
большого числа клеток
чтобы сложная структура
действовала просто
как
передатчик,
изображение света
рецепторах. Скорее можно
мозг
до
такого
маловероятным,
в
миллиона
около
от
и
тени,
кажется
сетчатки
который передает
образованное на
предположить, что сетчат-*
анализирует зрительный образ и передает
полученную информацию в зрительные центры.
ка
СТРУКТУРА И СЛУЧАЙНОСТЬ
70
В
1938
г.
ганглиозные
соответствии
локальные
Хартлайн
клетки
с
их
(Hartline)
разбить
можно
реакцией
в
ответ
[ГЛ. 2
показал*),
на
на
что
три класса в
ограниченные
световые
раздражения их поля
восприятия. Поле восприятия ганглиозной клетки
определяется как та часть поля зрения, которая отображается
на множестве всех тех
рецепторов, возбуждение
которых влияет на данную ганглиозную клетку. Эти
классы таковы:
1. Клетки, которые длительно, но с некоторым
запозданием реагируют на появление пятна света.
2. Клетки, которые реагируют на появление и
исчезновение
света
кратковременной серией
частых
импульсов.
3. Клетки, которые сразу и в течение длительного
времени реагируют на исчезновение пятна света.
Эти наблюдения явились первыми, показавшими,
что
ганглиозные
сложных
операций
света
являются
клетки
над
выполняют
зрительным
не
несколько
образом. Но
пятна
настолько
лягушки
раздражителями, как муха или-червь. Это
позволяет предположить, что ганглиозные клетки до
некоторой степени повторяют, но более грубым и
непостоянным
образом, первоначальную конфигурацию
зрительного образа с некоторыми локальными
различиями. Но восприятие понятий, что следует из
поведения лягушки, по-видимому, требует наличия
некоторых функциональных инвариантов деятельности
составных частей ее зрительной системы. Таким
для
естественными
образом,
мы
выполняет
предполагаем,
вычисления
над
что
сетчатка,
зрительным
возможно,
образом,
которые способствуют ^выявлению таких характерных
свойств, как наличие врага или жертвы. Леттвин и
другие пытались найти подходящие функциональные
инварианты и, следовательно, аналитические функции
ганглиозных
клеток,
применяя естественно-научный
подход и изучая их в терминах реакций на реальные
объекты окружающей среды.
*)Н art line Н. К., The response of single optic
nerve
vertebrate eye to illumination of the retina, Amer. J.
Physiol. 121 (1938), 400 415. {Прим. ред.)
fibres
of
the
ЗРИТЕЛЬНАЯ СИСТЕМА ЛЯГУШКИ
§2.1]
В
своих
исследованиях
они
американскую
лягушку»
Лягушку помещали таким
«обычную
71
использовали
(Rana
pipiens).
чтобы
центре полусферы диаметром 14
дюймов, которая служила экспериментальным полем
образом
был
один
глаз
зрения.
Электрод
(рис. 2.3),
в
вводили
в
лягушку
так,
что
он
мог
Минрозлептрод
Алюминиевая
полусфера^
Рис. 2.3. Установка для изучения
зрительной системы лягушки.
реагировать либо на активность одной ганглиозной
клетки (конец электрода помещали на аксон в
нерве), либо на активность
бугре. Алюминиевая полусфера
зрительном
клетки в
зрительном
составляла около
третих поля зрения одного глаза лягушки.
Подходящей ориентацией животного можно было
охватить любую желаемую часть поля зрения и полностью
контролировать поле восприятия изучаемых клеток.
Стимулирующие предметы перемещались по
внутренней поверхности с помощью магнита, который
двигался
по
внешней поверхности. Было использовано
много различных по форме и виду предметов,
например темные диски, темные полоски и темные квадраты
двух
72
СТРУКТУРА И СЛУЧАЙНОСТЬ
[ГЛ. 2
(заметьте, что стимулы не предполагали реакции на
цвет*)).
Было обнаружено, что по своей реакции ганглиозные клетки распадаются на 5 групп.
Группа I. Детекторы границы. Эти волокна имеют
поля восприятия от 2 до 4 градусов в диаметре. Они
реагируют на любую границу между двумя
оттенками серого в поле восприятия, если она является
резкой. Измеряется, по-видимому,
границы, чем степень контраста.
резкость
скорее
Реакция
если
граница движется, и не меняется, если
контраста изменяется в очень
широких пределах. Если в поле нет никакой границы, то
усиливается,
освещение данного
нельзя вызвать путем
реакцию
каким бы резким оно ни было.
изменения
Другим
клеток первой группы является то, что
темноте в поле восприятия возникает граница
включается
свет,
то
после
короткой
яркости,
свойством
если в полной
и затем
паузы наступает
длительная реакция.
Аксоны первой
волокна
это
первого
группы
малое, хорошо
классификации Хартлайна
сфокусированное пятно света определяется как
класса
в
резкая граница.
Группа II. Детекторы движущейся границы и
границы выпуклой темной области. Эти волокна имеют
поля восприятия от 3 до 5 градусов. Они также
реагируют только на резкие границы между двумя
оттенками серого, но только в том случае, если граница
является кривой и движется, а темная область
выпукла: Реакция опять же не меняется в широких
пределах освещенности, грубо говоря, между тусклыми
сумерками и ярким полднем. Они не принадлежат ни
к одному из классов Хартлайна и не реагируют на
световые пятна и раздражители, у которых светлые
области хотя и выпуклы, но неподвижны.
Группа III. Детекторы меняющейся или движущейся контрастности. Эти
волокна
имеют
поля
вос-
*) Реакция на цвет обсуждается в статье: W. R. A. Muntz,
Effectiveness of different colors of light releasing the positive photoactic behavior of Frogs
J. Neurophysiol. 25 (1962), 712 720.
...
,
ЗРИТЕЛЬНАЯ СИСТЕМА ЛЯГУШКИ
§ 2.1]
приятия от 7 до
11
относятся
сущности,
Они,
градусов в диаметре.
ко
в
второму классу классификации
их реакция не меняется в
Хартлайна. Однако
широком диапазоне
73
освещенности,
если
и
один
тот
же
постоянной скоростью на одном и
том же фоне. Хотя их реакция непродолжительна, они
включаются только тогда, когда происходит
смещение или изменение контрастности. Реакция тем
интенсивнее (выше по частоте), чем резче граница и чем
быстрее она перемещается.
Группа IV. «Сумеречные» детекторы. Эти
силуэт движется
с
к
относятся
детекторы
Хартлайна. Их
классификации
классу
третьему
восприятия достигает 15
градусов. Они реагируют на любое потускнение всего поля
восприятия с учетом расстояния до центра этого поля.
При реакции границы не играют никакой роли. Одна
и та же степень потускнения дает ту же реакцию,
более или менее независимую от уровня первоначальной
поле
освещенности.
Группа
можем
даже
V. Эта группа
сказать,
Мы
малочисленна.
ли
имеет
она
поле
не
восприятия
в
Клетки этой группы возбуждаются
с частотой, обратно пропорциональной интенсивности
средней освещенности. Когда освещенность меняется,
обычном
смысле.
частота медленно изменяется до своего нового уровня.
Каждая ганглиозная клетка принадлежит только
к
одной
из этих
групп, а клетки каждого класса
равномерно распределены по сетчатке. В любой
небольшой области сетчатки можно обнаружить
представителей всех групп пропорционально их общему
соотношению.
Аксоны
разных
клеток
-слоях
совмещены
(нервные
слое
в
действительности
слоя
окончания
они
пятой
образуют
группы
четыре
«непрерывный» образ
операцией, выполняемой
лиозными
клетками.
Эти
сетчатки
в
из них
два
группы),
нервных окончаний. Каждый из
нервных окончаний формирует
бугре
с
оканчиваются
группы
бугра. Однако
нервных окончаний третьей
в
слоев
каждой
зрительного
лежат
так
что
основных
этих
в
в
четырех
зрительном
соответствии
соответствующими гангчетыре слоя производят
СТРУКТУРА И СЛУЧАЙНОСТЬ
74
зрительного
в
и
регистрацию,
любую
бугра
достаточно
приходят нервные
[ГЛ. 2
область
малую
окончания
всех
слоев одного и того же места сетчатки.
Таким образом, функция
к
сводится
светлых
образа.
в
простой
и
темных
Напротив,
анализе
передаче
пятен
она
каждой
сетчатки лягушки не
всей
мозаичной
образовавшегося
заключается
точки
этого
на
главным
изображения
картины
ней
образом
по
четырем признакам (граница, движущиеся кривые,
меняющаяся контрастность и локальное потускнение),
степени освещенности
и
передаче этой информации
в зрительный бугор, где эти функции разделяются в
четырех конгруэнтных слоях*) нервных окончаний.
Сетчатка преобразует зрительный образ из
мозаики освещенных точек в систему частично
перекрывающихся качественных областей, в которой любая точка
описывается
в
окрестностью.
терминах ее связи с
Так как преобразование
окружающей
является
сетчатки, то особое значение имеет
интегрирующая способность ганглиозных клеток. Эти
основной
функцией
соображения побудили Леттвина
анатомически
исследовать
способность
и
его
коллег
ганглиозных
клеток
поступающую к ним информацию,
определить связь между различными
комбинировать
пытаясь
морфологическими
отличаются
типами
структурой
операциями,
которые
пять
клеток
древовидных
они
исследованиям в этом
Существует
(типы
дендритов) и
выполняют. Обратимся к
ганглиозных
их
их
направлении.
анатомически
различных
Вы можете заметить, что
показанная на рисунке классификация дендритов
позволяет сделать предположение о существовании двух
основных подразделений внутреннего сетчатого слоя
ганглиозных
клеток
(рис. 2.4).
(inner plexiform layer**)), хотя, несомненно, каждое
подразделение можно в свою очередь разбить на
несколько слоев.
За обсуждением
значения этого
факта
*) Точки различных слоев, которые перемешаны между
собой, сходятся в одной небольшой области сетчатки.
**) Слой сетчатки, занимаемый дендритами ганглий,
называется внутренним сетчатым слоем,.
ЗРИТЕЛЬНАЯ СИСТЕМА ЛЯГУШКИ
§ 2.1]
75
мы отсылаем читателя к третьей из оригинальных
работ, упомянутых в начале этой главы.
I. Узкое однослойное поле. Это мельчайшие ганглиозные клетки. Главные дендриты простираются
только до
внутренних слоев внутреннего сетчатого
слоя и там ветвятся плотным и узким плоским кустом.
Рис. 2.4. Пять
типов
ганглиозных дендритовых
клеток.
II. Многослойное Е-распределение. Это
следующие по величине ганглиозные клетки. Главные
дендриты простираются только до внутренних слоев внут«
реннего сетчатого слоя
и там
ветвятся
плоским
Однако
каждая ветвь по всей своей длине имеет
отростки; некоторые из них тянутся до внешних слоев
внутреннего сетчатого слоя, а другие остаются во
внутренних слоях.
образом.
III. Многослойное
Н-распределение. Следующие
величине ганглиозные клетки.
простираются до
Однако
слоя.
распростершихся
IV.
по
слоев
внутреннего сетчатого
широко
во
внутренних, а другое
от них отходят
дерева,
внешних
большие
внешних
одно
по
Главные дендриты
во
два
слоях.
Широкое однослойное
величине
ганглиозные
поле.
Это самые
Главные денд-
клетки.
СТРУКТУРА И СЛУЧАЙНОСТЬ
76
[ГЛ.
2
ригы простираются до внешних слоев внутреннего
сетевидного слоя и там широко ветвятся над
значительной областью.
V. Диффузные деревья. Существует несколько
размеров этих клеток. Дендриты ветвятся хаотически по
всему внутреннему сетчатому слою и не имеют
плоского расположения, как это было в четырех
предыдущих видах клеток.
Если предположить, что размер поля дендритов
до некоторой степени определяет размер поля
восприятия, то появится довольно тесная связь между
типами клеток и операциями.
I. Узкое
Обнаружение
однослойное
границы.
поле
II. Многослойное
разное
Е-об-
Детекторы
темной
поле
движущейся
выпуклой
границы.
III. Многослойное
разное
IV.
Н-об-
Детекторы
и
поле
Широкое однослойное
движущегося
контраста.
детекторы.
меняющегося
Сумеречные
поле
Редкий диффузный
произвольно
сопоставляем
тип
мы
группе,
более
или
менее
измеряющей
средний
уровень освещенности.
Вышеуказанные сопоставления подтверждаются
следующими фактами. Диаметры полей дендритов
совпадают с угловыми диаметрами полей восприятия;
тела клеток распределены по размерам таким же
образом, как поля дендритов. Если диаметры аксонов
отражают размер тела, то наибольшие аксоны
должны иметь наибольшие поля восприятия, а наименьшие
наименьшие
аксоны
есть.
круглые,
по-видимому,
это
так
и
бывают не
Далее,
восприятия
а эллиптические или кардиоидные. На рисунках
ганглиозных
имеются
поля;
как
часто
поля
клеток,
выполненных
эллиптические,
так
и
Матураном,
кардиоидные дендрито-
вые поля.
Переходя от ганглиозных клеток к клеткам
бугра, Леттвин и его коллеги обнаружили
зрительного
несколько
типов
клеток,
хотя
и
не
смогли
выделить
ЗРИТЕЛЬНАЯ СИСТЕМА ЛЯГУШКИ
§2.1]
подгруппы.
они
которые
Однако
назвали
того же самого».
имеются
обнаружением
непрерывностью
поле зрения.
2.1.1.
совокупности,
«нейронами новизны»
Первые, по-видимому,
новизны
с
две
и видимых
во
77
и
«нейронами
связаны
событий,
с
а
вторые
времени интересных объектов
в
Сравнения
В эмбриологии установлено, что сетчатка по
существу является частью мозга. Работа Леттвина, Матурана, Маккаллока и Питтса обнаружила, далее,
некоторую фундаментальную структуру мозга
лягушки. Следует, конечно, подчеркнуть применимость
ни
ни
этой работы только к лягушке
анатомия,
действие поля восприятия лягушек не обязательно
являются такими же, как у млекопитающих или
других
земноводных.
Подробная работа
системе кошки выполнена
лем*).
В
зрительной
о
зрительной
Д. X. Хюбелем
коре
кошки
они
Т. Н. Визе-
и
обнаружили
клетки, сравнимые с теми, которые Леттвин и другие
нашли в зрительном бугре лягушки. Они говорят: «На
первый взгляд может показаться удивительным, что
сложность нейронов третьего порядка зрительной
системы
лягушки должна быть сравнима только со
сложностью нейронов шестого порядка в коленчатокорковом пути (geniculo-cortical pathway) кошки.
Однако
это
становится
менее
удивительным,
если
у
обоих животных обнаруживаются большие айатомические различия, особенно отсутствие у лягушки
какой бы то ни было коры или дорзально-латерального
коленчатого тела.
Несомненно, существует
параллельное
различие в том, как каждое животное использует
свою зрительную систему:
зрительный аппарат
лягушки, по-видимому, специализирован для
распознавания более ограниченного числа стереотипных
конфигураций или ситуаций по сравнению с высокой
остротой и многогранностью той же системы у кошки.
*) D. Н. Hub el, Т. N. Wiesel, Receptive fields, binocular
interaction and functional architecture in the cat's visual cortex,
J. Physiol. 160 (1962), 106 154.
СТРУКТУРА И СЛУЧАЙНОСТЬ
78
{ГЛ. 2
Вероятно было бы целесообразно выяснить, что у
кошки специализация клеток для сложных операций
отодвигается
осуществляется
в
до
более
высокого
мельчайших
деталях
уровня
и
числом
огромным
клеток».
Чего
же
структуры
можно
ждать
высокоорганизованной
от
человеческого мозга?
§ 2.2. Персептрон
В первой главе мы кратко остановились на
нейрофизиологии и построили абстрактную модель мозга
модульную сеть, илисеть из нейронов Маккаллока
Питтса. Персептрон, построенный сотрудниками Корнуэльского университета, работает на несколько
отличной основе, чем модель нейронной сети. Главное
различие заключается в том, что его создатели не
стали
предполагать, что функции нейронов жестко
фиксированы. Вместо этого они допустили, что веса
каждого нейрона могут меняться со временем. Цель
заключается
этого
нейронной
образом,
как
в
том,
чтобы
сети изменяться со
при
дать
временем
возможность
таким же
«обучении».
представлять себе как прибор
построен не для
того, чтобы узнавать специфическое множество
образов, а скорее для того, чтобы «научиться» после
конечного числа испытаний узнавать образы из
Персептрон
можно
для распознавания
некоторого
образов, который
множества.
В
персептрон образ поступает через сетчатку,
состоящую из чувствительных элементов (например,
фотоэлементов). Хотя любое воспринимаемое
изображение может быть закодировано в форме,
подходящей для входа, состоящего из набора чувствительных
элементов, однако наиболее естественно (о чем и
говорит
термин
«сетчатка»)
представлять
наблюдаемый вход, состоящий
из
света
образ
как
и тени.
который воспринимает относительно светлую
образа, возбуждается, а фотоэлемент,
воспринимающий относительно темную часть образа, не воз*
буждается.
Фотоэлемент,
часть
После
лягушки
реакция,
79
ПЕРСЕПТРОН
§2.2]
детального
становится
связанная
с
рассмотрения
ясным,
что
освещением
2.1
§
в
эта
сетчатки
двоичная
сетчатки,
имеет
мало
сходства
физиологической деятельностью.
Чувствительные элементы соединены с промежуточными элементами (формальными нейронами), которые в свою
с
Рис. 2.5.
Схематическое
изображение персептрона.
очередь могут быть соединены
ментами
с
реагирующими
эле*
(рис. 2.5).
В терминах нашего первоначального
нейрофизиологического рассмотрения нервной системы как
трехступенчатой системы сетчатка является рецептором
персептрона; промежуточные элементы охватывают
собственно нервную систему, а реагирующие элементы
являются
эффекторами
нейронам,
выходы
С
или,
которых
скорее,
соответствуют
эффекторами.
управляют
нашим
первоначальным рассмотрением совместимо
также и то, что когда на сетчатку персептрона
действует изображение, то импульсы передаются от
элемент, превосходит его порог, то этот
элемент становится активным и посылает импульсы к
элементам, с которыми он связан.
До сих пор персептрон являлся просто другим
промежуточный
воплощением сильно упрощенных
нейрофизиологических
80
СТРУКТУРА И СЛУЧАЙНОСТЬ
[ГЛ. 2
данных о
нервной системе, снабженной зрительными
рецепторами. Однако конструкторы персептрона
пошли дальше этого, так что здесь стоит обсудить
дополнительные
/.
Правила
свойства сети.
поощрения
Существует, по-видимому, много подтверждений
того, что люди имеют два вида памяти:
«кратковременную» и «долговременную». Кроме того, кажется,
что мы сначала должны запомнить мысль в
кратковременной памяти, прежде чем передать ее в
память. Время, необходимое для этой
передачи, оценивается по-разному; в частности, одна
из таких оценок равна 20 минутам. По-видимому,
долговременную
бессознательное состояние, то
что прошедших 20
минутах потеряны навсегда, так как они не были
переданы в долговременную память. В настоящее время
если
его
кто-то
впадает
воспоминания
общепринято
представляет
которой
мы
о
в
только
считать, что кратковременная память
собой в точности тот же тип памяти,
снабдили нашу модульную сеть,
прохождением по сети сложных
электрических импульсов. Далее, если
временная
активность
е.
такая
продолжается довольно долго,
',
реагирующих элементов
>26). В проведенном
эксперименте, как сообщалось,
машина научилась правильно
распознавать
буквы после 15
показов
элементами
пяти
а
Мы
для
чем только выделение
буквы,
же
т.
е.
было
показов
требуем
от
распознавания
образов
в
стандартной форме. Нам
нужна машина, которая может
каждую букву, помещенную на сет-
распознавать
чатку, даже если
она
напечатана
слегка
искаженно и
пестром фоне. Но если мы допускаем это,
то число образов катастрофически
возрастает. В этом
можно убедиться при рассмотрении
различных
вариантов стандартной буквы £, образ которой представлен
показана на
как показано на
рис. 2.8.
Следовательно, сделанный выше вывод о том,
для заучивания наизусть достаточно произвести
некоторое число опытов, по порядку равное числу
в
виде точек,
различных
Простой
3tqt
образов,
является
персептрон
не
столь
оказывается
простой персептрон
мы
что
значительным.
слишком
обсуждаем
из
простым,
методиче-
СТРУКТУРА ПРОТИВ СЛУЧАЙНОСТИ
§ 2.3J
85
ских
соображений; он полезен при рассмотрении
вопроса о памяти нейронных сетей. На самом деле
конструкторы персептрона проделали более сложную
работу. Так как для своих сетей они ставили более
трудные задачи, то и строили их с более сложной
структурой. Их работа даже включает
нейрохимическое исследование памяти и описание сопутствующих
моделей.
Прежде чем закончить обсуждение этой темы, надо
честно предупредить читателя, что связанная с персептроном работа подвергалась резкой критике.
Конечно, в первых статьях конструкторов персептрона
имелись
большие претензии, и читать их следует
с большой осторожностью. Кроме того, многих
отталкивают
довольно
неудачные
сообщения
в
широкой
следует реагировать так, чтобы
отвергать всю последующую работу о сетях, которые
могут «учиться».
Однако
печати.
не
§ 2.3. Структура против случайности
Анатомия
и
работа которой
физиология
относится
к
той части нашего
высшей нервной
мозга,
деятельности, мало изучена. Хотя макроскопическая анатомия
мозга обнаружила сложную структуру, микроскопии
ческая анатомия дает смутную картину, по-видимому,
случайных взаимосвязей. Кажется невозможным,
чтобы наши гены определяли точную структуру нашего
мозга. Гораздо более вероятно, что они определяют
некоторые схемы роста, более или менее
влияниям опыта.
Кроме того,
даже строго детерминированы,
мы все равно не знаем механизма, посредством
которого мозг может распознавать понятия, например
подверженные
если
меняющимся
бы
связи
были
букву А в разных видах и при некоторых
(теория этого вопроса все-таки имеется,
§ 4.4). Поэтому конструкторы персептрона
узнавать
искажениях
см.
допускают, чтобы первоначальная структура была
случайной,
структура, которая необходима для
в
возникала
результате
вызванных
правилами поощрения. Их подход
а
та
распознавания
изменений,
образов,
СТРУКТУРА И СЛУЧАЙНОСТЬ
86
[ГЛ. 2
представляется интересным, но я все же чувствую, что
в нем чего-то не хватает.
В этой главе мы рассмотрели зрительную систему
и обнаружили подтверждение того, что по
лягушки
крайней мере
в
лягушке некоторая очень важная
предопределена генетически. В § 3.5 мы
Кована (Winograd
теорию Винограда
Там мы убедимся, что если модульную сеть,
структура
изложим
Cowan).
предназначенную для
преобразовать
таким
чувствительность
к
определенной цели,
образом, чтобы уменьшить ее
ошибкам,
появляющимся
вследствие
гибели нейронов,
то в результате получится сеть, имеющая
микроскопическую случайность, очень похожую на ту, которая
обнаружена микроскопической анатомией мозга. В
качестве
последнего
аргумента против использования
полной случайности укажем на то, что имеются
умственные
акты,
доступные ребенку, но совершенно
недоступные для гориллы. Это происходит, возможно,
вследствие генетически детерминированных различий
в структуре. Дарвиновской
эволюции понадобились
неправильного
функционирования
тысячелетия,
чтобы
или
наш
сделать
мозг
способным
узнавать образы. Было бы крайне удивительно, если
бы случайная сеть приобрела такую способность за
часов
несколько
обучения.
Однако я должен признаться, что все
вышеприведенные
утверждению:
быть
аргументы сводятся
адекватная
модель
богата
различными
структурами, вроде той, которая
прямых линий. Но это не
вопрос: необходима
Другими
словами,
если
прогресса
в
противоположных точек
следующему
мозга
должна
специфическими
обеспечивает
помогает
восприятие
ответить
на
структура для обучения?
допустить, что человеческий
ли
обладает структурой,
никакого
к
человеческого
то
мы
выяснении
не
достигнем
мозг
еще
следующих двух
зрения:
а) Человек разумен потому,
что
эволюция
структурой. Эта
структура выполняет различные функции и, в
частности, дает ему возможность учиться. Требуется
снабдила
его
некоторая
мозгом
с
очень
критическая
сложной
степень
сложности
структуры,
СТРУКТУРА ПРОТИВ СЛУЧАЙНОСТИ
§ 2.3J
чтобы сеть могла изменять себя
поощрения)
сложности ее правил
мы могли бы считать
б) Человек
снабдила
Схема
его
мозгом
с
взаимосвязей
очень
не
(независимо
таким
разумным.
разумен потому,
от
способом, который
что
сложными
имеет
67
эволюция
взаимосвязями.
отношения
к
истинно
разумному обучению, которое» является результатом
действия правил поощрения на достаточно большую,
но существенно случайную сеть.
Возможно, что истина заключается в искусном
соединении этих точек зрения. Поиск такого соединения
будет
одним из самых захватывающих этапов в
щем этого предмета.
буду*
Глава 3
Исправление ошибок при передаче
и вычислениях
Индивидуальные нейроны мозга
Кроме того, несколько
неправильно.
мозга
человека
замещаются.
могут
тысяч
работать
нейронов
погибают и никогда не
интересно знать, каким
функционировать с высокой
ежедневно
Поэтому
очень
образом такой мозг может
устойчивостью и надежностью.
Основная
цель этой главы заключается в
ознакомлении читателя с
функционально
теорией Винограда Кована по
модульным сетям,
устойчивым автоматам
которые надежно функционируют
неисправностей модулей. Эта теория
независимо от
основана
на
хорошо
теории
при наличии
шумов. Поэтому большую часть этой главы мы
посвящаем рассмотрению теории Шеннона
теории,
имеющей большое значение и представляющей
известной
шенноновской
связи
самостоятельный интерес.
§3.1. Надежный
мозг из ненадежных
нейронов
Этот параграф
посвящается краткому обзору
нейрологических данных, которые
показывают, что мозг функционирует точно и устойчиво,
несмотря на гибель и неправильное функционирование
нейронов. Мы широко цитируем обзорную работу
У. С. Маккаллока, М. А. Арбиба и Дж. Д. Кована*).
В этой книге мы будем строго придерживаться
электрической гипотезы центрального торможения и
возбуждения. Она требует, чтобы электрические свой-
некоторых
*) Neurological models and integrative processes, in M. С Vovits, G. T. J a cob i and G. D. Goldstein (eds.), Selforganizing Systems,
(1962), 49 59.
1962,
Spartan
Books,
Washington,
D.
С
НАДЕЖНЫЙ МОЗГ ИЗ НЕНАДЕЖНЫХ НЕЙРОНОВ
§ 3.1]
89
ства
передачи и геометрия структур определяли
выход как специфическую функцию входа каждой ткани.
Возможно,
простым примером такого
между структурой и ее
функционированием является верхняя олива (superior
olive) (рис. 3.1), крупные клетки которой получают
однозначного
сигналы
от
самым
соответствия
обоих
ушей. Анатомия
этих
клеток
и
их
Рис. 3.1. Мозг человека в поперечном разрезе.
синапсов
такова,
что
они
возбуждаются
уха, тогда
обоих ушей,
идущих только от одного
идущие
и
одновременно
клетка
остается
от
от
сигналов,
как сигналы,
гасят
невозбужденной.
друг друга,
С помощью этих
мы определяем направление звука и слышим
сигнал в одном ухе, несмотря на значительный общий
клеток
шумовой фон
обоих ушах.
может
примером
в
Вторым
(рис. 3.1), который
состоит
из
служить
свода
мозжечок
крупных клеток,
каждая
из которых получает сигналы от
органов обоих ушей и передает информацию об
ускорениях головы. На вход поступают сигналы почти
от всех частей тела и остальной части мозга. Они
вестибулярных
поступают
однотипные
на
множество
аксоны
мелких
клеток, тонкие и
которых делятся, пересекая
ответвления гигантских клеток, как провода пересекают парал-
[ГЛ. 3
ИСПРАВЛЕНИЕ ОШИБОК
9Э
лельные ряды
регулярно расположенных телефонных
столбов; многие тысячи проводов присоединены к
каждому столбу своего ряда. Мозжечок выполняет роль
часов во всех двигательных
актах, таких,
как письмо,
и
других, в которых ускорения и замедления должны
быть точно отмерены и зарегистрированы в
промежутки времени, слишком короткие, чтобы в этом
процессе могли
участвовать
Основанием
рассмотрения верхних
является то, что функция ткани
мозжечка
принадлежит
рефлексы.
для
оливов
и
какому-либо отдельному нейрону, а
всем
нейронам. Анатомически это
обнаруживается во временном запаздывании, так как
оба органа срабатывают, один выполняя функцию
засечения
обнаружения, а другой
времени, с
точностью до
как
при
1 2 микросекунд, тогда
обнаружении
их
совпадения
имеют
испускании
при
большее 1/3 миллисекунды.
как их компоненты
импульсов,
так
и
стандартное отклонение,
Из данных патологии
следует, что потеря точности незначительна, несмотря на
гибель одной десятой доли числа всех клеток. Мы
подчеркиваем, что как обе верхние оливы, так и
функционируют более устойчиво, чем их
мозжечок
даже если каждая компонента
ту же функцию, но в разное время
компоненты,
выполняет
одну
от
и
различного множества
Прежде
должны
чем
ввести
входов.
продолжить наши рассуждения,
некоторые новые понятия. Входы
нейрона
X
^
6
с~*7
*
Ю-
^
Рис. 3.2. Взаимодействие эффектов,
возбуждает
модействием
тов
аф-
называются
ферентами.
.
мы
Под
мы
взаи-
афферен-
понимаем
схематически
ситуацию,
показанную на рис. 3.2,
когда афферент не
тормозит сам нейрон, а блокирует
другом афференте. Таким образом, если на
импульс
этом рисунке импульс, идущий по А, достигает X
одновременно с импульсом, идущим по В, то его прохождев
или
§ 3 1]
НАДЕЖНЫЙ МОЗГ ИЗ НЕНАДЕЖНЫХ НЕЙРОНОВ
91
ние прекращается; если же он не встречается с другим
импульсом, то его прохождение продолжается и
приводит к возбуждению или торможению этого нейрона.
Под булевой функцией мы
/(*ь
хп) *), аргументами и
...,
0
являются только два
числа
можем
отношение
что
считать,
Питтса
1. Таким
и
функцию
которой
образом, мы
понимаем
значениями
выход»
«вход
булевой
существует много
функцией. Нетрудно показать,
булевых функций, которые не могут вычисляться
Питтса (например, /(0,0)
нейронами Маккаллока
Маккаллока
нейрона
описывается
.
что
=
1; /(0,1) =/(1,0) =0). Если
=/(1,1)
формальные нейроны
=
наши
то
афферентов,
можно
по
построить
же
имеют
допустить,что
взаимодействие
любой данной
булевой функции
формальный нейрон, который ее
вычисляет.
Имеются
расположение
и
тел .клеток,
которое
основания
считать,
а
также
которую
каждая клетка,
в
расположением, задают ту
порога вычисляет
получаемые ею сигналы имеют
и
длительность.
нейрофизиологу-экспериментатору
нет
сожалению,
никаких
из этого точно
адаптацией
или
и
зависимости от
когда
определенную силу
к
точное
их
определяется
функцию*
что-либо
что
соединений дендритов
взаимодействие афферентов,
последовательность
Каждому
хорошо известно, что,
оснований считать, что
определяется
нашими генами,
обучением.
Начнем с деталей синапсов наших 1010 нейронов,
которые при фиксированных условиях окружающей
среды вряд ли определяются нашими генами. Нейросчитают, что достаточно большое
обычно растет. Различие в структурах
оценивают, как правило, не менее чем одним
анатомы
число
процентом.
вообще
аксонов
Соседние
никогда
не
сходные столбики клеток в коре мозга
полного анатомического сходства
имеют
по-видимому, разумно предполагать, что хотя их
синапсы в общем определены, детали в значительной
и,
*) Названа по имени Джорджа Буля, который впервые в
1840 г. изучал применение функций этого вида в математической
логике.
[гл. а
ИСПРАВЛЕНИЕ ОШИБОК
92
остаются
мере
синапсы
были
на
долю
точно
случая.
определены
в
Даже
если
деталях,
бы
случайная
гибель хотя бы одного нейрона в минуту вскоре при?
бы к их дезорганизации. Миелинизация *)
тончайших аксонов хотя бы во внешних слоях коры мозга
вела
продолжается по
возраста. Более того,
крайней мере до 50-летнего
мозг обнаруживает явные
биением сердца,
недавно приписываемые
а также
связанные с дыханием,
пульсации,
высокой частотой,
ритмическим
сокращениям
Живой
глии.
мозг,
конечно,
жесткой геометрии.
к другим параметрам,
влияющим на нервную деятельность, то заметим, что
многие из обычных химических изменений действуют
не
имеет
фиксированной и
Если мы обратимся
все
на
образом. Например,
механизмы**) стараются поддерживать
***) приблизительно на уровне 7,2. Если
компоненты
гомео-
сходным
статические
рН
мозга
это
значение
и
тела
нормальной
появляются
падает
повышается
аксона
7,4,
до
уменьшается
то
порог нейронов,
приблизительно
величины, и при таком высоком
судороги кистей рук
7,0, порог
больше, чем те
до
и
ступней
повышается
на
ног.
на
50%
рН
Когда рН
100%. Это
немного
неопасные для организма
изменения, которые появляются вследствие повышенной
гипервентиляции при усиленном дыхании, и ни одно
из них не мешает водолазу выполнять сложные
задания. Обезболивание во время хирургической
операции
рН
понижает
дыхание
мозга
продолжается
Наконец, пороги
и
приблизительно
до
6,9,
но
автоматически.
сила
импульсов чувствительны
известно, что человеческий
мозг работает, хотя и не слишком хорошо, при
температуре 42°С, довольно близкой к смертельной
к
температуре.
Однако
температуре. При температуре ниже 26° С (тела, а не
помещения) нервные ткани млекопитающих становятся
оболочки»
это
*) Миелинизация
образование «изолирующей
вокруг аксона нейрона. Клетки, имеющие такую
оболочку, называются глиальными.
**) См. также § 4.3.
***) Величина рН является характеристикой концентрации
ионов водорода.
(Прим. перев.)
НАДЕЖНЫЙ МОЗГ ИЗ НЕНАДЕЖНЫХ НЕЙРОНОВ
$ 3.IJ
невозбудимыми,
но
выше этой
градусов
при
сердце, еще
известно, что
операций
на
Давно
в
несколько
на
температуре
больные, которых
93
охлаждают для
состоянии
думать.
высокой
вспышки
частоты
время их
Более
и
того,
восстановления, порог
силу импульсов.
известно, что во время восстановления их градиенты
напряженности действуют на другие нейроны,
в
клетках
нервных
в
находящиеся
их
и
их
аксонах
Эти
окрестностях.
значительны, и их легко
изменяют
обнаружить,
эффекты
когда
много
возбуждается одновременно. Они должны
встречаться до некоторой степени и в нормальных условиях
и их можнр отнести за счет больших флуктуации
порогов, которые мы обнаруживаем в них. Но
используются ли эти возбуждения, доставляющие, скажем,
компонент
10% от порогового значения, при передаче сигналов,
или они представляют собой только шум, это еще не
установлено.
Надо
признать
что
возможность
изменений
случайных
изложены
выше,
в
и
случайностей. Наконец,
локальных
многих
силу причин, подобных тем,
из-за
так
многих
как
незначительных
каждая
точка
представляет собой небольшую область
высокого характерного сопротивления, которая и дол«
жна
работать при температуре тела, то ее порог
переключения
должен
В
модель
меняться.
любом
случае
должна
правильно
быть
адекватная
построена
функционировала, несмотря
случайные изменения.
При изучении адекватной
мы должны
модели.
учесть
чтобы
она
на локальные
нейрологической
следующие два
модели
нарушения
в
нарушение состоит в гибели нейронов:
время болезни эти нейроны испускают
Первое
часто во
длинные серии
после
нейрологическая
так,
импульсов, когда их не должно быть,
не испускают импульсов, хотя в
или
гибели
нормальном
испускать их.
состоянии эти
нейроны
Второе
должны были
нарушение состоит в рассеянном
распределении во времени и пространстве импульсов,
спонтанно возникающих в аксонах, или в виде
невозможности
их
распространения.
ИСПРАВЛЕНИЕ ОШИБОК
94
§ 3.2. Многократные
схемы
Познакомившись
с
[ГЛ. 3
фон Неймана
содержанием предыдущего
вплотную подошли к проблеме: каким об-»
разом модульная сеть может надежно
функционировать,
несмотря на неправильную работу отдельных
йейронов? Необходимость решения этой проблемы
подтверждается следующим простым подсчетом.
параграфа,
мы
Рассмотрим цепочку, состоящую из п модулей, и
вероятность сбоя *) каждого нейрона
равна р. Тогда вероятность того, что выход цепочки
является правильным, как нетрудно подсчитать**),
равна
(1 р)п. Если п взять достаточно большим***),
предположим, что
то
даже
принять
малом
при
р
1/2. И
значение
(1
величина
-нас,
р)п
может
не
конечно,
устраивает,
одинаковой вероятностью может быть
как правильным, так и ошибочным! Мы снова убеж«
если
выход
с
даемся, что при рассмотрении модульных сетей
(лучшим образом приближающихся к нашей модели
мозга),
в
неправильного
ответа,
которых при
*) Под сбоем
т.
е.
работе нейронов допускаются
здесь понимается выдача
когда
нейрон
вместо
0
сбои,
нейроном
выдает
1
или
вместо
I
(Прим. ред.)
**) На самом деле этот подсчет неверен. Производя подсчет
по формуле, предложенной автором, можно прийти к следующему
парадоксу.
Пусть, для определенности, выход элемента
двоичный {0, 1} и вероятность его сбоя р=7г. Соединим п таких
выдает 0.
в последовательную цепочку. Тогда, согласно
приведенному выше подсчету, вероятность правильного выхода равна
р 7гп. При достаточно большом п вероятность правильного
элементов
=
выхода может быть сделана сколь угодно малой. Вероятность того,
что выход неверен, равна 1 /?=1 7гп и в этом случае может
быть сколь угодно близкой к единице. Но это означает, что,
получив на выходе 0, надо рассматривать его как 1 (с
вероятностью 1 7гп) и 1 на выходе
как 0. Таким образом, соединив
последовательно достаточно много элементов, работающих
ненадежно, мы могли бы получить выход с любой заданной степенью
надежности. Интуитивно ясно, что если только вероятность
правильной
работы
последовательной
стремится
к
элемента
0.
=
/(*)=0.
что
полагаем,
Предположим, что мы теперь имеем совокупность сообщений
Pal
\Pl
{pt
имеет вероятность pi
> 0,
Из
3.3.1
что
2Л
О*
определения
следует,
среднее
количество информации, полученной приемником от
f-e
где
сообщение Х{
=
источника,
//(;Odef
где
SAlog2A,
=
01og20 полагается равным 0. Величину Н(Х)
энтропией этой совокупности.
Мы стремились к тому, чтобы приведенное выше
назовем
определение было правдоподобным. Однако
настоящим оправданием для этого определения является
2а1°&А
функция
что
основных задачах
3.3.2. Модель
появляется
кодирования
источника
и
и
во
то,
многих
связи.
канала
Мы договорились характеризовать сообщение
вероятностью его появления. Поэтому мы должны
характеризовать наш источник распределением
вероятностей сообщений, которые он создает. Воспользуемся
следующей характеристикой марковских процессов*):
источник
имеет
«состояний» Si, S2,
конечное
число
возможных
Sn. Кроме
того, имеется совокупность
вероятностей переходов р^, т. е. вероятностей того, что
система, находящаяся в состоянии S*. перейдет затем
*) Это
русского
...,
основное понятие теории
математика
вероятностей
носит имя
А. А. Маркова, который впервые
ввел
его.
ШЕННОНОВСКАЯ ТЕОРИЯ СВЯЗИ
§3.3]
в
состояние
процесс
в
Sj.
Чтобы превратить
источник
этот
сообщений, нужно
105
марковский
только
предположить, что при каждом переходе из одного состояния
другое создается одна буква. Состояния будут
«остатку влияния» предыдущих букв*).
всевозможных
дискретных марковских
Среди
процессов имеется одна группа процессов с особо
Этот специальный
важными для теории связи свойствами.
в
соответствовать
Рис. 3.8. Два марковских источника: а) эргодический; б) неэргодический.
класс состоит из «эргодических» процессов, и
соответствующие источники мы будем называть эргодическими источниками. Хотя строгое определение эргодического процесса несколько сложно, общая идея
проста. В случае эргодического
бесконечная последовательность,
каждая
процесса
создаваемая
и те же статистические
процессом, имеет одни
свойства. Поэтому частота букв, пар
полученных на
начальных
букв
этим
и т. п.,
кусках этой последовательности,
с
увеличением их длины будет стремиться к
определенным пределам, не зависящим от этих начальных
кусков. В действительности это верно не для всякой
последовательности, но множество последовательностей,
для которых это неверно, имеет вероятность,
*) Ради развлечения читатель может попытаться
«марковский конечный автомат» (см. § 1.3).
равную
означает
определить
ИСПРАВЛЕНИЕ ОШИБОК
106
[ГЛ. 3
На рис. 3.8 показаны графы двух источников,
первый из которых эргодический, а второй
неэргодический (вершины соответствуют состояниям схемы, а
вероятности переходов указаны около
соответствующих дуг),причем предполагается, что различные
переходы задаются различными буквами.
Теперь
свяжем
с
нашим
понятие
состояния Si
вероятностей pt(j) выработки различных
символов /. Следовательно, для каждого
5г- существует энтропия
возможного
множество
возможных
состояния
источником
дискретным
энтропии. Для каждого
имеется некоторое
типа
марковского
Hi
=
-2iPiU)l°g2PiU)'
j
Энтропия
значение
источника
величин
Н определяется
как
Ни которые осреднены
среднее
в
соответствии с
вероятностями рг- осуществления
соответствующих событий
//=2яд
i
Эта
величина
символ
-2 ptPi (у) iog2 Pl (у).
=
I, J
называется
сообщения. Ясно,
энтропией
что
пару
источника
«источник
на
S
кодирующее устройство» теперь можно рассматривать
как новый источник S'. Процесс кодирования просто
заключается
символов
последовательность.
созданных
точности
на
замене
другую
же
множество
одной
множество
составным
самое
последовательности
закодированную
Следовательно,
новым
то
в
источником
сообщений,
S\ имеет в
распределение вероятностей,
что
и
сообщений,
созданных
первоначальным
источником S. Из этого следует, что энтропия
источника S равна энтропии источника S', т. е, в процессе
кодирования Н не меняется. Этот факт будет
3.3.4.
Если источник является эргодическим (с этого
использован в п.
будем рассматривать только эргодические
источники), то число тех случаев, когда данный путь
(iy /') на графе переходов встречается в
последовательности большой длины N, приблизительно пропори
момента
мы
ШЕННОНОВСКАЯ ТЕОРИЯ СВЯЗИ
§ 3.3]
107
вероятности
пребывания в состоянии /,
Я*, и с последующим прохождением этого
е. приблизительно равно PiP^N. Если N
ционально
скажем
пути,
т.
достаточно велико, то
±6',
превосходящая
значения,
в
за
вероятность ошибки, не
случае меньше чем е, так
этом
множества
исключением
что все
малой
вероятности, заключены в пределах
(PlPlJ±b')N.
Следовательно,
почти
все
имеют
последовательности
вероятность
P=\lp\7Pli±b')N
и j
и
\og2p/N
ограничен
соотношениями
или
^--S^7log2A
С, то можно применить такое кодирование
источника,
что
ненадежность
будет
меньше
чем
С + е, где е сколь угодно мало. Не существует,
Н
способа кодирования, обеспечивающего ненадежность,
С.
меньшую чем Н
ИСПРАВЛЕНИЕ ОШИБОК
112
Метод
Доказательство*).
первой части этой теоремы состоит не
[ГЛ. 3
доказательства
в
указании
имеющего желаемые свойства, а
в доказательстве того, что искомый код должен
существовать в определенной группе кодов. Будем
усреднять по этой группе частоту ошибок и покажем, что
полученное среднее может быть сделано меньше чем е.
Но если среднее некоторого множества чисел меньше
чем е, то в этом множестве должно существовать по
крайней мере одно число, меньшее е. Это и даст
желаемый результат.
Пропускная способность С канала с шумом была
способа кодирования,
как
определена
С
где X
канала.
значение
быть
значение
У
выхода
на
входе
такого
которые
канала.
рассматриваемый источник 5
то можно взять другой
если
энтропию #H. Пусть 50
Рассмотрим возможные
последовательности
принимаемые
передаваемые и
длины Т. Из теоремы 3.3.2 следует, что Г можно
выбрать
настолько
большим,
что
выполняются
слеДую-.
щие четыре условия.
(а) Передаваемые
распадаются на два
класса:
последовательности
высоковероятная группа,
содержащая примерно 2ТН№ членов, и остальные
последовательности с малой суммарной вероятностью.
(б) Аналогично имеется высоковероятное
множество принимаемых последовательностей, содержащее
примерно 2ГН000, 1 -> 1Н. Сообщения 000 и 111
рассматриваются как точки (0, 0, 0) и (1, 1, 1)
трехмерного
пространства. Они являются двумя
вершинами единичного куба
(рис. 3.11). Если при передаче
Рис. 3.11. Трехмерный куб.
произойдет не более одной ошибки, то принятая
последовательность будет соответствовать либо
переданной
вершин.
вершине, либо
Таким
одной
из
смежных
с
ней
образом,
0 0 0->0 0 0, 1 0 0, 0 1 0
или
0 0 1,
1 1 1-И
или
110.
1 1, 0 1 1, 1 0 1
Заметим теперь,
что обе эти «смежные системы» не
Это и позволяет исправлять ошибки
в коде Хэмминга. Декодирующая функция является
логическим
выражением для «стягивания обратно»
пересекаются*).
вершин куба к «переданной вершине». Коды (5,2) и
(7, 4) построены аналогично, но на единичных кубах
в пяти- и семимерном пространствах соответственно.
*) Если
мы
произошла
не
010,
100, 001)
011, 101)
более
допускаем,
чем
одна
что
при передаче сообщения
то принятые сообщения
ошибка,
должны расшифровываться
как
000,
а
(000,
(111, ПО,
как 111. Если бы множества принимаемых сообщений,
соответствующие 000 и 111, имели непустое пересечение, то
такая расшифровка была бы невозможна, ибо, приняв сообщение,
принадлежащее пересечению, мы не смогли бы установить,
(Прим. ред.)
какому передаваемому сообщению оно соответствует.
ТЕОРИЯ СВЯЗИ И АВТОМАТЫ
§3.4]
§ 3.4. Теория
119
связи и автоматы
Переведем временную избыточность, обычно
связанную с передающим каналом, в избыточность
по
Вместо
одного
канала,
которому
оборудования.
последовательно передаются п символов блока, мы
использовать п
будем
каналов для
передачи п символов так, что
одновременной
каждый
канал используется
для передачи только одного символа блока (рис. 3.12).
Временная
Л символов
избыточность
-
Избыточность
Рис.
Кодирующее
устройство
П
Канал
Символов
панала
п
символов
п
/taналов
3.12.
*-
Временная
избыточность
в
сравнении
с канальной избыточностью.
При
скорости передачи k/n
коэффициент эффективности
/?), равный отношению K/N, где К
таком подходе вместо
рассматривается
(обозначаемый через
которое должно быть использовано,
бы не было шума (т. е. число элементов в
неизбыточной системе), а N
число элементов, которое
на
самом
деле используется
(т. е. число элементов
число
элементов,
если
в избыточной
Вернемся
системе).
теперь
к
используемой фон Нейманом
покомпонентной избыточности
в
вычислительных
непростыми системами связи),
чтобы сделать их более надежными (см. § 3.2). Мы
системах
(являющихся
ИСПРАВЛЕНИЕ ОШИБОК
120
что
видели,
=
1/Зя (т.
при
[ГЛ. 3
коэффициенте эффективности /?
=
е. каждая компонента заменяется на п
(2/г)-компонентный восстанавливающий
неправильной работы системы
компонент
плюс
орган)
вероятность
рп~ап-112.\0-Ьп,
где а и Ь
подходящие константы. Это выражение мы
можем переписать следующим
pn
где с и d
рис. 3.13.
=
образом:
dR4'.21-clR
(3.2.1)
Графически это изображено на
Нейману можно получить сколь
константы.
По
фон
малое
угодно
счет
рп
стремления
только
к
за
нулю
/?,
как
тогда
Шенноном для систем связи
величины
существование
установлено
кодов со сколь угодно
малым
всякий
раз, когда
означает, что
автоматов
по
избыточность
рп
/?0 и еа*'->0. Однако если аА>0, то при
*-> оо £а»'-> оо и в этом случае система нестабильна.
Если at и а2 комплексно-сопряженные, т. е. a + ib и
a
ib, тогда выражение Веа*'-\-Сеа2< может быть
приведено к виду
величины,
а
следовательно,
А + eat
его
значение
а4
и
а2
или
(D cos 6/ + F sin W);
стремится
к
положительное же значение а
А при /-^оо
и
а
где /= 1,
...,
п\ Хг и t/j
=
соответственно i-й вход и
bij(d/dt) некоторый
выход; a
х1>
дифференцирования
включающий
оператор
отмечает, что подобная
известных свойств.
система
/-й
многочлен,
по
/.
Грин
обладает рядом
хорошо
«...Если в произвольную точку такой системы
подать одиночный импульс, то, как хорошо известно, ее
ответная реакция будет суперпозицией нормальных
колебаний
(normal modes),
или
распределением
каждая из которых имеет одну и ту же
всей
сети. Эти естественные, или
для
частоту
резонансные частоты могут быть выражены через параметры
реакций,
простых
системы
нормальное
коэффициенты
колебание
отношений
Ьц.
интенсивность
распределением
возбуждения в различных
другой, в то время как
интенсивности
точках одна относительно
абсолютная
Индивидуальное
характеризуется
в
целом
зависит
только
от
места
Нормальные
приложения и интенсивности входа.
колебания не влияют одно на другое в
том
возбуждение одного нормального колебания
ограничивается этим колебанием (не вызывает других
смысле,
что
нормальных колебаний). Любое стимулирование
может быть представлено в виде суммы синусоидальных
колебаний (быть может, затухающих или
нарастающих), и каждая из этих входных частот вызовет
возбуждение всех нормальных колебаний, причем
величина возбуждения зависит от частоты и точки
приложения
входного
сигнала.
возбуждения приближается
Если
к
частота
источника
частоте
резонанса,
амплитуда соответствующего нормального колебания
значительно
превышает амплитуды остальных
нормальных колебаний. Таким образом, к какой бы точке
приложить входное возбуждение, имеющее
близкую к частоте резонанса, в системе будут
преобладать колебания соответствующей частоты.
Итак, при резонансе выходы принимают большие знасистемы ни
частоту,
РЕЗОНАНСНЫЕ ЧАСТОТЫ В НЕРВНЫХ СЕТЯХ
§ 4.2]
чения, а распределение отношений ответов
но относительно положения
147
инвариант*
источника».
Грин
предлагает следующую модель нервной активоснованную на свойствах линейных систем.
«Предположим, что одной из задач сенсорных входов
является
возбуждение линейных систем. Конечно,
ности,
этим системам
предшествуют, за ними следуют и ими
управляют нелинейные системы, о которых мы не
станем делать никаких предположений. Например,
допустить, что входным сигналам соответствует по
закону рост активности в цепях дендритов,
которая, достигнув определенного значения, может
вызвать переход аксона из
невозбужденного состояния
можно
линейному
в
возбужденное. Однако
будем разбирать
подробно эту частную иллюстративную модель; наши
выводы всецело будут основываться на свойствах
линейных цепей. Мы будем считать, что как сенсорные,
мы
не
так и моторные системы являются линейными цепями.
Компонентами выходного вектора будем считать
уровни
возбуждения
сигналы
и
в
различных
точках
цепи;
эти
управляют
нервов и
мускулов, что в конечном счете определяет поведение
животного. Естественно предположить, что сенсорная
и моторная системы
построены таким образом, что
ряд важных для организма входных воздействий воз-1
буждают собственные колебания в нейронных сетях,
активностью
которые характеризуют наличие
признаков в
множества
необходимых
поступившей сенсорной информации. Это
в свою
необходимым условием возбуждения
очередь
нормальных колебаний в моторной системе.
является
возникающие в моторной системе, и определяют
конкретное поведение животного».
Не будем здесь углубляться в анализ частного
Колебания,
котором Грин демонстрирует возможность
различных стилей передвижения
«лошади» при помощи возбуждения нормальных
колебаний в простой нейронной сети. Ограничимся выводами,
примера,
на
моделирования
к которым он приходит, анализируя свою модель
«лошади».
«В заключение мне хотелось бы сделать кое-какие
выводы в отношении нашего гипотетического четверо-
КИБЕРНЕТИКА
148
[ГЛ. 4
ногого, подчеркнув, что эти замечания относятся в
основном к элементам, объединенным в системы.
Предположим, что мы обнаружили у себя в лаборатории
эту модель и, приняв ее за живую лошадь? решили
провести нейрофизиологические эксперименты,чтобы
выяснить особенности управления для всех четырех
стилей ее передвижения. Для каждого стиля мы ожи*
обнаружить систему нейронов,
обусловливающую работу четырех мускулов в заданном ритме. Для
одного из стилей нужно соединить ноги А и В;
обратная связь от В на С должна подавлять движения
последней, в то время как С через ряд синапсических
даем
или что-то в этом роде.
задержек подключена к Д
Затем мы станем разыскивать элемент,
осуществляющий переключения разных схем управления в
соответствии с нужным в данный момент стилем
передвижения.
Возможно, эти четыре системы не будут
полностью
физически независимы: изменение порогов
может позволить одной системе управлять более чем
одним стилем. Может оказаться очень трудным в
сложной системе проследить все структуры, регулировки и,
наконец,
пониманием
связать их с
но
поведением,
в
определенным
принципе это и было бы
функционирования нервной
Однако
внешним
полным
системы
животного.
добились
бы подробного уровня понимания, следуя
вышеупомянутым предположениям и воспользовавшись
обычными
даже в случае нашей модели мы не
приемами
Устанавливая
бы погребены
анализа
частные
под
реакций
грудами
нейронов.
отдельных
зависимости,
данных,
мы
оказадись
анализ
которых
вообще невозможен, либо должен длиться
бесконечно долго, хотя в действительности наша модель
состоит
из
единственной системы четырех
либо
нейронов
снабжена
и
ними
здесь
это
нет
не
четырьмя каналами связи между
четыре системы, с переключателем, и
связей, которые
можно
было бы принять
за
тормозящие, цепи задержки и т. д., исходя из
аналогий с внешними признаками, когда медленная походка
называется «шаг», более быстрая
«рысь», «галоп»
и т. д.».
РЕЗОНАНСНЫЕ ЧАСТОТЫ В НЕРВНЫХ СЕТЯХ
§ 4.2]
Прежде
сделать
после
о
выводов,
знакомства
Первый
что
том,
могли
это
является
принятие предположения
линейной цепью (на самом
характеристиками мозга, тем
нелинейности)
но
,
что
согласие,
явления
Выбор
животного.
в
их
резонанса
в
мозгу
формировании
Грином линейной цепи
могут играть значительную роль
поведения
необходимо
возникнуть
не
подробней мы знакомимся с
бесспорней убеждаемся
чем
деле,
раздел,
которые
работой Грина.
с
вывод
мозг
этот
окончить
чем
пару
149
в
диктовался
математические
необходимостью упростить
выкладки при выводе зависимостей для
частот
*).
резонанса
вывод крайне важен, и к нему приводит
последняя цитата. А именно: как бы ни был
объективен физиолог или психолог, выбор им эксперимента
Второй
и
экспериментальной
какой-то
гипотезой,
всегда
методики
или
определяется
или
просто
интуицией. Если модель никуда не годится, время будет
убито на эксперименты, которые либо вообще не дадут
почти никакой информации, либо полученные
результаты
будут
наверняка
Математические модели
действительности,
могут
как
и
моделью,
неверно
истолкованы.
так же не соответствовать
нематематические.
Бесспорным
первых является то, что они часто
позволяют количественно и качественно предсказывать
поведение системы, а поэтому могут быть легче
достоинством
подвергнуты
нематематические
более
строгой проверке,
Но одно
чем
только
жонглирование
формулами не придает теории магической силы, поэтому
всегда следует опасаться дефектов в наших прежних
моделях, а также ложных идей, ведущих к появлению
модели.
моделей,
новых
математических
или
же
нематематических.
*) Читателя, который заинтересуется резонансными
отослать к статьям:
R. L. В е и г 1 е,
of cells capable of regenerating pulses, Phil. Trans.
Roy Soc, London, Sen B, 240 (1956) 55. B. G. Farley, Selforganizing models for learned perception, in «Self-organizing
systems», Pergamon Press, New York, 1960. [Русский перевод: Ф э pнервными
Properties
сетями,
of
a
можно
mass
л^ Б. Г., Самоорганизующиеся модели для обучения восприятию.
В сб. «Самоорганизующиеся системы», Изд-во «Мир», 1964.]
[ГЛ. 4
КИБЕРНЕТИКА
150
§ 4.3. Протезирование
и гомеостазис
Исследования роли обратной
связи
в
нервной
системе человека начинают оказывать заметное влияние
на
конструирование протезов.
Старейший
вид протеза
«деревянная нога»
единственную функцию утраченной
конечности
поддерживание тела. Современные протезы
конечностей, как, например, протез руки, который
позволяет
брать предметы и производить некоторые
манипуляции с ними, возвращают своему обладателю
уже несколько степеней свободы. Но мы видели в
§ 4.1, что для полноценного управления конечностями
выполнял
кинестетическое
уделяется
обратная связь (так называемое,
ощущение). В настоящее время
важна
чрезвычайно
много
исполь*
созданию протезов,
вроде кинестетического ощущения,
например протезы руки, в которых на кончиках пальцев
внимания
нечто
зующих
помещаются
датчики
давления,
от
которых подводится
В конце 1961 г. стало
с
протезов
используются
обратной
к коже
электрический сигнал
уцелевшей части руки.
известно,
связью
что
35
около
изготовлены
таких
и
Советском Союзе*). Дальнейшие усилия
в
в
СССР, так и в США,
потребуют проведения ряда нейрофизиологических
этом
направлении
исследований
как в
особенностей
стыковки
кинестетических
обратной связи и нервной системы
того, потребуется соответствующий
помогающий изготоЁлению этих
цепей
«в
человека.
цепей
Кроме
анализ,
металле».
Существует также ряд физиологических процессов,
значительной мере использующих принцип обратной
связи и независимых от собственно нервной системы.
Можно привести внушительное количество примеров,
в
когда обратная
*)
На
самом
связь не только
деле
такие
протезы
присутствует
были
в
изготовлены
физио*
в
раньше: Кобринский Д. Е., Брейдо М. Г., Гурфинкель В. С, Славуцкий Я. Л., Сысин А. Я, Полян Е. П., Цетлин М. Л., Якобсон Я. С,
Работы ЦНИИПП в области создания биоэлектрической системы
Советском
Союзе
намного
управления. Труды 7-й научной сессии Центр, научно-исслед.
полиграф, пром-сти, 1958, 125 132. (Прим. перев.)
ин-та
ПРОТЕЗИРОВАНИЕ И ГОМЕОСТАЗИС
§ 4.3]
151
процессе, но и имеет жизненно
гомеостазис. Говорят, что в
значение. Это
логическом
(физиологической)
системе
некоторого
отклонение
взаимодействуют
влияния
системы
образом,
большой
с
гомеостазис,
воздействия,
после
если
вызвавшего
от нормальных значений,
реагируют и
эффект постороннего
параметров
части
таким
в
встречались
ее
ряда
составные
имеется
внешнего
важное
что
степени
в
гомеостазисом
нейтрализуется. Мы
§ 3.1. Вот еще два
примера,
которые должны пояснить это определение.
а) Когда человеку холодно, соответствующие
воздействуют на определенный механизм мозга,
сигналы
действие которого вызывает дрожь. В результате
работы мускулов выделяется тепло, которое препятствует
охлаждению.
б) Внезапное кровотечение вызывает резкое
падение кровяного давления. Это влечет сужение просвета
артерий, что в свою очередь уменьшает величину
падения давления.
До какой степени математическая теория обратной
связи
углубит
наше
понимание
механизма
гомеоста-
вопрос будущего, но бесспорно, что.понятие
связи служит серьезным подспорьем в этом
зиса
обратной
вопросе*).
Гомеостазис проявляется
и
в
процессах
Шведский ученый Ларе Лёфгрен (Lars
Lofgren) теоретически исследовал сеть из логических
самовосстановления.
на наши абстрактные нейроны,
способностью
обладающую
обнаруживать и заменять
элементов,
похожих
неисправные элементы**).
*) Ряд статей
на
эту
тему
помещен
в
«Homeostatic
Media-»
Brookhaven Symposia in Biology, № 10, Upton, N. Y., 1957.
**) Self-repair as the limit for automatic error-correction in
nisms»
Von Foerster and G. Zopf (eds.), «Proc. symp. on principles
of self-organization», Pergamon Press, New York (1962), 181 228.
[Русский перевод: Самовосстановление как предел для автоматической^коррекции ошибок. Сб. «Принципы самоорганизации», Издво «Мир», М., 1966] и «Kinematic and tesselation models of selfH.
repair» in «Biological prototypes and synthetic systems», Plenum
Pre'ss, N. Y. (1962), 342 369. [Русский Перевод помещен в сб.
«Проблемы бионики», Изд-во «Мир», 1965, стр. 475 517.]
[ГЛ. 4
КИБЕРНЕТИКА
152
Изложим выводы, к которым пришел Лёфгрен. Он
показал, что максимальная продолжительность жизни
полностью локализованного автомата (т. е. автомата,
чей
рост, если таковой наблюдается, должен быть
объемом)
ограничен постоянным
компонентов
достигается
в
том
из ненадежных
случае, когда
в
автомате
обнаружения ошибок. Далее
он
присутствует
с
ошибок
локализации
того,
рассмотрел вопрос
учетом
что сбои возможны в самой системе поиска ошибок,
система
и показал, что максимальная
продолжительность
такого полностью локализованного
автомата
жизни
конечна.
Эта величина пропорциональна квадрату срока службы
компонентов автомата. Таким образом нетрудно
видеть, что продолжительность жизни всего автомата
может значительно превышать срок службы
отдельных его компонентов.
В своей
второй
ной локализации.
самовосстанавливающийся
статье он снимает
Показано,
неполностью
ограничение
пол-»
что
локализованный
автомат
может
жизни,
-неограниченную
продолжительность
он обладает необходимыми возможностями роста
иметь
если
и
самовосстановления.
подобный
автомат
В этой интерпретации
включает в себя
самовоспроизводящиеся
подавтоматы. Приводятся вероятности возникновения
ошибок,
самовоспроизводящихся подавтогеометрическая форма всего автомата с
самовосстановлением в процессе его роста,
обеспечивающие бессмертие автомата.
сложность
матов и
Лёфгрен
подчеркивает,
что
конечное
время
жизни
самовосстанавливающихся полностью локализованных
автоматов
соответствует конечному времени жизни
любого растения или животного в природе.
Неограниченное время жизни самовосстанавливающегося нелокализованного автомата, развивающегося
безгранично, соответствует неограниченному времени
общества, рассматриваемого
как
Результаты Лёфгрена подтверждают мысль,
борьбе за жизненное пространство
что
существования
человеческого
нечто целое.
человечество в
должно
выйти
за
пределы Земли.
ОБРАЗЫ И ПОНЯТИЯ
§4.4]
§
4.4.
Образы
В этом
сами,
и понятия
параграфе
Как
когда
мы
будем
рассматривавшимися
«Кибернетики»,
«Как
каллока
видим
а также в
мы
иметь
его
в
профиль
или
Винером
в
его под углом
в
нам человека,
фас? Как
квадрат, независимо от того, мал он или
или близок? Как мы узнаем круг, даже
наблюдаем
с вопро*
VI главе
и У. Мак-
дело
работе У. Питтса
понятия...*)».
узнаем
узнаем черты знакомого
мы
153
мы
узнаем
велик, далек
если
в виде эллипса?
Важнейшим фактором при сравнении форм разных
предметов является зрительно-мускульная система
обратной связи. Иногда эта связь носит чисто гомеостатический
сокращение зрачка,
в узких
света
пре-
характер, например
интенсивность
поддерживающее
Когда в поле периферического зрения
попадает предмет, выделяющийся своей яркостью,
делах.
цветом
или
движением,
возникает
рефлекторный
сигнал
обратной
связи, вызывающий перемещение
изображения в центр поля зрения, т. е. в область сетчатки,
обладающую наибольшей чувствительностью к
форме
и
цвету.
Другими словами, человек стремится придать
предмету, привлекшему его внимание, стандартное
положение и ориентацию, чтобы зрительное впечатление,
возникающее от подобных предметов в мозгу,
менялось в минимально возможных
Однако
обратной связи
эта
система
пределах.
зрительно-мускульной
недостаточно полно объясняет наше
восприятие таких понятий, как стул, круг и т. п. Нам
по-прежнему приходится задавать себе вопрос, каким
образом мозг узнает, например, букву А независимо
от действия на нее ряда преобразований
поворотов,
сдвигов в поле зрения, изменения размера и т. д. Питтс
и Маккаллок
посвятили свою работу рассмотрению
возможных
нервных
механизмов,
действием которых
*) W. Н. Pitts and W. S. M с С u 1 1 о с k, How we know
universals
the perception of auditory and visual forms, Bull
Math. Biophys, 9 (1947), 124 147.
[ГЛ. 4
КИБЕРНЕТИКА
154
к
можно было бы объяснить способность мозга
Их конструкции
обнаруживают
ряд
аналогий, возможно, поверхностных, со структурами живого
мозга.
Займемся немного математикой. А поэтому вспо«
мним понятие группы.
Определение 4.4.1 *). Группой преобразований
восприятию.
называется
если
то
таких
АВ£ G (под АВ
полученное выполнением
преобразование,
Л;
совокупность G
Л, £6 G,
преобразований,
сначала
В,
заметим, что, в общем случае, АВФВА) и
а) тождественное преобразование /£ G
неизменным,
расстояние).
б)
=
I
то
(А'1
полностью
и
его
затем
(/
которое оставляет
например, смещение на нулевое
Если А £ G,
AA-l=A~lA
которого
а
где:
преобразование,
тривиальное
что
понимается
все
А'16 G,
инверсия
где
преобразование, результат
противоположен результату
преобразования А).
Заметим, что для преобразований
от
действия
автоматически
выполняется свойство ассоциативности:
(АВ) С
=
А
(ВС)
=
С,
после
которого следует В,
а
затем
Л.
и Маккаллок утверждают:
«...ряд сетей, объединенных в особые структуры
Питтс
нервной
системы,
информации
свойствами.
В зрительной сфере
эквивалентность
подобия
предназначен
для
классификации
в соответствии с полезными
эти
сети
общими
устанавливают
реализаций (apparitions)
за счет
и
конгруэнтности, сохраняющихся при
наблюдении одного и того же предмета из разных точек
пространства. В сфере слухового восприятия они
тембр и гамму звуков независимо от высоты
Эквивалентные реализации во всех случаях
обладают общей фигурой и определяют группу
преобразований, переводящих эти реализации одна в другую,
но сохраняющих фигуру неизменной. Так, например,
группа сдвигов переводит квадрат с одного места на
распознают
квадрата остается неизменной.
«геометрическими объектами»
фигура
другое, однако
являются
Картану и
(Wertheimer)
по
Вейлю
155
«образами»
Колеру (Kohler).
и
или
Вертхаймеру
по
Мы ищем общие принципы построения нервных
сетей, распознающих фигуры так, что для всех
реализаций одной и той же фигуры они выдают один и
тот же выход».
Итак, все,
отображается в виде
мы
что
видим
или
слышим,
своеобразной
картины из возбужденных
нейронов в коре головного мозга М. Распределение
возбуждения в М описывается функцией ф(л;, /), где
ф(л;, t) l, если нейрон, находящийся в точке л:,
возбужден в момент /, иф(х, /)=0в противном случае.
=
Пусть G
переводит
группа преобразований, которая
функции ф(л:, /),
описывающие реализации,
некоторой фигуры, в
функции. Пусть G имеет N элементов.
возникающие при предъявлении
эквивалентные им
Питтс
и Маккаллок рассматривают случай, когда
преобразования Т из G могут быть порождены
преобразованиями Т основного множества М *), так что
Ту(х)
Например,
если
G
=
то
Ц)(х-{-ат),
постоянный вектор, зависящий только от Т.
где ат
G
=q>(aTx),
число,
Все
Т
(р(Тх).
группа сдвигов,
Ту(х)
Если
=
изменений
группа
масштаба,
положительное
ат
зависящее только от Т.
где
то
подобные преобразования линейны,
(аф(х) + bW (х))
=
аф
7\p(#)
=
действительное
то есть
(Тх) + bW (Тх)
^=аТ^(х) + ЬТ^(х).
=
Простейший способ получения инвариантов
данного распределения ф(л;, /) возбуждения заключается
в том, чтобы
усреднить группу G. Так, пусть f
*) Там, где это
опускать переменную /
не
вызовет
и записывать
двусмысленности,
ф(х, t)
как
ф(*).
мы
будем
КИБЕРНЕТИКА
156
[ГЛ. 4
произвольный функционал (т. е. функция от функции),
ставящий в соответствие каждой функции ф(л;, /)
некоторое число. Осуществляем поочередно все
преобразования Тср(х, /), вычисляем f(Tcp) и
усредняем
результаты по
G. Имеем
по всем
T£G
Если мы начнем с
1- v
по
Sq(S£ G)
f(TSq)=-L
у;
всем
по
T£G
R£G
поскольку G
вместо ф, то
получим
nm=a.
всем
таким, что
RS~l£Q
группа. Чтобы полностью
по G
(т. е. понятие, соответствующее той реализации,
которая вызывает возбуждение нейронов ф(л;,/)), нам
нужен полный набор таких значений а для разных
функционалов f (один функционал, например,
характеризует «округлость», другой
«прямоугольность» и
т. п.). Функционалы можно отличить один от другого,
приписав им индексы £, принимающие значения из
некоторого множества S. Таким образом, мы получим
различные усредненные значения
характеризовать
фигуру, соответствующую функции ф(л\ /)
Ы£т). Если система нейронов не нуждается в
полной информации для правильного распознавания
очертаний, то множество S может оказаться
значительно меньше М, иметь меньше измерений и вообще
ее
также
один
выродиться
в
изолированные точки.
Время
некоторые из Xj, описывающие положение в
служить
координатами
в
S.
t и
М, могут
ОБРАЗЫ И ПОНЯТИЯ
§4.4]
157
Пусть S многомерно. Тогда простейшая нервная
сеть, реализующая описанный выше формальный
процесс, может быть получена следующим способом.
Повторим
М
множество
исходное
N
в
1
слоях,
6 G
слой MTl затем подключим их
к М или к его сенсорным путям таким образом, чтобы
при наличии в М функции возбуждения ). Результаты
значение
суммируются, поступая
точке g мозаики S.
g
нейронов
сетью
и
каждого
для
вычислений
Мт
всех
от
нейрон, находящийся
на
Мт
вычисляется
в
если мы будем действовать подобным образом,
потребуется неправдоподобно много нейронов.
Но
нам
Все
Мг в совокупности имеют
раз большую, чем М, и во столько же раз
больше степеней свободы, чем в группе G. Еще более
множества
в
размерность
важно
N
нейронов
число
связей, которые необходимы
и
для вычисления значений
fi(Tq>),
7\р и
принципе, от всего распределения
отдельного вычислителя для
Г6 G. Особенно
fi
вычисления
соединений
это
в
поэтому
отдельно
Мт:
от
случае растет еще
этом
и
каждого
схема
если
в
в
требующих
g
каждого
сказывается,
выполнена
зависящих
для
количество
большей
степени.
Можно
Пусть
Мт
ранее,
но
повысим
они
не
могли
остаются
их
сами
дополнительные
в
разветвляющиеся
Мт таким образом, чтобы при
компенсировалось действие
на Мт могла бы снова возникнуть
и
порогов,
их
Ту(х).
картина
Свяжем
координату
нейроном
волокна
каждого
возбуждении
повышенных
и
пороги до такой величины, чтобы
по себе возбуждаться от своих
нервные
управляющие
как
соединенными,
специфических афферентов. Введем
пределах
модель.
существенно упростить эту
слои
х,
х
все
во
нейроны,
всех
находящимся
также
является
аксон
может
N
имеющие
слоях
в
копией
возбудить
Мт>
одну
скажем,
этот
ту же
с
который
Q. Пусть любой
специальном
М,
и
аксонами
слое,
нейрон. Если
дополни*
[ГЛ. 4
КИБЕРНЕТИКА
158
управляющие нервные волокна, введенные
выше, последовательно возбуждать так, чтобы
выдавался каждый слой Мт> причем только один слой в
тельные
Неспецифищние\ т~~^
и ассоциативные
афферентные
'
'
"
'
'
Специфические афферентные пути
*
пУти
*
Ассоциативные афферентные пути
Рис. 4.3. Входная информация поступает по
афферентным путям (отмечено знаком +)
до уровня
в
импульсам
данный
момент
последовательно
и
рецептивном поле, активированном
неспецифическими афферентами. Это
момент
специальным
проходит
в
данный
позволяет
в один слой.
поступать только
времени,
возникать
все
Q будут
преобразования Гф функции
то на
слое
) будут
получены последовательно согласно сигналу
сканирования, вызывающему периодическое проектирование
на
Q картин Гф. Эти
накапливаться в течение
любым способом.
значения
цикла
на
/$(7Vp)
конечном
могут
S-нейроне g
НЕКОТОРЫЕ ДРУГИЕ НАПРАВЛЕНИЯ
§ 4.5]
Описанное
использование
бы
общего
назвать
устройство
полезного
обменом
159
иллюстрирует
приема,
времени
который можно
оборудование.
было
на
переходя от параллельного выполнения
последовательному, мы, экономя на
оборудовании, расплачиваемся соответствующим
Другими словами,
операций
к
быстродействия.
Насколько мне известно, до сих пор нельзя дока*
зать нейрофизиологическими
приемами соответствие
рассмотренной модели механизмам человеческого
снижением
мозга. Тем не менее внешнее сходство настолько
что, по словам Винера, когда нейрофизиолог
фон Бонин увидел схему, подобную нашей (рис. 4.3),
велико,
он спросил: «Не схема ли это четвертого
тельной области коры головного мозга?»
слоя
зри*
§ 4.5. Некоторые другие направления
В
параграфе вкратце изложены вопросы в
сферы кибернетической психологии, касаю*
щиеся «разумных машин», которых мы в подробно*
стях рассматривать не будем.
этом
основном
из
В 1958 1959 гг. трое американских ученых
встретились в Центре современных исследований в области
наук о поведении (Center for Advanced Study in the
Behavioral Sciencies) и задумались над вопросом:
«Имеет ли отношение кибернетика к психологии?».
Заинтересованный читатель сможет найти прекрасно
аргументированный утвердительный
ответ
в
книге:
G. A. Miller, Е. Gal ante г and К. Н. Pribram,
Plans and the structure of behavior, Publ. by Holt, Ri«
nehart and Winston, Inc., 1960).
Их работа в области «искусственного интеллекта»
они занимались програм*
плодотворной
мированием на ЦВМ процессов поиска решения задач.
По этому вопросу читателю будет полезно ознако*
миться с обзорной статьей: М. L. М i n s к у, Steps to-»
ward artifical intelligence, Proc. IRE, 49, № 1 (1961),
8-30.
В кибернетической психологии фундаментальное
понятие обратной связи используется в двух смыслах:
была весьма
[ГЛ. 4
КИБЕРНЕТИКА
160
а)
б)
буквальном
в
как
смысле
в
следящих
в
системах,
переносном смысле
подразумевая
связь между
науками о мозге и машинах
в
виду обратная связь между психологией
и
интеллектом).
искусственным
Те,
обратную
(имеется
интересуется буквальным смыслом этого
термина, могут обратиться к упоминавшейся выше
книге. Мы же коротко обсудим обратную связь между
изучением мозга и вычислительных машин. Это могло
кто
форму беседы
бы вылиться в
и
Питтса,
но здесь
использовании
мы
психологические теории.
обсуждение гипотезы
типа
в
человеческое
как
и
на
автоматов
объяснить различные
Тьюринга (см.
§ 1.6) показали, что
вычислительных
машинами,
внимание
Работы
Тьюринга
теми
наше
машин
вычислительных
как
Маккаллока
мозга
сосредоточим
с тем, чтобы с их помощью
устройства
нейрофизиологии,
по
модели
рассмотрении
при
на
удобно
которых
поведение.
являются
машин
Заметим,
что
как
раз
моделировать
в задачу
буквальное моделирование (мы не
от
машины, играющей в шахматы,
будем требовать
чтобы она имела пальцы); они предназначены для
машины
не
входит
имитации
данное
тех
время
аспектов
мы
хотим
поведения,
на
сосредоточить
которых
в
внимание.
Так,
психолог-теоретик, следуя рассматриваемому
принципу обратной связи, может воплотить свои
программу для вычислительной машины,
в
предположения
которая
будет
в
занесена
«память».
ее
При
«стимула», она, как и живой
организм, «отреагирует» на него, действуя в строгом
соответствии с заложенной в нее программой.
Следует различать при этом так называемый
«искусственный интеллект» и «моделирование». Первый
предъявлении
машине
входного
термин подразумевает, что
любым способом, а второй
действия
человека
Минский
в
машина
что
решает задачу
копирует
машина
подобной ситуации. На
этот
счет
отмечает:
бесспорным,
по
крайней мере, в
будет наблюдаться
плодотворное содружество наук, изучающих поведение
«...кажется
течение
что,
ближайших нескольких лет
человека
и
попыток
повысить
«интеллектуальность»
НЕКОТОРЫЕ ДРУГИЕ НАПРАВЛЕНИЯ
§ 4.5]
161
машин.
Но в перспективе мы должны быть готовы
к тому, что возникнут более эффективные приемы
программирования, и необходимость в копировании
поведения человека отпадет».
Но что касается психолога, то он бесспорно
заинтересован в том, чтобы промоделировать поведение
в
игрока
или
шахматы
но
специалиста-логика,
совсем
чтобы заменить их машиной, или создать
что-либо более совершенное. Для иллюстрации
упомянем вкратце о двух программах для ЦВМ,
относящихся к области «искусственного интеллекта».
1) Г. Гелернтер и Н. Рочестер*) составили
не
в
том,
программу для доказательства на ЦВМ теорем
планиметрии путем применения заданных правил вывода
к данной совокупности аксиом. Так же, как и
учащийся, машина рассматривала чертежи. Для
повышения
надежности
несколько
фигур,
заключения
несущественных
позволяло
случайного совпадения
Рассмотрение чертежей
упростило процесс
2) А. Л. Сэмюэль**)
своим
случае анализировалось
избежать неверного
каждом
что
из-за
свойств.
степени
в
поиска
громадной
в
доказательства.
подводит
следующий
итог
исследованиям.
«Довольно
детально
были
рассмотрены
две
программы по
Проделанной
обучению машины игре в шашки.
работы достаточно для подтверждения
возможности
составления
которой
машина
такой
программы
для
ЦВМ,
будет
играть в шашки лучше
составителя программы. Более того, она сможет
сделать это в исключительно короткий период времени
(8 10 часов машинной игры), будучи снабжена лишь
по
правилами игры, «ощущением» направления, а также
и неполным перечнем параметров,
как
предполагается, имеют какое-то
которые,
но
значение,
правильные знаки и относительные веса
приблизительным
*) Н. Gelernter and N. Rochster, Intelligent
behavior in problem-solving machines, IBM J. Res. Develop. 2, № 3
(1958), 336 345.
**) A. L. Samue 1, Some studies in machine learning, using
the game of checkers, IBM J. Res. Develop. 3, № 3 (1959), 211
229.
КИБЕРНЕТИКА
162
Принципы обучения
неизвестны.
которых
(ГЛ.
подтвержденные
этими
применимы и ко
Восстановим
многим
экспериментами,
4
машины,
бесспорно,
*).
другим ситуациям
содержание этой главы и
укажем на ряд вопросов, заслуживающих внимания
при дальнейших исследованиях. Мы убедились в
исключительной важности понятия обратной связи и в
том,
оно
как
заболеваний,
позволяет
в
памяти
помогает
явлении
в
разобраться
в
гомеостазиса,
совершенствовать протезы. Все
ряде нервных
а
также
области
эти
исследований.
Мы убедились в необходимости более сложных
моделей нервных сетей для сложных систем с обратными
требуют
применения
еще
связями
и для
длительных
частотного
кодирования сенсорной
известно, что зрительно-мускульная
информации.
обратная связь играет существенную роль при
Нам
узнавании
видимых
обратная
связь
форм,
известно,
каким
быть воплощена
может
в
образом
нервной
эта
Тем не менее нам еще очень далеко до
нервных процессов, лежащих в основе нашего
восприятия понятий. Исследование механизмов обратной
системе.
понимания
связи
в
психологическом
аспекте
и
с
связанное
этим
мастерство составления программ «искусственного
интеллекта», по-прежнему являются источником многих
исследовательских
Мы
в
работ.
состоянии
чительно
интересных
лишь
теория клеточных автоматов
генетические
Чомского
основательнее
коды
упомянуть
проблемах,
как,
(molecular
таких
исклк>
например,
automata
математическая
и
theory),
лингвистика
(Chomsky). Читателю, желающему
с работами в этой области,
познакомиться
можно рекомендовать просмотреть
журналы: The Bulletin of Mathematical
Information
о
and
Control,
Journal
of
следующие
Biophysics,
the
Association
for
Computing Machinery, Journal of Theoretical Biology,
Cybernetik, а также труды специализированных
секций IRE (IEEE) по электронным вычислительным
машинам, теории информации и т. п. Механизмам дей-
шахматы,
*) См. также М. М. Ботвинник, Алгоритм игры
Изд-во «Наука», 1968. (Прим. перев.)
в
НЕКОТОРЫЕ ДРУГИЕ НАПРАВЛЕНИЯ
§ 4.5]
163
связи внутри живой клетки посвящена
B.C. Goodwin, Temporal organisation in
cells, Academic Press, Inc., London, 1963*).
Мы подходим к концу этой главы с пониманием
ствия
обратной
книга
того, что
перед
увлекательных
важными из них в
будут работы
кибернетикой еще неисчерпаемое море
проблем. Быть может, наиболее
области психологии и физиологии
по
установлению функций
подсистем, которые и
составляют в совокупности нервную систему человека,
пока мы имеем весьма смутное представление.
координирования
и
связи
*) Из
множества
о чем
отечественных журналов мы посоветуем читателю
«Биофизика», «Кибернетика», «Техническая кибернетика»,
«Проблемы передачи информации», «Автоматика и
телемеханика» и периодический
сборник «Проблемы кибернетики». (Приди
ред.)
журналы
Глава
5
Теорема Гёделя
этой, нашей последней
В
свое
о неполноте
внимание
всего
прежде
мы
главе
на
сосредоточим
основаниях
*). В § 5.1 мы дадим краткий исторический обзор
формального подхода к основаниям математики; там
математики
же покажем, почему теорема
опровергает всю программу
Гёделя
формалистов;
полностью
в
§ 5.2 вернемся
рассмотрению рекурсивных множеств, которые
изучались в первой главе; в § 5.3 обсудим некоторые
общие свойства рекурсивных логических систем
(рекурсивных логик). В § 5.4 мы ограничимся так
к
называемыми
позволят нам
неполноте.
книги
и
извлечь
«Имеет
арифметическими логиками, которые
(в § 5.5) доказать теорему Гёделя о
Наконец, мы вернемся к главной теме этой
обсудим философский спор о том, что можно
из
Гёделя
теоремы
для
решения
вопроса:
перед
машиной?».
Я включил в эту книгу доказательство теоремы
Гёделя главным образом по следующим трем
ли
мозг
преимущества
существенные
причинам:
1) На
возможностях
нее
часто
человека
2) Это
и
ссылаются
при споре
о
машины.
очень важная
теорема для оснований
математики.
3) Я полагаю, что доказательство, данное в этой
книге, достаточно короткое и простое для того, чтобы
с его помощью можно было опровергнуть миф (су*)
В качестве полного
и
очень
интересного
введения
в
этот
Nagel and J. R. Newman, Godel's proff, New
York Univ. Press, 1958. Для радикального изучения всех
предмет
см.
Е.
технических подробностей см.
Е.
W.
Beth,
The Foundations of
mathematics, North Holland Publishing Co., Amsterdam,
1959.
ОСНОВАНИЯ МАТЕМАТИКИ
§51]
часть
щественную
фольклора)
165
математического
современного
теоремы Гёделя
доступно только
о том, что доказательство
является настолько
что оно
трудным,
специалистам по математической логике.
§5.1. Основания
математики
Кант утверждал, что
геометрии априорно заданы
аксиомы
евклидовой
интуиции. Это
утверждение было в духе определения аксиомы как
очевидной истины, определения, которое не вызывало
никаких сомнений на протяжении 2000 лет.
Эта
позиция
была
человеческой
поколеблена
в
девятнадцатом
благодаря работам Больяи, Лобачевского
веке
Ри-
и
Они постулировали геометрические системы,
которые не были евклидовыми, более точно, системы,
которые отвергали истинность следующей аксиомы
мана.
Евклида: «Если даны прямая и точка, не лежащая
ней, то существует только одна прямая, которая
на
проходит через данную точку параллельно данной
прямой».. И мы с вами живем в такое время, когда
общепринятые взгляды на Вселенную опираются на теорию
относительности
Эйнштейна,
а
она
имеет
дело
с
пространством, геометрия которого лучше описывается
неевклидовой римановой схемой, в которой
параллельных линий просто не существует.
Другими словами, наши современные взгляды не
противоречат взглядам Канта, что аксиомы
только
Евклида даны a priori человеческой интуиции, более
того, они утверждают, что одна из аксиом Евклида,
так называемая аксиома о параллельных, в
действительности неверно описывает Вселенную. В настоящее
время
достаточно
мы
полагаем,
точно
в нашей
геометрия Евклида
пространственные отношения
что
описывает
повседневной жизни,
но
не
космическое
пространство Вселенной. Теперь у нас может возникнуть
искренний и важный вопрос, от которого точка зрения
Канта позволяла легко отделаться: «Откуда
мы
знаем, что евклидова
свободна
от
геометрия непротиворечива
противоречий)?»
(т.
е.
[ГЛ, 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
166
будто
Как
бы для того, чтобы еще более усугубить
вопроса, Риман показал, что если
важность этого
евклидова геометрия непротиворечива, то и его (Римана) неевклидова геометрия также непротиворечива.
Вот прекрасный пример противоречия:
не
только
перестает
непротиворечивость евклидовой
геометрии
быть a priori очевидной, но оказывается, что она
влечет непротиворечивость соперничающей с ней системы!
Из этого можно сделать вывод, что тот, кто
занимается
аксиоматическими
вопрос об
их
системами,
как бы явно «истинно» система
«реальный
должен
ставить
независимо
непротиворечивости
от
того,
не описывала
мир».
Между
развитие теории множеств показало,
непротиворечивость системы нельзя установить
просто при помощи общих рассуждений. В самом деле,
тем
что
теория множеств, развитая
совершено
Кантором,
казалась
Рассел,
до тех пор, пока
непротиворечивой
а
за
другие, не показали, что эта, казавшаяся такой
«надежной» система содержит парадокс, к которому
можно прийти следующим образом. Рассмотрим
ним и
множество
и,
математиков
следовательно,
оно
это
не
является
множество
не
математиком,
является
своим
А теперь рассмотрим
множество всех вещей, о которых говорится в этой главе.
Здесь, кроме всего прочего, говорится о множестве
всех вещей, о которых говорится в настоящей главе,
собственным
элементом.
и следовательно, оно является элементом
Определим
множеств,
множество
которые
не
N
являются
своим
образом, М принадлежит N
когда М не принадлежит М.
Поэтому
а
множество
множество
всех
самого
себя.
как множество всех тех
элементом.
тогда
и
только
Таким
тогда,
принадлежит N,
которых говорится в этой
математиков
вещей,
о
главе, не принадлежит ЛЛ
А само N принадлежит N? Согласно данному выше
определению N принадлежит N тогда и только тогда,
когда N не принадлежит ЛЛ
Парадокс! И следовательно, наивная теория
множеств является противоречивой. Рассел устранил та*
кие
парадоксы введя
свою
теорию типов,
но нам важ-
ОСНОВАНИЯ МАТЕМАТИКИ
§5.1]
167
но здесь подчеркнуть, что непротиворечивость не яв«
ляется очевидным свойством логической системы.
Риман показал, что его геометрия непротиворечива,
непротиворечива евклидова геометрия, а
показал, что евклидова геометрия
непротиворечива, если непротиворечива арифметика, т. е.
если
Гильберт
элементарная теория
положительных целых
чисел*).
Логическую
систему можно рассматривать как не*
которую совокупность аксиом, из которых можно по-»
лучать теоремы повторным применением
определенного числа правил вывода. Представители формальной
школы, основанной Гильбертом, полагали, что при
поисках доказательства непротиворечивости они могут
полностью игнорировать все вопросы об истинности и
смысле теорем и аксиом, а вместо этого могут
рассматривать аксиомы просто как строчки символов, а
как способы получения новых строчек.
правила вывода
Более того, они решили потребовать, чтобы правила
вывода были финитными и полностью
детерминированными, т. е. в некоторой степени были похожи на
работу
первой
машин
главе.
Мы
Тьюринга,
которые
назовем
логические
мы
изучали
в
системы,
удовлетворяющие таким условиям, рекурсивными логиками.
Если мы хотим использовать рекурсивную логику для
описания теории положительных целых чисел, то мы
должны снабдить ее символами, которые бы
соответствовали основным
количественным понятиям
элементарной теории чисел.
Для доказательства
непротиворечивости
арифметическую логику, которая была
бы полной, т. е. такую, в которой можно было бы
вывести (как теоремы) все истинные утверждения о
целых числах. Кроме того, они требовали, чтобы
формалисты искали
непротиворечивость системы была показана надежным,
полностью детерминированным, «финитным» способом.
*) Разъяснение понятия «элементарная теория» и
факты об элементарных теориях можно найти, например,
многие
в
обзоре: Ю. Л. Ершов, И. А. Лавров, А. Д. Т а и м а н о в,
М. А. Тайцлин, Элементарные теории, Успехи матем. наук,
т. 20 вып. 4, 1965, стр. 37 108. (Прим. ред.)
Эта программа
теоремой Гёделя
в его
неразрешимости
[ГЛ. 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
168
формалистов
о неполноте,
знаменитой
работе
подобных систем*).
Теорема утверждает,
о
была разрушена
сформулированной
формальной
впервые
что
любая адекватная
непротиворечивая арифметическая логика неполна, т. е. что
существует истинное утверждение о целых числах,
которое нельзя доказать в такой логике. Этот важный
результат (который мы вскоре докажем) показывает,
что поиски формалистами полной непротиворечивой
арифметической
На
самом
деле
были
логики
Гёдель
обречены
показал даже
на
больше,
неудачу.
а
именно, что невозможно доказать непротиворечивость
арифметической логики (пусть даже неполной) теми
методами, которые выразимы в самой этойлогике.
Впоследствии Генцен (Gentzen)
доказал, что
чисел
элементарная теория
непротиворечива, но при этом
он использовал «ео-индукцию», которая является
бесконечным
индукции,
так
как
обобщением обычной математической
не удовлетворяющий формалистов,
метод,
он
не
является
«финитным». На сегодняшний
день положение с поисками доказательства
арифметики следующее. Гёдель показал,
существует финитного доказательства,
непротиворечивости
что не
арифметике; Генцен дал доказательство,
но при этом он пользовался такими методами, что это
доказательство можно рассматривать как
неудовлетворительное (недостоверное); и, наконец, вопрос о
том, существует ли доказательство
выразимого в самой
непротиворечивости,
тем
которое,
не
менее
хотя
и
не
«финитно»,
выразимо
остается
в
арифметике,
но
открытым.
§ 5.2. Некоторые факты
из теории рекурсивных функций
Мое изложение логики и теоремы Гёделя в §§ 5.3
5.5 во многом носит нестрогий, неформальный
характер. Строгое формальное изложение этих вопросов
*) Kurt G б d е 1, Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme, I (часть II не была
опубликована), Monats Math. Phys.
38
(1931), 173 198,
ТЕОРИЯ РЕКУРСИВНЫХ ФУНКЦИЙ"
§5.21
можно найти в гл. 8 книги
169
Мартина Дэвиса*). Кроме
того, я старался подражать превосходному стилю
ясной статьи Э. Поста**). Позвольте мне повторить
мною
сделанное
явление,
в
за*
§ 1.6. Мои рассуждения
строги, за исключением следующего:
интуитивно ясно, что данная процедура
эффективна, то я буду считать, что существует
соответствующая машина Тьюринга. Замечу, что во всех таких слу*
имеются
чаях
строгие доказательства, например, в
книге М. Дэвиса. Приняв это соглашение, мы ввели
следующие определения на языке наших эффективных
будут
вполне
если
процедур.
Определение
рекурсивной,
1.6.1.
Функция
называется
существует эффективная процедура для
ее вычислений.
Определение 1.6.2. Множество называется
рекурсивным, если существует эффективная процедура
если
для выяснения того, принадлежит или не принадлежит
произвольный элемент к этому множеству.
Определение 1.6.3. Множество называется
рекурсивно перечислимым, если
существует эффективная
процедура для последовательного порождения
(перечисления) его элементов.
Если мне потребуется убедить Вас в том, что
существует программа для выполнения определенных
вычислений (сколь угодно длинная и работающая
достаточно
долго), то я просто представлю Вам блок*
схему вычислений, а не программу на языке машины.
Ниже мы останавливаемся только на существенных
вопросах
которых
опуская
могло
детали, подробное рассмотрение
бы
затемнить
основное
содержание.
Мы доказали три теоремы о рекурсивных
перечислимых множествах.
Теорема 1.6.1. Если R и S рекурсивно
и
рекурсивно
перечислимые
множества,
множества RUS
и
то
рекурсивно перечислимы
R(]S.
*) М. Davis, Computability and unsolvability, McGraw-Hill
Book Company, Inc., New York, 1958
**) E. Post, Recursively enumerable Sets and their decisions
problems, Bull. Amer. Math. Soc. 50, № 5 (1944), 284 316.
[ГЛ. 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
170
Теорема 1.6.2. Множество
положительных
целых
S рекурсивно тогда и только тогда, когда S и S
рекурсивно перечислимы.
Теорема 1.6.3. Существует рекурсивно перечислимое, но не рекурсивное множество положительных
чисел
целых
чисел.
Последняя теорема
по существу является
теоремы Гёделя. Большая работа, которая
проделывается в двух последующих параграфах,
заключается в том, чтобы определить и разъяснить
абстрактной
формой
адекватной со-непротиворечивой арифметической
понятие
логики.
Гёделя
После
о
этого
воречивая
«Каждая
арифметическая
§ 5.3. Рекурсивные
Теперь
легко доказывается
уже
неполноте:
мы
теорема
адекватная со-непроти-
логика
неполна».
логики
сформулируем
в очень
общем
требования, предъявляемые формалистами
виде
к логике.
всего, у нас должен быть алфавит а0, аи а2,
терминах которого мы могли бы записывать
Прежде
в
утверждения
нашей
Конечная
логики.
...,
последовательность
будет называться «словом»*).
приписывания (справа) к слову X слова
этих символов
Результат
записывать
Y
Под высказыванием мы понимаем некоторое
утверждение, которое является либо истинным, либо
ным.
Предикатом
называется
несколько символов
элементы
лож*
выражение, содержащее
которое становится
(переменных),
если
высказыванием,
подставить
будем
XY.
вместо
некоторого
этих
символов
специального
множества.
Если
это
множеством
слов, то предикат называется словарным.
называется рекурсивным, если существует
Предикат
специальное
*) Отметим,
что
понятие
множество
«слово»
является
нас
у
эф-
употребляется
необычно. В нашей терминологии фразу Cogito ergo sum
можно рассматривать как слово, если алфавит имеет «пустую»
несколько
букву, означающую пропуск между
я мыслю, значит
Cogito ergo sum
положение
Декарта. (Прим. ред.)
словами.
я
(Прим. автора.)
существую
знаменитое
РЕКУРСИВНЫЕ ЛОГИКИ
§5.3]
фективная процедура,
позволяющая для каждого-вы*
из
полученного
узнать, истинно оно или ложно.
данного
оказывания,
Например,
174
высказывание
«х
предиката,
человек»
является
словарным предикатом, и если мы вместо х поставим
слово
«Джон», то получим истинное высказывание
человек». Если же вместо х поставить слово
«Джон
получится ложное высказывание «стул
В приведенном примере предикат является
одноместным; так как он содержит только одну
переменную.
мы
Для
рекурсивной логики
требуем, чтобы
была эффективная процедура, позволяющая по
любому слову сказать, является ли это слово аксиомой
«стул»,
то
человек».
или
нет,
требуем
и
существования
эффективной
которая позволяла бы узнать, можно ли
данному правилу вывода получить данное слово
других или нет*). Дадим точное определение.
Определение 5.3.1. Под рекурсивной логикой
процедуры,
по
из
L
мы
понимаем
называемых
рекурсивное
аксиомами
L,
и
множество
конечное
слов,
множество
словарных предикатов, называемых
вывода L (ни один из этих предикатов
рекурсивных
правилами
не
одноместным).
Если /?(У, Хи
Хп)
правило вывода L,
будем говорить, что Y непосредственно следует
Хп по правилу R.
Хи
является
...,
то
из
,
слов Хи Х2,..., Хт
если для любого
L,
(слова Хт)
/, l^Ci^m, либо Х{ является аксиомой, либо
k < i, что Х{ непосредственно
существуют такие /,
из
по одному из правил вывода
Xk
следует
Xh
Конечная
последовательность
называется выводом
в
...,
...,
L. Каждое Хи /=1,2,
т, называется
шагом вывода. Будем говорить, что W
теорема или
логики
W
доказуемо
...,
в
L,
и записывать
что
,
T(L): W,
*) Для сравнения различных способов гарантии такой
эффективности см. М. A. Arbib, Monogenic Normal Systems are
Universal, J. Australian Math. Soc. 3, № 3 (1963), 301 306.
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
172
[ГЛ. 5
если существует вывод W ъ L. Читатель найдет
пример такого вывода при доказательстве леммы 5.4.1
в
параграфе.
Обозначим через TL
следующем
множество всех теорем L.
Заметим, что каждая аксиома является теоремой L.
Теорема 5.3.1. Множество TL рекурсивно
перечислимо.
Доказательство. Укажем эффективный
метод
теорем. Так как множество аксиом
рекурсивно, мы можем их эффективно перенумеровать
А\, Л2, Л3,... Для каждого натурального п читатель
всех
порождения
может проверить, что выводы, которые имеют не
чем п шагов, и в которых использованы только
аксиомы
можно получить
более
{Ль Л2,..., Лп},
эффективно,
т.
перечислимое
е.
эти
выводы
множество.
образуют рекурсивно
Отсюда
легко
следует утверждение
теоремы.
Если мы
хотим в нашей логике говорить о
натуральных чисел Q, мы должны для
натурального п иметь эффективный способ
подмножестве
выписывания слова
Если
L
теоремой
говорить,
Описание
в
что
Q
Wn,
мы
означающего п
можем
точности
в
L
доказать,
имеется
называется
6Q.
Wn
n(iQ,
является
что
когда
тогда,
полным,
тогда,
когда
п
Wn
если
является
(£ Q*). Другими
полное описание
Q,
будем
Q.
то
полуполное описание
мы
также
я
выражение Wn, которое интерпретируется
можем доказать, что
каждого
оно
Q
(£
Q,
и
в точности
словами, L содержит
L для каждого
если в
установить, принадлежит
L
теоремой
имеем
п мы можем
Введем
или нет.
определение.
Определение
5.3.2. Логика L
полуполной для множества целых чисел
рекурсивно
W2,...
перечислимое
называется
Q,
если
множество
существует
слов
W0, Wu
такое, что
Q={n\T(L): Wn}.
*) Если Q
называют
имеет
перечислимым
полуполное
в L. Если
описание
в
L,
то
его
часто
Q имеет полное описание
то оно называется разрешимым в L.
(Прим. ред.)
в
I,
РЕКУРСИВНЫЕ ЛОГИКИ
§5.3]
Q,
L называется полной для
Q.
Теорема 5.3.2. Если L
рекурсивно перечислимо.
Доказательство.
для Q
173
если
она
полуполная
и
полуполная для
Q
=
Q,
то
Q
{n\TLn{W0,Wu W2y...}}
является
пересечением двух рекурсивно перечислимых
множеств и, следовательно, согласно теореме 1.6.1,
рекурсивно перечислимо.
Вспомнив теорему 1.6.2, получаем
Следствие 5.3.3. Если Q рекурсивно перечислимое,
но не рекурсивное множество, то никакая рекурсивная
логика не может быть полной для Q.
От этого следствия до теоремы Гёделя совсем
недалеко. Для этого надо средствами некоторой
рекурсивной логики развить теорию целых чисел, причем
так, чтобы принадлежность чисел данному множеству
можно было трактовать адекватно (т. е. число п
принадлежит Q тогда и только тогда, когда некоторое
эффективно сопоставленное ему слово выводимо в L).
Это возможно только тогда, когда Q по крайней мере
рекурсивно перечислимо. Следовательно, множества,
не являющиеся рекурсивно перечислимыми, в лучшем
случае могут быть представлены в рекурсивной
логике неполно.
Чтобы объяснить интерес лиц, занимающихся
автоматов, к множествам, которые не являются
рекурсивно перечислимыми, оставим на минуту
теорему Гёделя и обсудим проблему останова машин
теорией
Тьюринга. Напомним (см. § 1.5),
установим
машину
Тьюринга
Я,
ее ленте запишем
и
записывать
что
гарантии,
Тьюринга,
на
нее,
она
в
что если
начальное
то она
q0
и
на
начнет считывать с ленты
двигать
ленту,
остановится
но
у нас
(например,
которая сдвигает ленту вправо
делает).
Проблема останова
мы
состояние
нет
машина
и
больше
ничего не
состоит в том, что для
для
машины
каждого числа п
Тьюринга
требуется
Z
определить, остановится Z или нет, если она начинает
работу
в
ленты
если
состоянии
qo, наблюдая самый левый квадрат
Проблема останова называется разрешимой,
существует эффективный метод для ее решения.
п.
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
174
[ГЛ. 5
Если через Rz обозначить множество тех /г, для
которых Z не останавливается, то вопрос «Разрешима
ли
проблема
«Является
для Z?» эквивалентен вопросу
Rz рекурсивным множеством?». Ясно,
останова
ли
что для лиц, занимающихся теорией автоматов, Rz
представляет интерес. Я покажу, что существует такая
машина Тьюринга Z, для которой проблема _останова
неразрешима эффективно,
является даже
что
Rz (множество
останавливается)
те
не
которых Z
тех п, для
всегда является рекурсивно
перечислимым: на /г-м шаге,
Rz
Rz
следовательно,
рекурсивно перечислимым.
Отметим,
в
и
из
первых
останавливается за
я=1, 2, 3,
п чисел,
п тактов.
для
мы
...,
включаем
машина
которых
Поэтому,
Rz
если
Z
не
рекурсивно, то и Rz не рекурсивно, а так как оно
рекурсивно перечислимо, то Rz не является рекурсивно
перечислимым (см. теорему 1.6.2). Значит, чтобы найти
Z, у которой Rz не является рекурсивно
перечислимым множеством, надо найти Z, для которой Rz не
получим
Но это мы
множество.
рекурсивное
(см. теорему 1.6.3),
каждое
если
рекурсивно перечислимое
Rz для некоторой
Тьюрицга (см. § 1.6), мы
множеством
тезис
немедленно
сможем
показать,
что
множество является
машины
Z.
Используя
получаем, что для
любого данного рекурсивно перечислимого множества/?
можно найти машину Тьюринга Z(R), которая
эффективно выполняет следующую процедуру: для
данного числа п машина последовательно порождает
элементы
*2,
х\,
xiy равное
...,
R
из
Тогда
п.
до тех пор,
машина
пока не
п
стирает
найдется
и
останавливается.
Ясно,
что
Z(R)
R
n£R,
рекурсивно
перечислимое,
Rz(R)=R
имеет
т.
е.
только
останавливается
когда
=
не является
Rz(R)- Поэтому,
если
тогда,
R
рекурсивное множество, то
рекурсивно перечислимым иZ(R)
но
не
проблему останова.
существуют множества, которые
неразрешимую
Значит,
не
являются рекурсивно перечислимыми, но тем не менее
представляют интерес для лиц, занимающихся теорией
автоматов.
Следовательно,
неполноты в нашей
мы
нашли
рекурсивной
разные
логике.
степени
АРИФМЕТИЧЕСКИЕ ЛОГИКИ
§5.4]
§ 5.4. Арифметические
175
логики
Этот параграф посвящен разъяснению и точному
определению всех понятий, содержащихся в
формулировке теоремы Гёделя о неполноте: «Каждая
^-непротиворечивая и адекватная арифметическая логика
неполна».
Рекурсивная логика L называется арифметической
логикой, если она обладает свойствами,
перечисленными ниже в пп.
на две
разделен
содержательные
1, 2, 3
части.
разъяснения,
4. Каждый
и
В
а
части
в
(а)
части
из этих
пунктов
даются
(б)
формальные
требования.
У.
Правильно
У
(а)
позволяющий
нас
построенные
должен
быть
формулы
эффективный способ,
для любой строчки символов определить,
имеет она смысл или нет, прежде чем говорить об ее
истинности или ложности. Понятие «правильно
формула» (п. п. ф.) родственно понятию
грамматически правильно построенного предложения
в русском
языке. При такой интерпретации логики
построенная
п. п.
ф. содержат предложения, которые представляют
или
высказывания
предикаты.
Следовательно,
обе
человек» и «Сократ
человек» являются
фразы «jc
п. п. ф. русского языка, а «человек не»
не п. п. ф.
русского
языка.
(б) Для каждой арифметической
логики
рекурсивное множество слов,
логики L. Все теоремы L являются
непустое
п. п.
2.
ф.
Пропозициональные
L имеется
называемых
п. п.
ф.
связки
п. п. ф. А и В, мы хотим иметь
комбинировать их различными
способами, для того чтобы получать новые п. п. ф., такие, как
(а)
Если
нам даны
возможность
~Л
Azd В
А&В
Ау В
А ==В
не А
А влечет В
А и В
А
или В (или оба)
А тогда и только тогда,
когда
В.
1ГЛ. 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
176
Логические
является либо
принимают
системы,
которые
двузначными,
являются
истинным,
т.
е.
мы
любое
либо ложным
истинностное
рассматриваем,
высказывание
(предикаты
значение
при
замене всех переменных константами). Мы можем
рассматривать
приведенные выше пропозициональные
связки как двузначные функции (см. булевы функции,
§ 3.1), т. е. А&В истинно, когда А истинно и В
истинно; А&В ложно в остальных случаях.
Мы можем выразить это при помощи
«истинностной таблицы», позволяющей определить истинностное
единственное
значение
А
Мы
В
и
А&В
по
требуем,
истинны.
истинно и
задающая
ЛрВ
известным
А
В
А&В
и
и
и
и
л
л
л
и
л
л
л
л
значениям
чтобы AzdВ было истинным, если
Мы также требуем, чтобы если А
истинно, было истинным и В.
истинностные
удовлетворяют
истинностным
этим
значения
требованиям,
ЛзВ,
Схема,
которые
такова:
А
В
AziB
и
и
и
и
л
л
л
и
и
л
л
и
*) См., например, W. V. О. Q u i п е, Mathematical logic, rev«
ed. Harvard Univ. Press, Cambridge, Mass., 1958. (Прим. автора.)
См. также П. С. Новиков, Элементы математической логики,
Физматгиз, 1959. (Прим. ред.)
АРИФМЕТИЧЕСКИЕ ЛОГИКИ
§ 5.4]
177
Мы также имеем
А
~Л
а
л
л
и
и
Теперь
А
В
Ау В
и
и
и
и
и
Л
и
Л
=
Л
и
и
Л
Л
Л
Л
и
легко
пропозициональные связки
В
проверить, что все наши
могут быть построены из
A8lB
=
~[Azd~B],
Л V £
=
~Л:э£,
A
=
B
А
и
~
гэ:
[Az>B]&[Bz>A\ ~[[Az>B\z>~[Bz>A]].
Следовательно, если мы введем одни только
=
связки
и
~
их
установим
может
=
быть
связками.
потребовать,
правильного
и
гэ
при помощи подходящих
свойства,
наша
дополнена
При
чтобы
этом
эти
построения
б) Задаются
[ДзВ]
то
Л
В
логика
другими
мы,
связки
пропозициональными
конечно,
должны
сохраняли свойство
формул*).
рекурсивные
~А
аксиом
соответственно
Л.
словарные
~Л есть п.
функции:
ф. тогда
и только тогда, когда А есть п. п. ф. [A zdB] есть п. п. ф.
тогда и только тогда, когда и Л и В являются п. п. ф.
от
Если Л, В
и
и
С
и
п. п.
ф.
от
в
L,
то мы
имеем
п.
следующие
аксиомы:
T(L): [Лз[£зЛ]],
Т(L): [ [Л z> [В => С] ] з [ [A zd В]
T(L): [[~Вз~Л]з[ЛзВ]|.
*) То есть, чтобы формулы
ф. (Прим. ред.)
п. п.
с
этими
э
[А
э
связками
(5.4.1)
С] ],
(5.4.2)
также
были
ТЕОРЕМА ГЕДЕЛЯ О НЕПОЛНОТЕ
178
Кроме
мы
того,
используем
[ГЛ. 5
следующее правило
вывода:
Если
T(L):
Это правило
3.
А
T(L): [AzdB],
и
называется
В.
T(L):
то
modus ponens.
Кванторы
(а)
иметь
Для
В излагаемой
в
своем
ниже теории чисел мы должны
распоряжении числовые переменные.
этого мы введем последовательность хи х2, х3у
в
качестве
переменных, которые
принимать натуральные числа.
Для данной^п.
сказать,
что
возможных
п.
она
ф. А
значениях
мере для одного
мы хотим
выполняется,
ее значения.
иметь возможность
например,
переменной
Тогда
Квантор всеобщности: {х{)А\
...
значений могут
А
при
хи или по
нам
всех
крайней
нужны:
истинна
для
всех
значений Х\.
Квантор существования: (Зх^А: Существует
крайней мере одно значение хи для которого А
по
истинна.
Если переменная
квантора
в
(всеобщности
п. п.
ф.
или
находится
под
существования),
говорим, что она связана. В противном случае
говорим, что переменная свободна. Например,
знаком
то
мы
мы
х
(х)[х-\-2>х\, но
свободна в предикате [х + 2>х]&(у) [у>0].
Введем обозначение В(М, Л), которое читается:
«М связано в А». Мы скажем, что п. п. ф. замкнута,
связана в
(истинном)
высказывании
переменная не является в ней
будущей интерпретации замкнутые
если
никакая
свободной.
При
п. п.
будут представлять собой высказывания, а не
замкнутые п. п. ф.
предикаты. Если мы имеем предикат,
можем
ф.
то
получить из него высказывание, связав все его
свободные переменные кванторами всеобщности.
образом, из [х>у] получаем (ложное)
(х)(у)[х>у]. Замкнутая п. п. ф. C(W)y
полученная из данной п. п. ф. W, называется замыканием Wm
Далее, если X есть п. п. ф. и М есть переменная,
свободная в X, мы хотим иметь возможность делать подТаким
высказывание
АРИФМЕТИЧЕСКИЕ ЛОГИКИ
§ 5.4]
становку. Обозначим через
в
получается
S(X, М, N)
замещения
результате
179
слово, которое
переменной М
N
во всех вхождениях М в X.
(б) Имеется рекурсивно перечислимая
последовательность *i, x2j х3,
различных слов в L,
называемых
Никакая
переменными.
переменная
на
...
ф.
Имеется бинарная
ляется
функция
яв--
не
п. п.
М(А). М(А)
тогда, когда Л
словарная
является
п. п.
ф. и М
(М) ~А.
~
тогда и только
(ЗМ)А
переменная. Под
п. п.
мы понимаем
рекурсивная
ф.
Имеется бинарный словарный рекурсивный
В(МУ Л). Если В(М, А) истинный, то А есть
М
п. п. ф.,
переменная и М есть часть А (т. е.
А
ВМС при некоторых В и С). Когда В(хи А)
предикат
=
истинно, мы говорим, что Xi связано в А. Когда
ложно
и
свободно
Если
ни
Л,
в
Л,
мы
не
является
В(*ь А)
что
говорим,
Xi
Л.
в
никакая
какой
то мы
частью
является
Xi
п. п.
переменная
ф. В, которая
говорим,
что
для замкнутых п. п.
Если В (хи Л) и
Существует
S(X, М, N)
Л замкнута. РЛыпишемз.
ф. В(хи (х{)А)
Л
свободной
всегда истинна.
есть часть п. п.
словарная
такая, что
ф.
п.п.ф.
является частью п. п.
ф. С,
то
В (хи
рекурсивная
S(X, М, N)
С).
функция
является
в
полученным
результате замещения
его вхождениях в X. Таким
М
на
словом,
N
во
всех
образом,
S([Xz>Y], М, N)
есть
5(~Х М, N)
Если /=£/,
есть
~S(X, Ж, N).
то
S{{Xj}X,
функция
[S(X, М, N)z>S(Y, Ж, N)]
xt,
N)
есть
(xj)S(Xt
xt,
N).
Имеется еще одна словарная рекурсивная
C(W), которая называется замыканием W. Если W
п.п.ф., то C(W) есть з. п. п. ф. и получается
дописыванием спереди W нескольких кванторов
общности (возможно ни одного). Если W есть з. п. п. ф.,
есть
C(W)=W.
Если W
не
п.п.ф.,
то
и
C(W)
де
то
п.п.ф.
[ГЛ. 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
180
Отсюда следует,
так
рекурсивным,
W
C(W)
когда
тогда,
=
з. п. п.
класс
что
как
есть
W,
з. п. п.
ф.
ф.
является
и
тогда
только
и
существует рекурсивная
процедура для распознавания равенства.
4. Целые
числа
(а) Наше
логике
возможность
мы
ней
в
говорить
хотим
требование
последнее
состоит в том,
иметь
о
мы
иметь
Для этой
числах.
целых
нашей
арифметической
к
должны
цели
слова, называемые
нумералами, которые бы служили названиями целых
чисел. Идея введения нумералов преследует цель
разделить вещи
в
что
имена
и
логике
вещей. П.
этих
логике
это не сами числа
которые
являются
ф.
п.
как таковые, а
именами
в
нашей
нумералы,
чисел.
этих
(б) С
связываем
каждым целым числом п рекурсивно
слово (обозначаем его я*), которое мы
называем
нумералом,
то
п*фт*.
Если А
числом
ф., х{ свободно
нумерал, то 5 (Л, xif N)
связано в Л, то
есть
п. п.
или
переменная
Х{ не
с
связанным
Т(L): [S (A,
Этим
xL
rrf)
з
Если пфт,
п.
А
в
N
и
есть п.
п.ф. Если
(5.4.3)
(Эх,) А\.
определение
образом, арифметическая логика
рекурсивной логикой, снабженной точными
завершено
наше
арифметической логики. Таким
является
критериями правильного построения формул с
связками, с кванторами общности
пропозициональными
существования и с числами.
Посвятим оставшуюся часть этого параграфа
понятиям
со-непротиворечивости, адекватности и
и
полноты.
Определение
п-арной,
и
5.4.1. П.
п.
W
ф.
...,
никакие
другие переменные
свободными в W. Если W
я-арная п. п.
дг-ка
чисел,
полученную
вхождениях
Xi
из
в
то
W(jfv
...,
г/*)
W замещением
W,
/=
1, 2,
.,.,
я,
L называется
в
хп свободны
не являются
переменные хи
если
ф. в
L
и
на
у]
во
W
(уи..., уп)
обозначает п.
хь
в
п.ф.,
всех
АРИФМЕТИЧЕСКИЕ ЛОГИКИ
§5.4]
181
логику непротиворечивой, если она
противоречий.
Определение 5.4.2. Арифметическая логика
называется
непротиворечивой, если ни для какого
слова А не может быть T(L): А и T(L): ~А (другими
Мы
называем
свободна
от
словами, если нет такого выражения, для которого
средствами этой логики можно было бы получить его
отрицание).
Теперь предположим, T(L):W(m*)
и его
3,
...
Даже
если
в
L
невозможно
мы, конечно, можем считать
приведенного выше списка теорем.
это
для m
=
0, 1,2,
(х{) Wy
доказать
следствием
Следовательно,
бы рассматривать T(L):~ (х{) W как
противоречие. Таким образом,
со-непротиворечивость
и
так же желательной, как
просто
непротиворечивость, где
Определение 5.4.3. Арифметическая
называется (^-непротиворечивой, если в ней
мы
могли
является
L
такой
логика
нет
унарной п. п. ф., что для всех целых чисел m T(L):
W(m*) и T(L):
(х{) W.
Лемма 5.4.1. L противоречива тогда и только тогда,
когда все п. п.ф. в L являются теоремами.
~
В
Доказательство. Пусть T(L):A, T(L):~An
произвольная п. п.ф. в L. Покажем, что T(L):B.
Из
(5.4.1) T(L):[~Az>[~Bzd~A]}.
поненс T(L): [~Вг> ~А].
Из (5.4.2) T(L):[[~Bz>~A]zd[A=>B]].
По модус поненс T(L):[AzdB].
И наконец T(L): В.
Обратное утверждение (т. е. если все п. п. ф.
являются теоремами, то L противоречива) тривиально
(см. определение).
Следствие 5.4.2. Если L со-непротиворечива, то онаПо
модус
непротиворечива.
Скажем, что предикат Р вполне представим*) в
логике, если мы средствами этой логики всегда
можем
решить, является он истинным или ложным
после
подстановки
констант
(на
места
свободных
переменных).
*) Нумерически выразим (по Клиии). (Прим. ред.)
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
182
Определение
-
предикат. Скажем,
арифметической логике
W в L такая, что
5.4.4.
Пусть P(x[t
Р вполне представим
...,
что
L,
[ГЛ. 5
если
хп)
в
существует я-арная
п. п.
а) Для каждой я-ки чисел (уи
f/n), для
которой Р(уи у2,
уп) истинный, T(L): W (у\,
б) Для каждой /г-ки чисел (уи
уп), для
которой Р(уи
уп) ложен, T(L): ~W (у\,
*/*).
ф.
...,
...,
...,
у\).
...,
...,
...,
Попробуем
будем
теперь определить, какую логику
адекватной. Мы хотели бы иметь
мы
называть
возможность отвечать на
вопросы о рекурсивно
такой логике, так как мы
множества, которые могут быть
перечислимых множествах в
что это такие
порождены
знаем,
процессами. Поэтому они
для специалистов, строящих
механическими
представляют
различные
интерес
модели,
теорией автоматов,
§ 5.3 мы показали, что
занимающихся
для биологов и инженеров. В
Q может быть описано в
L только тогда, когда оно рекурсивно
перечислимо. В этом случае мы можем надеяться, что
она является полуполной для Q, т. е. существует
рекурсивно перечислимое множество слов W0l Wu W2i...
такое, что
множество
рекурсивной
чисел
логике
Q
Если
мы
для
мы
можем
хотим
=
{n\(L):Wn).
назвать
каждого
нашу логику адекватной,
чтобы
потребовать,
она
была
полуполной
множества,
т. е. чтобы она представляла каждое множество,
которое может быть представлено в рекурсивной логике!
При
рекурсивно
доказательстве
перечислимого
теоремы
5.3.1
мы
отметили,
могут быть
эффективно перенумерованы. Помня об этой нумерации, мы
можем говорить об у-м выводе
(выводе номера у).
Возьмем наше множество Q и соответствующее ему
множество слов {W0y Wu W2, ...}. Рассмотрим
следующий предикат R(xy у): «у
номер вывода Wxy>.
Если R(x, у) истинный, то у является номером
вывода о том, что х принадлежит Q. Теперь, взяв х и у,
мы можем эффективно построить Wx и эффективно
что
выводы
рекурсивной
логики
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ГЁДЕЛЯ
^§ 5.5]
породить
узнать,
=
а следовательно, эффективно
R(x, у) истинным или нет.
R(xy у) такой рекурсивный предикат, что
у-й
вывод,
является
Следовательно,
Q
183
[х| существует
такое у, что
R(л:, у) истинный).
Если мы добавим требование, чтобы каждый
рекурсивный предикат был вполне представимым,
у нас
будет
введения
достаточно
следующего
оснований
определения
для
то
формального
(по
адекватности
Дэвису).
Определение
5.4.5. Арифметическая логика L
называется адекватной, если для каждого рекурсивно
перечислимого множества Q существует вполне представимый в L предикат R(x, у) такой, что Q {x\
существует такое у, что R(x, у) истинный}.
=
И, наконец, последнее определение в этой книге*
Логика называется полной, если в ней можно
доказать
истинность
или
ложность
каждого
утверждения.
Более
формально
Определение 5.4.6. Арифметическая
называется
полной,
если
для
каждой
логика
з. п. п.
ф. А
в
L
L
либо
T(L):
Простое
неполноте дано в
А либо
T(L):
~А
доказательство теоремы
Гёделя
о
следующем параграфе.
§ 5.5. Доказательство теоремы Гёделя
о
неполноте
Теорема 5.5.1 (Гёдель). Если L является
{^-непротиворечивой и адекватной арифметической логикой^
то
L неполна.
Доказательство. Согласно теореме 1.6.3
такое Q, которое является рекурсивно
перечислимым, но не рекурсивным множеством. Так как L
адекватна, то существует предикат R(x, у), вполне
выберем
представимый
Q
=
[х\
в
L, такой,
что
существует у такое,
что
R(x, у) истинный}.
(5.5.1)
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
184
Значит, существует бинарная
когда
п.
[ГЛ. 5
п.ф. W
такая,
что
R(x, у) истинный,
ТЩ: W{x\y*).
Когда R(x, у) ложный,
ТЩ: ~W(x*,y*).
Пусть
U
унарная
п.
п.ф. (3x2)W. Очевидно,
(5.5.2)
Q={x\T(L): U(x*)\.
Для
что
W(n*> х2)
каждого целого числа п запишем
для
S(W9x, п*).
Предположим,
такое, что
R(n0l уо)
я0€ Q- Тогда найдется у0
истинный (согласно 5.5.1).
Но по (5.4.3)
ТЩ:
W(n*0, у*0).
ТЩ:
[Wfa. yl)^3x2W(nltx2)]
Следовательно,
и по
что
модус
поненс
T(L):(3x2)W(n*0, х2),
а
следовательно,
ТЩ:
Предположим обратное,
ТЩ:
£/(/$.
т. е.
(Зх2)
T(L):U(n*oy
(я;, х2)
Тогда
W
или
ТЩ: ~(x2)~W(nl,x2).
L является «-непротиворечивой,
как
существует такое целое число т0, что п.п.ф.
Так
является
не
R(n0, m0)
бы
мы
Таким
теоремой L. Следовательно, значение
(если бы оно было «ложь», то
ТЩ:
W(п^ т*0), а значит, n0£Q).
«истина»
имели
образом,
мы доказали
Q
=
[x\T(L): U(x*)}.
Теперь предположим,
п£Q (если бы n£Q,
Значит,
то
W'(n*Q, rrQ
что
ТЩ:
то мы имели
U(#*).
бы
T(L): £/(л*)
МОЗГ И МАШИНА
§56]
и
L
логика
была
185
Таким
противоречивой).
бы
U(x)} является подмножеством
{x\T(L):
множества (5. Согласно следствию 5.3.3
образом,
~
~и(х*)\Ф$.
{х\ТЩ:
так
в
Q
как
то
не
есть
рекурсивно перечислимое
Значит, существует
множество.
что
стороны, неверно также,
что
не
n0j
выводимы
и
~
(п*0),
L и, значит, L
в
tiodQ,
что
£/(#*). С другой
ибо из этого
Т (L): U
T(L):
/г0€ Q. Следовательно, U (ity
что
следует,
число
такое
время неверно,
же
не
полна,
^{по)
и
и
что
требовалось доказать.
Посмотрим
Согласно
теперь
(5.5.1)
на
его
наше высказывание
можно
~
U
интерпретировать
(я*).
как
оно обязательно является
и,
следовательно,
«истинным» высказыванием. И все же оно не является
n0€Q
е. мы показали, что если L со-непротисуществует истинное высказывание, не
Изменить это положение, добавляя
выводимое в L.
U
к списку аксиом, не удается, так как для вновь
теоремой L,
воречива,
т.
то
(rfy
логики U опять верны все те
которые выше привели нас к теореме Гёделя.
Значит, мы снова можем найти такое число пи что
полученной
обстоятельства,
^
высказывание
теоремой Z/,
U
(#*)
истинно,
но
не является
и т. д.
§ 5.6. Мозг
и машина
Э. Нагел
Дж. Ньюман
и
в
своей
книге
«Теорема
Гёделя»*)
указывает
утверждают, что теорема Гёделя
пределы математических возможностей машин.
Приведем
«В
несколько цитат:
связи
с
теоремой
Гёделя
возникает
вопрос,
машину,
которая с точки зрения математических способностей
равнялась бы человеческому мозгу. Современные
машины содержат конечное число заложенных
вычислительные
можно
ли
построить
вычислительную
*) Е. N a g е 1 and J. Newman,
Univ. Press, New York, 1958.
GodePs
proff,
New
York
[ГЛ. 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
186
в них команд, которые соответствуют
правилам
вывода
процедуры.
Эти
функционируя
программам. Однако,
формализованной
машины
согласно
дают
фиксированным
аксиоматической
ответы
заложенным
в
на
вопросы,
них
как показал Гёдель в своей теореме о
существует бесконечное число проблем
элементарной теории чисел, решение которых
невозможно никаким данным аксиоматическим методом, и
на которые машины не смогут дать ответа, как бы
совершенны ни были их конструкции и с какой бы
скоростью они ни выполняли операции. Человеческий
неполноте,
мозг, возможно, также ограничен, но теорема Гёделя
указывает, что структура и мощь человеческого ума
являются более сложными и тонкими, чем строение и
функционирование любой машины, какую мы только
можем себе вообразить в настоящее время.»
Процитировав Нагеля и Ньюмана, я думаю, что
по справедливости, надо процитировать также и тех
авторов, которые с ними не согласны. Обе
из
книги
взяты
«Возможности
приведенные
ниже
цитаты
ума»*). Хилари Путнам (Hilary Putnam) в статье
и машины» («Minds and machines») пишет:
машина Тьюринга, которая
«Пусть Т
«Ум
представляет меня в том смысле, что
Т
может доказать в
утверждения, которые могу доказать я.
Тогда утверждают (Нагел и Ньюман не приводят
этого аргумента, но я думаю, что именно это они
имели в виду), что используя метод Гёделя, я могу
обнаружить высказывание, которое Т не может доказать,
и, более того, я могу доказать это высказывание. Это
опровергает утверждение, что Т «представляет» меня
и, следовательно, я не являюсь машиной Тьюринга.
точности
все
те
Здесь
имеет место элементарная ошибка,
заключающаяся в неправильном применении теоремы Гёделя.
Для произвольной данной машины Т я могу найти
такое £/, для которого я могу доказать:
если Т
непротиворечивая машина, то U
истинно, причем U неразрешимо посредством Г, еслиГдей-
*) ^Dimensions of Mind», Sydney Hook (ed.), Collier Books,
a
division of Growell-Collier Publishing Co., New York, 1961.
МОЗГ И МАШИНА
§5.6]
187
непротиворечивая. Однако Т также может
это, т. е. Т может доказать, что U
в ней неразрешимо, и если Т
непротиворечивая, то
U
«истинно» при данной программной
ствителъно
отлично доказать
U, которое Т
интерпретации. И утверждение
не
(предполагая непротиворечивость),
доказать (если я не докажу, что Т
что
мало
вероятно,
если
Т
может доказать
я
также не могу
непротиворечива,
достаточно
сложная
машина)!»
По-моему,
это опровержение Нагела и Ньюмана
удовлетворительно. Более
удовлетворительное возражение приводит Michael Scriven «The Complet Robot; «A Guide to Androidology». «Нагела и
Ньюмана вдохновил тот факт, что какие бы
аксиомы и правила вывода мы ни задали вычислительной
не вполне
машине, есть явные математические истины, которые
она никогда не сможет «получить» из этих аксиом по
данным правилам вывода. Это верно, но их
предположение, что это можем сделать мы, имея адекватное
данной машине понятие математической истины, ее
аксиомы и правила вывода, неверно. В таком случае
предположить, что формалисты были правы,
можно
и
они
могли
показать
неправоту Гёделя.
Теорема Гё-
деля не является большим препятствием для машин,
чем для нас самих. Мы можем только сказать, что
математикам было бы намного легче, если бы
формалисты
были
правы,
и
в этом
случае
можно было
бы
сравнительно просто построить механического
математика. Но они неправы, и это невозможно. Точно
так же
как
мы
что
мы
знаем;
истинность
распознаем
формулы, сравнивая то,
это
что
может
она
делать
невыводимой
утверждает,
и
с
тем,
вычислительная
машина».
Любой человек, знакомый с вычислительными
хорошо знает, что при современном уровне
программирования их «интеллект» не идет ни в какое
сравнение с человеческим. Приведенные выше
аргументы
нельзя
рассматривать как доводы в пользу
большого «интеллекта» современных машин. Они лишь
утверждают, что теорема Гёделя не дает
машинами,
доказательства
невозможности
«интеллектуальной»
машины.
~
[ГЛ. 5
ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
188
Наше
знакомство
с
персептроном
сведения об искусственном
навести
(§ 2.2) и
(§ 4.5)
интеллекте
краткие
должны
на мысль, что многие ограничения
современных вычислительных машин
могут быть преодолены за счет более совершенных
нас
«интеллекта»
конструкций
и
программирования.
показывает,
что
машина
Пример персеПтрона
приспосабливаться.
может
При- обсуждении искусственного интеллекта мы
«творческой». Примеры
видели, что машина может быть
следящих
иметь
действия
действиями
систем
очень
человека,
между
показывают,
целенаправленное
примитивны
но
человеком
все
и
же
что
поведение.
по
ясно,
машина
Конечно,
сравнению
что
казались
очень
времени
только количественными.
эти
с
многие
машиной, которые
может
все
различия
до последнего
являются
существенными,
Заключение
В этой
экспериментальных
книге
и
данных
менее
связанных
огромна, нова
же
быстро,
охватили
мы
основательное
более
количество
или
теорий. Эта область науки
быстро развивается. Почти так
ними
с
и очень
как
много
сама
наука, растет
обозначающих саму науку
или
ее
названий,
число
кибернетика,
части:
бионика, нейродинамика, теория самоорганизующихся
«искусственный интеллект» и т. д. Заканчивая
систем,
этого изобилия имен слово
обозначать им все содержание
этой книги, а не только те направления, которыми мы
интересовались в главе 4. Познания о кибернетике
этом
в
широком смысле, которые дает эта книга,
книгу,
я
выделю
«кибернетика»
легко
и
из
всего
буду
могут привести к
я
думаю, что
Поэтому
чрезмерной
неплохо
самонадеянности.
читателю
дать
предостережений:
Отбор материала, содержащегося
несколько
в этой книге,
1.
силу самой его природы мог быть только
субъективным. Ни одну из рассматриваемых здесь теорий
нельзя считать последним словом в этой области.
в
Я могу
предвзятый
только
что
надеяться,
дал
не
слишком
послужит
обзор предмета
твердой основой для дальнейшего чтения.
2. Кибернетика
это наука,возникшая на стыке
многих дисциплин. Поэтому, в лучшем случае, она
дает
ученому удовольствие работать одновременно
в
и
нескольких
областях таких,
психология,
математика
она
позволяет
выполнения
занимаясь
этом
и
не
своих
страдает,
эта
как
книга
техника,
физиология. В худшем
очень
так
же
хорошему инженеру
обязанностей,
теоретической
не
что
он
от
некомпетентно
биологией;
как
случае
уйти
его
гордость
слишком
мало
при
знает
190
ЗАКЛЮЧЕНИЕ
биологию, чтобы
понять, каким дураком он выглядит.
Чтобы
кибернетика могла избежать налета
псевдонауки, люди, работающие в ней, должны быть более
чем компетентны, по крайней мере в одном из
разделов современной
науки и должны быть действительно
знакомы
хорошо
соседние
игнорирующие
эффективно
с одним
более
или
из
соседних
Коллективы узких специалистов,
разделов.
общаться друг
с
слишком
специальности, чтобы
другом, не подходят для этой
цели.
3. Читатель, который решит погрузиться в массу
специальной литературы (в частности, отчеты о
многочисленных
симпозиумах), должен быть настроен
критически, потому что многие статьи содержат
чрезмерные претензии, технические ошибки и незнание
смежных областей.
4.
В
первом
кибернетикой,
что к
предсказывали,
порыве
многие
1960
г.
возбуждения,
лица
слишком
кибернетика
вызванном
смело
достигнет многих
как
машинный
результатов,
мозга.
Такой
создание
искусственного
сверхоптимизм должен был привести к обратной
захватывающих
перевод
таких,
и
реакции, самым выдающимся примером которой является,
по-видимому, книга Мортимера Таубе
«Вычислительные
здравый смысл»*). Реакция Таубе
кибернетику как
астрологией! Несомненно, такая позиция
машины
и
настолько сильна, что он сравнивает
науку
дала
представление
с
бы
о
неспециалисту очень искаженное
кибернетике. Тем
книгу Таубе
не
менее
вашему критическому
согласиться
с
критическими высказываниями
ные аргументы против его
и
когда
вы
сможете
я
рекомендую
вниманию.
справедливыми
привести собствен*
несправедливых
ских
тогда
высказываний
вы
сможете
возможности и границы
{а
таково
большинство
реалистически
Ибо,
его
критиче*
из
nux)t
увидеть
кибернетики.
*) Mortimer Taube, Computers and common sense, the
myth of Thinking machines, Columbia University Press, New York,
1961. [Русский перевод: M. Таубе, Вычислительные машины и
вдравый смысл, Изд-во «Прогресс», 1964.]
ЗАКЛЮЧЕНИЕ
Несмотря
подтверждает
на
мою
все
веру
191
эта
предостережения,
в то,
что
книга
знаменем
под
кибернетики была проделана большая и хорошая работа.
Цитируемая литература содержит основную суть
специальных публикаций, действительно добавляющих
пониманию
нечто к
нашему
машин
математики»,
чтобы
и
выявить
где
аналогию
общей
основы «мозга,
математика
между
управляющими,
вычислительными
информационными
машин.
аспектами
образуют
ядро новой
Я верю,
волнующей
человеческого познания,
используется,
работой
мозга
и
и
что
и
эти
публикации
ценной области
Приложен
Основные
ие
1
понятия
теории
множеств
Под множеством мы понимаем совокупность
объектов
(называемых
быть
точками,
элементами),
его
числами
или
которые могут
состояниями
конечного
автомата.
X
Если
из
состоит
элементов
хи
х2,
х3,
...,
то
пишут Х {хи х2у х3у
.}.
Через 0 обозначается пустое множество, т. е.
множество, не содержащее ни одного элемента.
Мы используем.запись х^Х, означающую «х
является элементом множества X». Так, например, если
X
множество четных чисел, то 2 € X, 46 X и т. д.
=
иногда
.
Обозначение
всех
х,
для
{х\у}
которых
.
используется для «множества
утверждение у». Таким
истинно
образом,
Х={х\х£Х).
Множество
целого п).
Если X
означает,
каждый
четных
У
и
что
X
элемент из
чисел
два
то
запись
подмножеством У,
т.
XaY
е.
X является элементом У.
для
любого
множества
X.
Если
пересечению X и У= {х\х£Х и х£У}
множеству элементов, каждый из которых
X иУ
=
2п для некоторого
два подмножества, то
У
XпУ
=
=
множества,
является
Например, 0аХ
X и
={х\х
=
=
принадлежит как X, так и У.
и У
{х\х£Х или х £ У}
объединению X
=
множеству элементов, каждый
принадлежит
=
по
крайней мере
из
из
к
которых
одному
множеств
X
или
У.
ОСНОВНЫЕ понятия ТЕОРИИ МНОЖЕСТВ
,
Если Ха
U
совокупность множеств,
[Ха\Р(а)}
=
[х\
существует
и
истинно
=
объединению
Если X и
=
{х\х£Х
У
два
х(£ У),
и
ТО
а, для которого
£ Ха)
Р(а)
истинно.
X\Y=
множества, то разность
где х
У».
Пусть N {0, 1, 2, 3,
Если XaN,
натуральных чисел.
У означает
(£
Р(а)
=
для которых
Ха,
тех
х
193
«х
не является
элементом
...} множество
=
то
дополнение
к
X
определяется как
X=N\X=
[х\х
входящим
является целым числом, не
Обозначение
/
:
X
У
используется
в
X].
для
/, отображающей множество X в множество У»,
т. е. «функции /, которая каждому х£Х сопоставляет
элемент f(x) € У». Например, если / определяется как
/(х)=х2, то f :N-+N.
«функции
Если X
чисел,
то
является подмножеством
характеристическая
множества целых
функция Сх : W->{0, 1}
множества X определяется так:
10,
1,
Если
декартово
=
X
и
У
первый
хФХ,
если
х£ X.
два заданных
произведение
множеству
если
X
и
множества, то
У
упорядоченных пар, в которых
принадлежит X, а второй
У\
элемент
Например,
декартова
произведением прямой
-+Z, то пишут /(*, (/),
плоскость
х
и
а не
прямой
является
у. Если
/((*, #)),
прямым
f ; XxY
*
Приложение
2
алгебры
Основные понятия
Операцией (бинарной), заданной
множестве Л,
на
непустом
функция со, которая каждой
упорядоченной паре (я, Ь) €АхА ставит в
соответствие определенный элемент множества Л,
называемый результатом операции на элементах а и Ь. Очень
часто
называется
операцию
употребляют для
называют
ab
[(«с
умножением
и
обычную мультипликативную
нее
=
запись
c
результатом операции (умножения)
ft» или «произведение аЬ равно с»).
является
на
элементах а и
Операция
называется
ассоциативной,
если для
любых а, b, c(l А
(ab) с
Множество А
операцией
называется
конечной,
(be).
если
нем
ассоциативной
А
конечное
множество.
единичным элементом (еди*
если для
еа
на
полугруппой. Полугруппа
называется
полугруппы,
а
заданной
называется
Элемент е€А
ницей)
с
=
=
ае
каждого элемента
=
а£А
а.
две
полугруппы.
Говорят,
Пусть А и А'
полугруппа А гомоморфно отображается на
полугруппу Л', если существует отображение q>: А
такое, что для каждой пары элементов а, Ь€А
что
*
А'
справедливо равенство
Ф(я6)
и
при
этом
прообраз
в
=
Ф(а)ф(6),
А' имеет хотя бы один
каждый
Л. В этом случае А' называется гомо*
элемент
морфным образом Л, а
называется гомоморфизмом.
само
отображение
ф
ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ
Группой
называется
такая
полугруппа,
195
в
которой
для любой пары элементов а и Ъ уравнения
ах
=
Ь
и
уа
=
Ь
имеют решения, притом единственные.
Отметим следующие свойства групп (которые
легко доказываются из определения группы):
1. В каждой группе существует единичный
элемент е.
'
2. Для каждого
один и только один
элемента
элемент
ab
=
а группы G существует
b 6 G такой, что'
e.
этого
элемента
справедливо также равенство
Ьа=е.
Элемент Ъ называется обратным элементом для а
и часто обозначается а~К Ясно, что обратным
е.
элементом для а"1 служит сам элемент а и что.£~!
Для
=
подмножество Н группы
G, которое само
Непустое
группой по отношению к групповой
операции G, называется подгруппой группы G. Если а
произвольный элемент О, то совокупность
всевозможных произведений вида aft, где ft пробегает всю
подгруппу Я, будем обозначать аН. Подгруппа Н
называется нормальным делителем группы G, если для
является
любого a£G
имеет место равенство
аН=На.
П риложение
3
Математика
биологии*)
в
Эдвард Мур
Биологи используют математический аппарат, но
ими, не поддаются
Теоретический анализ
математическому описанию.
пока сложные системы, изучаемые
самовоспроизведения
механизмов
в
будущем
Декарт
рассматривал
его души,
исключением
он давал
когда
и
может
привести
к появлению такого описания.
животных
как
шведской
уроки
и
человека,
механизмы.
королеве
за
Однажды,
Христине,
вопросом: «Но как же
Этот же вопрос
может машина воспроизводить себя?»
и
сегодня
математиков,
волнует
которые изучают
пределы возможностей машин. В своих усилиях создать
они
теорию
математическую
самовоспроизведения
математические
методы
для
применяют
изучения
процессов до сих пор считавшихся сугубо
обратилась
она
к
нему
с
биологическими.
Однако
то,
что
это оказалось не так просто.
физика
последние
и
триста
друга, передовая
лала
для
математика
лет,
бурно
биологии.
и
стимулируя
математическая
Несмотря
на
развивались
обогащая
друг
мысль немного еде*
Я припоминаю
несколько
Томас Мальтус создал математическую модель,
по которой население увеличивается в геометрической
прогрессии, в то время как производство
продовольствия возрастает лишь в арифметической,
обусловливая «борьбу за существование». Чарльз Дарвин и
Альфред Уоллес, ознакомившись с трудами Мальтуса,
увидели в этой борьбе проявление закона
исключений.
естественного
отбора. Другими
словами, чисто математическая
*) Edward Moor, Mathematics in the biological scienses.
Scientific America, № 9, 1964.
МАТЕМАТИКА В БИОЛОГИИ
способствовала
концепция
идеи
И
развитие
биологической
197
развитию
центральной
эволюции.
биологии
редко удавалось стимулировать
В этом смысле стоит отметить
математики.
популяций. Р. А. Фишер в Англии
США создали математические
модели, демонстрирующие закономерности совместного
действия законов наследственности и случайных
изучение генетики
и
Сьюэлл Райт
в
факторов, обеспечивающих
выживание
или
гибель
Чрезвычайно сложная
модель Райта базировалась на теории диффузии. Это
привело Вильяма Феллера из Принстонского
гена
определенного
в
популяции.
изучению новых разделов математики.
в своей повседневной работе биологи
используют математику. Как и при любых
исследованиях, биологи должны подвергать свои результаты
университета
к
Конечно,
определенным статистическим тестам (некоторые из
них были разработаны Фишером). Часто им
приходится пользоваться и аналитической геометрией,
представляя наблюдаемые зависимости в виде кривых.
Уравнения термодинамики знакомы биохимикам.
сыграла значительную роль в расшифровке
кода и в изучении строения генов. Но
все
это
традиционная математика. Хотя и было
предпринято множество отчаянных попыток создать
«математическую биологию», большая их часть, повидимому, не оправдала первоначальных'надежд. Тем
не менее, возможно, новейшие математические
Статистика
генетического
исследования
с
использованием
вычислительных
машин
достигнуть большего, чем раньше, когда
модели биологических процессов приходилось до
позволят
крайности упрощать.
Особая ценность
математики для
биологии
заключается не в использовании ее в качестве инструмента,
обнажить
а в ее силе
абстракции, позволяющей
фундаментальные проблемы и нащупать взаимосвязи
между казалось бы различными сущностями и
процессами.
Организмы
это
машины,
хотя
и
высоко
организованные. Мне кажется, что подлинное
сотрудничество между математикой и биологией возникнет
в результате разработки ряда логических проблем в
ПРИЛОЖЕНИЕ 3
198
теории машин, которые, как оказалось, имеют
связь
кую
и
будет
в
глубок
важнейшими проблемами биологии. Это
основном темой нашего последующего
с
обсуждения.
Клод Е. Шеннон (Массачусетский
технологический институт) и Джон Маккарти (Станфордский
университет) однажды заметили, что когда люди
моделируют человеческий организм,- машины, которые
они выбирают для этой цели, всегда являются
отражением своей эпохи. Декарт сравнивал организм со
сложными
водяными
часами;
в
начале
мозг рассматривали как коммутатор
наиболее совершенной моделью живого
нашего
века
АТС. Затем
организма стали
этой причине
большинство
занимающихся
ученых,
сравнительным
изучением животных и машин, сосредоточили внимание на
центральной нервной системе. Им пришлось -задать
себе два вопроса: Можно ли рассматривать мозг как
считать
своего
ЭВМ. Возможно,
рода
по
вычислительное
устройство?- Можно
ли
вычислительную машину, которая бы
«мыслила» как мозг?
Возникло несколько направлений исследований,
основой большинства из них является концепция
но
создать
«автомата»,
под
которым понимается
же требуется более
нейрофизиологии, за
основу берется некоторый идеализированный
машина
идеализированная
полное
или
часть ее.
соответствие
с
Когда
данными
например клетка.
теории автоматов рассматривают не их
внутреннее устройство, а наблюдаемые внешние
характеристики. По словам покойного Джона фон Неймана
элементы машины или организма «...рассматриваются
как
автоматы,
внутреннюю структуру которых не
нужно конкретизировать, но которые реагируют
совершенно определенным образом на совершенно
определенные раздражители».
Одной из самых полезных в этом смысле
абстракций является «конечный автомат». Это «черный
ящик», имеющий конечное число дискретных
внутренних состояний. Обычно он имеет конечное число
входов и выходов. Состояние автомата и*его выход в
организм или его часть,
В
МАТЕМАТИКА В БИОЛОГИИ
,
любой
момент
момент
Т находятся
времени
от
зависимости
и
состояния
времени
Имея
Т 1.
Тепущее
спгтпяние
ft
ь
Чз
9*
конечный
Генущий
бшод
состояние
1
4s
Чз
ч*
Чг
9*
Ь
Ч*
42
определенной
предыдущий
в
некоторый
Предыдущее Тепущее состояние
0
в
входа
199
0
0
0
1
Ч,
92
9з
9*
1
Рис. I. Конечный автомат это
идеализированная машина или часть машины: в теории
автоматов это основная составная часть систем,
начиная с нервных систем и вычислительных
машин
и
машинами.
кончая
самовоспроизводящимися
Автомат
может
таблицами. Первая
из
быть
них
описан
двумя
(вверху слева)
задает изменение состояния в единицу времени
в зависимости от входа. Другая (вверху справа)
задает выход по
каждому
описание может быть задано
(внизу). В вершинах указаны
дуги задают
переходы
состоянию.
Это
диаграммой
состояния и выходы;
для
каждого
входа.
определяющих его
другое, можно, зная
и
состояние
исходное
входную последовательность,
определить состояние и выход автомата в любой
момент времени. Правила переходов могут быть
представлены в виде таблицы или диаграммы (рис 1).
автомат
переходы
и
совокупность
из
одного
правил,
состояния
в
ПРИЛОЖЕНИЕ 3
200
Имея дело с конечным автоматом, важно ясно
представлять себе, что понимается под его состоянием.
Входной
комбинация набранных цифр.
такой
комбинацией
простом
примере
0, /, 0. Выход / означает «открыто».
конечных
автоматов.
последовательностью является
В
этом
является
деталей,
положения
многочисленных
невидимых
рычажков,
шестерен
снаружи
меняющиеся
с
ь.
каждым
перемещением внешних дисков с цифрами, как
показано на рис. 2.
В 1943 г. У. Маккаллок и У. Питтс (Массачусетский технологический
институт)
создали
абстрактную
упрощенную модель основного элемента
биологической нервной системы
нейрона, или нервной
клетки. Фактически это был конечный автомат с
двумя
возможными состояниями: возбуждения и покоя. Ком*
и
очень
эти элементы,
формальные нейроны они
нервной системы. Позже С. К. Клини
(Висконсинский университет) доказал общую теорему,
бинируя
или
строили модель
дающую
возможность
предсказать характер поведе^
МАТЕМАТИКА В БИОЛОГИИ
нейронной
ния, которого можно ожидать от
Питтса.
каллока
Теорема Клини
с
конечным
Мак-
сети
справедлива для любых устройств
состояний, не обязательно
числом
из
построенных
201
нейронов. Аппарат, разработанный для
нервной системе, привел в итоге
анализа процессов в
к получению новых теоретических
логике и в электротехнике.
Английский
«мыслящей
каких-либо
логик
А.
машины»
М.
Тьюринг
к
физиологии
о
проблеме
по-иному.' Не
подошел
предположений
результатов в
делая
мозга,
он
поставил задачу: определить в терминах
математической логики автомат, который мог бы в принципе
любые
выполнять
число
с
описанные
строго
вычисления.
большое
Тьюринга работает, выполняя очень
чрезвычайно простых операций. Это
Машина
конечным
состояний,
числом
но
автомат
снабженный
«лентой» бесконечной длины. Его программа записана на
участке ленты. Если машине предоставить
конечном
достаточно
времени,
то
записанные
команды
и
свободных участках той
ее
«головка»
печатает
же ленты.
прочитывает
результаты
Тьюринг
на
показал, что
можно
сконструировать даже «универсальную»
машину для производства любых возможных
вычислений. Если ее снабдить описанием задания и машины,
которая может выполнить это задание, то
«универсальная» машина «разберется», как выполнить
задание и выполнит его.
Как
так
и
нервной
абстрактное
модель
более
стимулировали
природе
шин.
мышления
сети
Маккаллока
Питтса,
машины
Тьюринга
понятие
появление
и
Специалисты
о
интересных гипотез о
колоссальных возможностях
ма«
по
теории автоматов, например,
пытались
моделировать способность биологических
систем к самовосстановлению и к надежному
функционированию, несмотря на наличие ненадежных
Фон Нейман показал, как можно построить
компонент.
машину, которая бы работала требуемым образом,
даже если в процессе
работы некоторые
ее
элементы
строя. Это достигается введением
избыточности: например, увеличением количества логических
выходят
из
ПРИЛОЖЕНИЕ 3
202
и
элементов
числа
соединений
вычислительной
электронной
самовосстановление
и
в
ними
между
И
машине.
чрезвычайно интересны
избыточность
с
зрения проектировщика ЭВМ или других
автоматических систем; в настоящее время этими
точки
проблемами серьезно занимаются.
Биологический нейрон, несомненно, не просто
выключатель с двумя состояниями: «включено» и
«выключено» в каждый данный момент времени.
Бесспорно и то, что ЭВМ не являются «мыслящими
Возможно,
машинами».
удастся
лучшие
построить
машины, не подражая мозгу в том виде, как мы его
сейчас понимаем, и, возможно, существуют более
короткие пути, ведущие к более полному его
пониманию, чем построение сверхупрощенных моделей
нейронов. Иногда мне кажется, что усилия,
направленные на конструирование этих моделей в качестве пер-»
вого шага на пути к «мыслящим машинам», похожи
на попытки наших предшественников создать
искусственные крылья, чтобы научить человека летать:
изучение полета птиц способствовало открытию ряда
аэродинамики, которые справедливы и для
аппаратов, создаваемых человеком, но конкретные
детали существенно различны. Что касается описания
законов
работы
мозга
превосходит
мнению
в
строгих
наши
логических
сегодняшние
фон Неймана, может оказаться,
конкретной деятельности
описанием
полная
схема
всех
удастся описать и
но, бесспорно, эта
более
сложная,
чем
нервных
в
то
терминах,
возможности.
связей.
что
это
По
простейшим
мозга
окажется
Возможно,
мозг
терминах математической логики,
задача
любые
на
несколько
созданные
порядков
до
настоящего
времени математические построения.
А не существуют ли такие свойства живых
организмов, которые легче подвергнуть логическому ана«
самовоспроизведение.
лизу? Одно из таких свойств
Вероятно,
проявление
а
это
наименее
«интеллектуальное»
Большинство организмов не «думает»,
вообще не имеют нервной системы, но все
жизни.
многие и
организмы воспроизводят себя. Есть надежда,
следовательно, что самовоспроизведение окажется
более
МАТЕМАТИКА В БИОЛОГИИ
простым, с точки зрения логики, чем
203
мышление.
Для
чтобы
построить логическую модель
самовоспроизведения, надо быть в состоянии по крайней мерз
того
сформулировать
изучения
основные
проблемы,
характеристик этого
наметить
некоторые
даже
касающиеся
и,
процесса,
приемы,
возможно,
кото'рыми
эти
могут быть решены; это может в свою
очередь подсказать биологам пути исследования и,
быть может, прольет свет на некоторые в
настоящее время
усиленно изучаемые биологические про-»
цессы.
Фон Нейман первый занялся детальным изучением
того, как в машине воплотить процесс
самовоспроизведения. Эта задача заключалась, по его
собственным словам, в следующем: «Можно ли из простых
элементов создать такую машину, которая, будучи
помещенной в резервуар, где в достаточном
проблемы
количестве
подобные
находятся
разрозненные
элементы,
бы создавать другие машины, являющиеся
точной копией оригинала?» Далее показывается
стала
реальность
подобной
обученная
модели:
определенным
помещенная
машина,
в
образом
«питательную» среду,
блуждать в ней, собирая части, нужные для
создания себе подобных, и со временем будет две,
и
затем четыре, восемь, шестнадцать таких машин
будет
так далее
до
тех
пор,
пока
хватает
элементов
свободного пространства.
На первый взгляд это звучит совершенно
неправдоподобно и даже несерьезно. Так ли уж
и
все
это
просто? Если кристаллический
«зародыш», состоящий
всего из нескольких молекул вещества, поместить в
среду, насыщенную такими же молекулами при соответствующей температуре и давлении, то свободные
кристалла
оседать на кристаллик, в точности
структуру. С этой точки зрения рост
есть самовоспроизведение. Еще пример
застежка
«молния»:
молекулы будут
повторяя
пары
его
зубчиков,
соединителя
в
и
ряд. Все остальные
вступают
в
здесь
происходит
сцепление
находящихся в среде, состоящей из
множества зубчиков, расположенных
зацепление,
зубчики тоже поочередно
образуя последовательность
ПРИЛОЖЕНИЕ 3
204
двухзубчиковых
кристалла.
Конечно,
на
это
тривиальные
аморфного
закрытому. А
них
к
вроде одномерного
примеры,
простейшего
использование
от
что-то
«машин»
построенные
изменения
состояния:
кристаллическому, от открытого к
пример с перфокартами. Каждая
вот
«машина»,
и она
воспроизводит
из
себя, конечно,
устройства дублирующего
перфоратора, который, собственно, и вносит в систему
необходимую упорядоченность. Попутно отметим, что
с
помощью
сложного
некоторые одноклеточные организмы могут
воспроизводиться в простой питательной среде, в то время как
более
высокоорганизованные
могут
потребовать
совершенной среды, содержащей, например,
более
такие сложные вещества
как витамины.
представляет интерес процесс
машины из простых элементов
Таким образом,
сложной
образования
возможно, из
большого их числа. Но количество разных типов
элементов (или их состояний) должно быть*невелико.
раз
этого и достиг
фон Нейман
в
Как
своей модели
самовоспроизведения.
Тем не менее
может возникнуть вопрос, насколько
отражает специфику соответствующего
биологического процесса. Одна из первых же
трудностей, с которыми пришлось встретиться, и способ,
каким она была преодолена, представляют собой
хороший пример связи с биологией. Фон Нейман вскоре
пришел к тому, что программа построения машиной
своей копии не может быть полной. Для получения
полной программы необходимо было бы дать
эта
описание
модель
не
только
автомата,
но
и
программы;
бесконечности.
Обойти эту трудность можно, создав две машины,
которые рассматривали бы описание в двух аспектах.
Одна из машин
копировальное устройство
потребовалось
бы
описание описания
и так до
устройство (О). Они работают
устройством синхронизации (s),
которое управляет работой каждого из них. Программа
должна описывать все три устройства (Bc+o+s). Всю
(С),другая
в
исполнительное
комплексе
машину
с
описать
C+0 + S +
выражением:
такой машине дано ее полное описа-
можно
{+Bc+o+s. Если
МАТЕМАТИКА В БИОЛОГИИ
ние, то
С копирует его,
205
О производит
а
все
действия,
для построения С, О и s.
Результаты, недавно полученные в
необходимые
молекулярной
обнаруживают поразительные аналогии
между элементами фон Неймана и процессами в живой
В
это
клетке.
набор генов, состоящих из дезоксирибонуклеиновой кислоты (ДНК), в которых
фермент
закодированы наследственные признаки. С
ДНК
полимер, который катализирует
генетике,
редупликацию ДНК,
в
О
в
аминокислоты
Первые
Но
Однако
несколько
эти модели не
продемонстрированы. В
кобсоном
из
самовоспроизводящаяся
фон
модели
«механическими».
с
инструкциями
образом ферменты
построении новой
в
участвуют
и
соответствии
таким
Полученные
ДНК копируют
образом набор генов.
из рибонуклеиновой кислоты
рибосом, которая соединяет
таким
система, состоящая
(РНК), ферментов
нити
чего
результате
друг друга, удваивая
менее
одной
и
ДНК.
другие белки
клетки.
Неймана были
были физически
общие
из них,
модели
построены.
были
построенной Г. Дже-
Бруклинского
машина
колледжа,
представляла собой поезд из
Вагоны представляли собой
автономные элементы системы, управление
осуществлялось устройствами, которые устанавливались в
игрушечных
вагонов*).
каждом вагоне.
разного
типа
Когда поезд, составленный
из вагонов
(в определенной последовательности),
помещался на пути, он начинал двигаться,
подталкивал
неприцепленные
менял
их
взаимное
пути, и составлял
вагоны,
при
необходимости
расположение, используя
из них поезда «по своему
запасные
образу
и
подобию». Джекобсон разработал подобную модель,
которая допускала поезда произвольной длины и
произвольную
построена
модель, в
последовательность
сравнительно
простая
которой воспроизводился
вагонов.
Им
была
демонстрационная
поезд из двух
вагонов.
*) Н. J a cob son, On models о! reproduction, Amer. Sci. 46,
№ 3, 255 268. [Русский перевод см, в «Кибернетическом
сборнике» JSfe
7, 1963.]
ПРИЛОЖЕНИЕ 3
206
генетику Л. С. Пенроузу
модель*), построенная частично
предположений о принципах
Английскому
принадлежит
другая
основе
его
самовоспроизведения
случае в
генетического
машину
материала. В простейшем
Пенроуза
В, вырезанные
Л и
на
входят элементы двух видов
образом, что они могут
соединяться друг с другом одним из двух способов.
Если в поднос поместить машину А В и несвязанные
элементы Л и В, а затем начать встряхивать поднос
.'(первая машина служит зародышом), то и возникают
новые соединения АВ (рис. 3). Если в качестве
таким
поместить машину ВЛ, то воспроизводимыми
парами будут ВА.
К числу достоинств механических моделей следует
отнести их наглядность и убедительность, но
зародыша
составить
трудно.
их
В
математическое
своих
обратился к
абстрактным
физических
моделей,
чрезвычайно
работах фон Нейман
описание
более поздних
моделям; он отказался от
избежав
этим
трудностей,
всех
связанных с их изготовлением, движением
Сформулированная
управлением.
им
задача
и
относилась
скорее к логике и математике, чем к механике и
электротехнике. Вместо «питательной среды» появилась
математическая
двумерная решетка или плоскость,
на
квадраты. В каждый квадрат помещается
разбитая
машина с конечным числом состояний
один элемент
(конечный автомат). Машины фон Неймана
не имеют
ни входов, ни выходов, они имеют лишь
некоторое
допустимых состояний. Таблица этих состоя^
ний и правила, определяющие переходы из одного
состояния в другие, являются общими для всех элемент
тов;
при этом в любой момент времени разные
элементы могут находиться в разных состояниях.
Каждая машина является детерминированным синхрон^
количество
ным
автоматом:
времени
Г
=
0)
своего
Т
(за
в
каждый дискретный
исключением
состояние
начального
каждого элемента
собственного
момент
состояния
при
зависит только от
состояния и состояния
ближайших
*) L. Р е п г о s е, Automatic mechanical self-reproduction, Ne\^
Biology, № 28, England, p, 92 (1959), {Прим, ред.)
МАТЕМАТИКА В БИОЛОГИИ
соседей
в
момент
времени Т 1.
состояние,
называемое
состоянии
находятся
Существует
состоянием
все
207
элементы,
«покоя».
за
особое
В этом
исключением
а)
Рис. 3. Самовоспроизведение является одним из биологических
процессов, подвергнутых математическому анализу. Маленькие
это два типа
заштрихованные и незаштрихованные «существа»
простейшей самовоспроизводящейся машины,
генетиком Л. С. Пенроузом.
Если эти части
поместить в поднос (а) и начать покачивать его взад-вперед,
то части будут сталкиваться друг с другом, не вступая в
зацепление (б). Но если в поднос поместить черно-белый зародыш
составных
частей
сконструированной
или
«машину» (в) и снова покачать его, то зародыш будет
способствовать приданию определенного наклона другим частям,
которые, вступая в зацепление, снова создают черно-белые
(г). Для наглядности эти машины показаны отдельно (д).
Если теперь за исходный зародыш взять бело-черную
комплексы
конфигурацию, то в результате покачивания будут возникать только белочерные машины (ж, з): машины дают «чистокровный приплод».
У Пенроуза «существа» были
показаны на
рисунке из
некоторого
элемент и
в
конечного
их
фанеры, а те, что
Телефонных лабораториях Белла.
числа.
Если''некоторый
ближайшие соседи находятся в
1, то этот элемент будет
времени Т
все
момент
сделаны из
алюминия в
его
покое
находиться в покое и в момент времени Т. Вся система в
целом: плоскость, разбитая на квадраты, элементар-
ПРИЛОЖЕНИЕ 3
208
ные машины, допустимые состояния и правила
перехода названа «мозаичной структурой» (рис. 4).
Конечная
совокупность элементов называется
если определены состояния всех входящих
«конфигурацией»,
в
нее элементов.
WV'W'
.У,
W7'
шШ
i
'//Ж
о
у.
WwvA
Рис. 4. Мозаичная структура
плоскости,
разделенная
Рассматриваемая
конфигурацию из
на
это часть
ячейки.
квадратные
область
представляет собой
40 ячеек,
состояния которых
обозначены Х% К, Z и 0 (невозбужденные).
Вся конфигурация состоит из трех
экземпляров семиклеточных конфигураций
(заштрихованы). Отдельные экземпляры должны быть
непересекающимися подмножествами.
Четвертое множество (заключенное в черный
контур),
хотя
и
повторяет
конфигурацию
остальных, не является самостоятельной копией изза пересечения с остальными.
Какая
же
связь
между всеми
этими
самовоспроизведением? Будем
рассматривать мозаичную структуру как некую
абстрактную среду, в которой квантованы пространство
определениями,
машинами
время,
а
и
движение
и
прочие
плавные
и
изменения
дискретных состояний;
к
переходы от одних состояний
другим
описываются некоторыми правилами. В этой среде
существуют конфигурации, составленные из элементов,
наши
это
«машины».
Эти машины и способны к
это
самовоспроизведению. Отдельные элементы
простейшие частицы, скажем молекулы. Изменение их
заменены
последовательностью
МАТЕМАТИКА В БИОЛОГИИ
209
можно представлять себе в виде
переходов, изменения уровня химической
положения.
изменения
активности,
геометрического
состояний
энергетических
А
правила
из
перехода
физические
и
состояния
химические
законы
в
состояние
это
среды,
определяющие изменения, происходящие в самих элементах,
их связь с другими элементами. Элементы,
это неиспользованное сырье, а
находящиеся в покое,
правила,
определяющие
состояние покоя,
и
фактически
какую-либо
гласят, что ни один элемент, не входящий в
конфигурацию, не может
машина «подбирается» к
внезапно
стать
активным;
окружающему сырью
лишь
действий.
Таким образом, необходимо построить мозаичную
структуру, состоящую из элементов с небольшим
путем
локальных
состояний (другими словами,
элементов), сформулировать правила
числом
весьма простых
переходов, а затем
такую конфигурацию, которая бы обладала
способностью к самовоспроизведению. Это до
некоторой степени напоминает процесс написания
программы для вычислительной машины. Фон Нейман
выдвинул дальнейшее требование: каждая конфигурация
должна содержать в себе машину Тьюринга. Затем
создать
он
подробно описал
конфигурацию, включающую
довольно
самовоспроизводящуюся
элементов
смерти
в
около
200 000
29 внутренними состояниями. После его
1957 г. мозаичными структурами
с
исследовались их структурные
особенности, процесс воспроизведения пытались записать
в строгой логической форме, результаты облекались
продолжали заниматься;
в
форму
Мы
быстро
доказываемых теорем.
уже
может
интересовались
вопросом:
насколько
популяция
самовоспроизводящихся конфигураций? В действительности она
может
возрастать экспоненциально, например
расти
удваиваться с каждым поколением. Численность
не
популяции
мозаичной структуры в любой момент
времени не может превышать квадрата времени ее
воспроизведения.
Сформулируем наше утверждение в качестве
если
теоремы:
самовоспроизводящаяся конфигурация
двумерной
ПРИЛОЖЕНИЕ 3
210
создает
то
себе подобных
f(T)
существует
конфигураций за время Г,
констанФа k9 такая что
f{T)
Последние комментарии
1 день 3 часов назад
1 день 8 часов назад
1 день 16 часов назад
1 день 18 часов назад
1 день 18 часов назад
3 дней 6 часов назад