Шрифт:
Одной из самых интересных задач является возможность создать машину Тьюринга, используя другую машину — игру «Жизнь». Этот автомат был придуман в 1970 году Джоном Хортоном Конвеем (р. 1937), профессором Кембриджского университета, где учился и Тьюринг. Речь идет о модели компьютера, которая была очень популярна среди любителей науки, особенно после того, как ее описал популяризатор математики Мартин Гарднер (1914-2010) в журнале Scientific American. Игра представляет собой клеточный автомат, то есть двумерную решетку, клетки которой заполнены конечными автоматами, также известными как машины конечных состояний. Речь идет об объекте, находящемся в одном из множества состояний, при этом данное множество конечно. Например, светофор может находиться в течение некоторого времени t в состоянии «зеленый», то есть в одном из трех возможных (красный, желтый, зеленый). Другой пример — нейрон, который может находиться в состоянии покоя или возбуждения. В машине Тьюринга, использующей для моделирования клеточный автомат, с течением времени состояния каждого конечного автомата обновляются. Обновление или расчет, каким будет состояние в следующий отрезок времени (lb + 1), происходит в соответствии с набором правил, известных как правила перехода, меняющие состояние каждого конечного автомата с учетом его актуального состояния и состояний соседних автоматов.
СОЗДАНИЕ МАШИНЫ ТЬЮРИНГА С ПОМОЩЬЮ ИГРЫ «ЖИЗНЬ»
В конце XX века несколько ученых и любителей науки задались вопросом: можно ли построить машины Тьюринга с помощью игры «Жизнь»? Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга. Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга. Возможность моделирования машины Тьюринга с помощью игры «Жизнь» привела к удивительному выводу: игра «Жизнь» имела аналогичные с компьютером возможности. Более того, любое природное явление, например формирование колец Сатурна или взаимодействие зайцев и волков, можно смоделировать с помощью компьютера. Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.
Один момент из игры «Жизнь».
В игре «Жизнь» каждый конечный автомат граничит с восьмью клетками, окружающими его в направлениях С, Ю, В и 3, а также по диагонали: С-В, Ю-В, Ю-3 и С-3. Считается, что для всех конечных автоматов возможны только два состояния: состояние 0 («мертвые клетки») и состояние 1 («живые клетки»); каждому из них соответствует свой цвет. Состояния конечных автоматов актуализируются с применением следующих правил перехода.
— Правило 1: если состояние конечного автомата tij 0 или 1, его следующее состояние, а именно t+1ij, будет таким же, как предыдущее, если количество соседних клеток в состоянии 1 равно 2:
t+1ij = tij, если сумма соседних клеток (tij) = 2.
— Правило 2: конечный автомат перейдет в состояние 1, если количество соседних клеток в состоянии 1 равно 3, изменение состояния автомата произойдет только при условии, что его состояние было 0 во время t. В противном случае состояние останется равным 1:
t+1ij = 1 если сумма соседних клеток (tij) = 3.
— Правило 3: описывает изменения при разном количестве соседних автоматов, находящихся в состоянии 1. Если количество автоматов рядом в состоянии 1 меньше 2 (то есть один или ни одного) или более 3 (четыре, пять, шесть, семь или восемь), конечный автомат «умирает», принимая значение 0. В этом случае изменение состояния происходит, только если во время t его состояние было 1, в противном случае состояние не будет изменено и останется равным 0:
если сумма соседних клеток (tij) < 2
t+1ij = 0
или сумма соседних клеток (tij) > 3.
При каждой итерации и применении правил перехода к каждому конечному автомату клеточный автомат эволюционирует, при этом появляются рисунки, характерные для данной игры. Образующиеся формы до сих пор вызывают восхищение среди компьютерных любителей. Существует большой выбор программ, позволяющих попробовать игру «Жизнь» (Life32, Xlife 2.0, Life 1.05/1.06, Pro Life, Mcell, dbLife и другие), из них самой впечатляющей является Golly.
АМЕРИКАНСКОЕ ПРИКЛЮЧЕНИЕ
В августе 1936 года Алан Тьюринг направил для публикации в Proceedings of the London Mathematical Society статью под названием «О вычислимых числах, с приложением к проблеме разрешимости». Мы уже говорили о ней, так как именно в этой работе впервые упоминалась машина Тьюринга. Также в статье даются определения понятиям «вычислимое» и «невычислимое» и представлены фундаментальные идеи математики и информатики. По воле случая в том же году Алонзо Чёрч опубликовал в журнале American Journal of Mathematics статью «Одна неразрешимая проблема элементарной теории чисел»; оба ученых разными путями пришли к одним результатам. Ход рассуждений Тьюринга был довольно оригинальным: он рассматривал класс операций, которые в реальном мире мог «механически» выполнять человек (например, клерк, осуществляющий одну и ту же задачу вновь и вновь) или машина (суммируя два числа). Ход рассуждений Чёрча был классическим для абстрактного мира, что традиционно для математики. К сожалению, Тьюринг опубликовал свою статью чуть позже, и это лишило его работу исключительности, так как ему приходилось ссылаться на статью американца. Однако обе статьи представляют теоретические основы создания машины, позже названной компьютером.
Месяц спустя, в сентябре 1936 года, Тьюринг отправился в США. Там он планировал получить докторскую степень и провести два года в Институте перспективных исследований в престижном Университете Принстона. Под руководством Алонзо Чёрча Тьюринг обратился к теме, странной даже сегодня — использованию в математике интуиции. Не теряя времени на философские объяснения, скажем, что интуиция может быть определена как продукт здравого смысла. То есть речь шла о предвосхищении или ментальном видении, которое помогает нам при рассуждениях прийти к умозаключению. Учитывая, что в ходе рассуждений мы связываем факты в логическую цепь, интуиция представляет собой дополнительный компонент, необходимый для разрешения задачи.
Жанры
- Романы
- Приключения
- Детективы
- Техно триллер
- Дамский детективный роман
- Исторические детективы
- Классические детективы
- Шпионские детективы
- Триллеры
- Юридический триллер
- Крутой детектив
- Полицейские детективы
- Медицинский триллер
- Иронические детективы
- Боевики
- Криминальные детективы
- Политические детективы
- Маньяки
- Зарубежные детективы
- Прочие Детективы
- Спецслужбы
- Драматургия
- Фантастика
- Хентай
- Ранобэ
- Сянься
- Дорама
- Уся
- Аниме
- Космоопера
- Юмористическая фантастика
- Боевая фантастика
- Героическая фантастика
- Технофэнтези
- Готический роман
- Социально-философская фантастика
- Попаданцы
- Историческая фантастика
- Ироническая фантастика
- Зарубежная фантастика
- Историческое фэнтези
- Юмористическое фэнтези
- Детективная фантастика
- Эпическая фантастика
- Мистика
- Космическая фантастика
- Фантастика: прочее
- Постапокалипсис
- Научная фантастика
- Киберпанк
- Альтернативная история
- Ненаучная фантастика
- РПГ
- Стимпанк
- Ироническое фэнтези
- Ужасы и мистика
- Сказочная фантастика
- Фэнтези
- Городское фэнтези
- Эзотерика
- Проза
- Военная проза
- Легкая проза
- Сентиментальная проза
- Советская классическая проза
- Антисоветская литература
- Афоризмы
- Эпистолярная проза
- Новелла
- Семейный роман
- Рассказ
- Классическая проза
- Эпопея
- Эссе
- Проза прочее
- Повесть
- Магический реализм
- Современная проза
- Контркультура
- Роман
- Историческая проза
- Русская классическая проза
- Феерия
- Стихи и поэзия
- Юмор
- Дом и досуг
- Рыбалка
- Охота
- Здоровье детей
- Домашние животные
- Воспитание детей
- Отдых / туризм
- Зарубежная прикладная литература
- Прочее домоводство
- Прикладная литература
- Домашнее хозяйство
- Кулинария
- Медицина и здоровье
- Сделай сам
- Спорт
- Хобби и ремесла
- Образовательная литература
- Сад и Огород
- Здоровье и красота
- Развлечения
- Коллекционирование
- Секс / секс-руководства
- Образование и наука
- Боевые искусства
- Органическая химия
- Обществознание
- Военная история
- Ветеринария
- Ораторское искусство / риторика
- Физика
- Химия
- Семейная психология
- Военная техника и вооружение
- Иностранные языки
- Прочая научная литература
- Психотерапия и консультирование
- Биохимия
- Cпецслужбы
- Астрономия и Космос
- Школьные учебники
- Учебная и научная литература
- Учебники
- Государство и право
- Психология
- Литературоведение
- История
- Научно-популярная литература
- Политика
- Детская психология
- Юриспруденция
- Шпаргалки
- Педагогика
- Физическая химия
- Медицина
- Биофизика
- Языкознание
- Зарубежная образовательная литература
- Зоология
- Геология и география
- Краткое содержание
- Зарубежная психология
- Саморазвитие / личностный рост
- Технические науки
- Религиоведение
- Военное дело
- Личная эффективность
- Аналитическая химия
- Рефераты
- Экология
- Философия
- Альтернативная медицина
- Математика
- Культурология
- Военное дело: прочее
- Ботаника
- Биология
- Словари и Энциклопедии
- Финансы и бизнес
- Отраслевые издания
- Бухучет и аудит
- Недвижимость
- Деловая литература
- Ценные бумаги
- Внешнеэкономическая деятельность
- Торговля
- Зарубежная деловая литература
- О бизнесе популярно
- Стартапы и создание бизнеса
- Корпоративная культура
- Управление, подбор персонала
- Маркетинг, PR, реклама
- Личные финансы
- Работа с клиентами
- Менеджмент
- Интернет-бизнес
- Поиск работы, карьера
- Малый бизнес
- Делопроизводство
- Государственное и муниципальное управление
- Банковское дело
- Экономика
- Книги по IT
- Техника
- Древние книги
- Документальное
- Прочее
- Интерьеры
- Газеты и журналы
- Театр
- Музыка
- Комиксы / манга
- Зарубежная классика
- Современная зарубежная литература
- Изобразительное искусство, фотография
- Мода и стиль
- Искусство и Дизайн
- Зарубежная литература о культуре и искусстве
- Фанфик
- Подростковая литература
- Шахматы
- Кино
- Культура и искусство
- Недописанное
- Классическая литература
- Без Жанра
- Народные
- Книги Для Детей
- Детские остросюжетные
- Сказки
- Детские стихи
- Прочая детская литература
- Детская образовательная литература
- Книги для дошкольников
- Детская фантастика
- Детские детективы
- Книга-игра
- Детский фольклор
- Буквари
- Детская проза
- Детская познавательная и развивающая литература
- Внеклассное чтение
- Зарубежные детские книги
- Детские приключения