Тоффоли Т., Марголус Н. Машины клеточных автоматов

М.: Мир, 1991. — 283 с. — ISBN 5-03-001619-8.Книга американских специалистов, излагающая теорию клеточных автоматов Дж. фон Неймана и описание машины клеточных автоматов на базе персональной ЭВМ (IBM PC). Такие машины могут использоваться для моделирования физических процессов, при решении комбинаторных и вычислительных задач, задач прикладной кибернетики. Изложение отличается простотой и ясностью и рассчитано на первоначальное ознакомление с предметом.
Для математиков-прикладников, специалистов по теории автоматов, физиков разных специальностей, аспирантов и студентов университетов.Идея клеточных автоматов была сформулирована независимо Дж. фон Нейманом и К. Цусе в конце 40-х годов. Оба рассматривали их как универсальную вычислительную среду для построения алгоритмов, эквивалентную по своим выразительным возможностям машине Тьюринга. Эта идея породила волну многочисленных теоретических и прикладных исследований. Прежде всего это касается работ по созданию формальных моделей и алгоритмов на основе локальных взаимодействий, универсальных клеточных процессоров и нейрокомпьютеров. Начиная с 1976 г. в Берлине регулярно проводятся международные конференции по параллельной обработке информации на клеточных автоматах. Современный интерес к ним усиливается возможностью реализации на СБИС с высокой степенью интеграции, перспективами обработки информации на молекулярном уровне.Книгу "Машины клеточных автоматов", перевод которой предлагается читателям, выгодно отличают широта охвата проблемы, доступность изложения и образность подачи материала. Вначале вводятся основные понятия, даются необходимые исторические сведения и описывается машина клеточных автоматов CAM-6, созданная в Массачусетсом технологическом институте.Во второй части описываются различные классы правил, окрестностей и особенности динамики клеточных конфигураций. Начиная с простейших типов взаимодействий клеток, авторы постепенно подводят читателя к сложным вопросам развития клеточных структур и зависимости динамики конфигураций от пространственных и временных фаз жизни клеток. Третья часть книги посвящена моделям физических процессов в газах и твердых телах, фундаментальным свойствам клеточных автоматов. Выбор гибкого, расширяемого языка программирования Forth, допускающего возможность создания диалектов, необходимых для решения того или иного класса задач, не случаен. Используемая в нем форма записи выражений - обратная польская запись - позволяет существенно повысить эффективность синтаксического анализа, а стековый характер языка идеально соответствует архитектуре машин клеточных автоматов. При этом значительно упрощается и задача отображения Forth-алгоритмов на СБИС.Книга несомненно заинтересует многих читателей как превосходное, великолепно иллюстрированное введение в стратегически важную область вычислительной техники и информатики. Б.В. Баталов От переводчиков. Уже когда перевод готовился к изданию, в расцвете творческих сил ушел из жизни Борис Васильевич Баталов. Тридцать лет своей жизни Борис Васильевич посвятил становлению микроэлектроники в стране. Его живая мысль, энергия и целеустремленность продолжают жить в делах многочисленных учеников, коллег и друзей. Бориса Васильевича всегда отличали широкая эрудиция, стремление к развитию фундаментальных аспектов микроэлектроники, ясное видение перспектив ее развития. Именно поэтому перевод данной книги осуществлен под его редакцией. Светлая память о Борисе Васильевиче - человеке и ученом, навсегда сохранится в наших сердцах.Для математиков-прикладников, специалистов по теории автоматов, физиков разных специальностей, аспирантов и студентов университетов.Предисловие редактора перевода
Благодарности
Введение
Обзор
Клеточные автоматы
Основные понятия
Мультипликация вручную
Машины клеточных автоматов
Исторические замечания и литература
Среда CAM
Машина CAM-6
Основные аппаратные средства
Память: плоскость битов
Дисплей: цветовая карта
Динамика: таблицы правил
Геометрия в малом: окрестность
Геометрия в большом: обертывание
Программное обеспечение: CAM Forth
Живая демонстрация
Игра "жизнь"
Повторение эхом
Трассировка
Как разводить глайдеры
Правила игры
Выбор вселенной
Словесная формулировка правил
Возможности
Наши первые правила
Неограниченный рост
Ограниченный рост
Конкурентный рост
Правила голосования
Компьютер Бэнкса
«Случайные» правила
Динамика второго порядка
Возбуждение нейронов: правило с тремя состояниями
Задний ход
Непроницаемый барьер
Другие примеры
Соседи и окрестности
Слабо связанная пара
Волшебное число двенадцать
Объявление окрестностей
Основные назначения
Дополнительные назначения
Сводка окрестностей
Заказные окрестности
Создание таблиц
Цветовая карта и счетчик событий
Случайность и вероятностные правила
Экспоненциальное затухание
Простой генератор шума
Снова правила голосования
Замечания о шуме
Под вашу ответственность!
Источник шума
Антология методов
Сохранение частиц
Дифференциальные эффекты
Соединение двух половин
Генетический дрейф
Пуассоновское обновление
Асинхронные детерминированные вычисления
Одномерные клеточные автоматы
Приемы расширения окрестности
Тождественность и движение
Случайное блуждание
Случайные перемещения
Псевдососеди
Пространственные фазы
Временные фазы и фазовое управление
Двухфазное правило
Инкрементное управление фазой
Рабочий цикл
Чередующиеся пространственные текстуры
Окрестность Марголуса
Правила для блока
Частицы в движении
Столкновения
Как преобразовать правило для блока в правило для клетки
Соседи по Марголусу
Выбор четной/нечетной решетки 1
Фазочувствительный газ
Примеры
Фракталы
Криттеры
Асинхронное вычисление
Цифровая логика
Физическое моделирование
Симптомы и причины
Мелкозернистые модели физических явлений
Обратимость
Обратимые клеточные автоматы
Метод второго порядка
Чередующиеся подрешетки
Метод защитного контекста
Метод разбиения
Обратимость и случайность
Диффузия и равновесие
Управляемая шумом диффузия
Расширение и установление теплового равновесия
Самодиффузия
Средняя длина свободного пробега
Проявление изобретательности
Регулируемый источник шума
Ограниченное диффузией агрегирование
Динамика жидкостей
Звуковые волны
Гидродинамика
Трассировка течения
Течение после препятствия
Другие решеточные газы
Автокорреляции
Волновая оптика
Коллективные явления
Критические параметры и фазовые переходы
Системы Изинга
Только спины
Банки энергии
Тепловая ванна
Отображение энергии
Только связи
Спиновые стекла
Вычисления на основе баллистического метода
Модель вычислений посредством биллиардных шаров
Обратимый компьютер на основе клеточного автомата
Несколько экспериментов с моделью биллиардных шаров
Волшебный газ
Конец света
Выводы
Приложения
Краткое руководство по языку Forth
Интерпретатор команд
Компилятор
Словарь
Числа
Стек
Выражения
Редактирование и загрузка
«Константы» и «переменные»
Итерация
Стековые комментарии
АDUP, DROP и т.д.
Выбор варианта
Условные предложения
Логические выражения
Литература для дальнейшего изучения Forth
Основы архитектуры CAM 264
Плоскостной модуль
Большие массивы: склеивание границ
Увеличение числа состояний клетки: группирование листов
Увеличение размерности: наложение слоев
Отображение и анализ
Модульность и расширяемость
Литература