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

Question

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

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

Answer 1

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

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

Answer 2

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

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

РЕДАКТИРОВАТЬ: есть больше на этом на сайте LogiCell .

Answer 3

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

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

Answer 4

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

Answer 5

А Пол Чэпмен на самом деле создал универсальную машину Тьюринга с игрой жизни: http://www.igblan.free -online.co.uk / igblan / ca / ​​, построив «Универсальную регистрационную машину Минского».

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

.