Почему "Игра жизни" Конвея может быть классифицирована как универсальная машина?

Question

Недавно я читал об искусственной жизни и наткнулся на утверждение, "Игра жизни Конвея демонстрирует достаточную сложность, чтобы быть классифицированной как универсальная машина". У меня было лишь приблизительное представление о том, что такое универсальная машина есть, и Википедия приблизила меня к пониманию настолько, насколько это когда-либо удавалось Википедии.Интересно, может ли кто-нибудь пролить некоторый свет на это очень сексуальное заявление?

Игра жизни Конвея мне кажется, это прекрасное развлечение с некоторыми потрясающими последствиями:Я не могу сделать скачок между этим и калькулятором?Это вообще тот скачок, который я должен совершить?

Answer 1

Ты может постройте машину Тьюринга из жизни Конвея - хотя это было бы довольно ужасно.

Ключ находится в планеры (и связанные с ними шаблоны) - они перемещаются (медленно) по игровому полю, поэтому могут представлять потоки битов (наличие планера для 1 и отсутствие для 0).Другие шаблоны могут быть построены для приема двух потоков глайдеров (под прямым углом) и выдачи другого потока битов, соответствующего И /ИЛИ /etc исходных двух потоков.

Редактировать:Подробнее об этом читайте на Веб - сайт LogiCell.

Answer 2

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

По сути, любой автоматический механизм, который может реализовывать AND, ИЛИ и NOT, может быть объединен достаточно сложными способами, чтобы быть завершенным по Тьюрингу.Это не самый полезный способ вычислений, но он соответствует критериям.

Answer 3

"Жизнь" Конвея можно завести еще дальше:Возможно построить модель Жизни, реализующую не только Универсальную машину Тьюринга, но и "Универсальный конструктор" Фон Неймана: http://conwaylife.com/wiki/Universal_constructor

Поскольку "Универсальный конструктор" может быть запрограммирован на построение любого набора ячеек, включая копию самого себя, "Жизнь" Коуэя, следовательно, способна к "самовоспроизведению", а не только к универсальным вычислениям.

Answer 4

Я настоятельно рекомендую книгу Паундстоуна "Рекурсивная вселенная".Вышел из печати, но вы, вероятно, сможете найти экземпляр, возможно, в хорошей библиотеке.Это почти все о силе Жизни Конвея и о вещах, которые могут существовать во вселенной с таким набором естественных законов, включая самовоспроизводящиеся сущности и IIRC, дарвиновскую эволюцию.

Answer 5

И Пол Чэпмен действительно построил универсальную машину Тьюринга с помощью game of life: http://www.igblan.free-online.co.uk/igblan/ca/ путем создания "Универсальной регистрационной машины Мински".

Рисунок построен на основе решетки размером 30x30 квадратов.Легкий Космические корабли (LWSSS) используются для обмена данными между компонентами, которые имеют логику P60 (за исключением регистров - см. Ниже).LWSS занимает 60 поколений, чтобы пересечь квадрат решетки.Следовательно, каждые 60 поколений любой межкомпонентный LWSS (импульс) находится в одном и том же положении относительно квадрата он находится внутри, что допускает вращение

.