Редактирование: Игра «Жизнь»

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 21: Строка 21:
 
===Базовые конструкции===
 
===Базовые конструкции===
 
Рассмотрим базовые конструкции необходимые для построения.
 
Рассмотрим базовые конструкции необходимые для построения.
 
+
<br><br>
 
В игры «Жизнь» можно построить различные конструкции (см. рис.):
 
В игры «Жизнь» можно построить различные конструкции (см. рис.):
 
* стабильные {{---}} не меняются с течением времени (первые два ряда),
 
* стабильные {{---}} не меняются с течением времени (первые два ряда),
Строка 29: Строка 29:
 
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
 
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
 
* glider eater {{---}} фигура, поглощающая планеры.
 
* glider eater {{---}} фигура, поглощающая планеры.
 
+
<br>
 
===Булевы функции===
 
===Булевы функции===
 
Так как <tex>\triangledown</tex> ([[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |полной системой]], то достаточно построить <tex>NOT</tex> и <tex>AND</tex>, чтобы показать возможность построения любой булевой функции.
 
Так как <tex>\triangledown</tex> ([[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |полной системой]], то достаточно построить <tex>NOT</tex> и <tex>AND</tex>, чтобы показать возможность построения любой булевой функции.
 
===Построение NOT===
 
===Построение NOT===
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.
+
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.<br>
 
 
 
 
 
[[Файл:Not.png|300px]]
 
[[Файл:Not.png|300px]]
 
===Построение AND===
 
===Построение AND===
См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.
+
См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.<br>
 
[[Файл:And.png|300px]]
 
[[Файл:And.png|300px]]
 
}}
 
}}
Строка 50: Строка 48:
 
[[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]
 
[[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]
 
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
 
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
 
+
<br>
 
МТ будет состоять из следующих элементов (см.рисунок):
 
МТ будет состоять из следующих элементов (см.рисунок):
* [[Детерминированные_конечные_автоматы |детерминированный конечный автомат]],
+
* конечный автомат,
 
* детектор сигнала,
 
* детектор сигнала,
 
* [[Стек|стек]],
 
* [[Стек|стек]],
Строка 65: Строка 63:
 
=== Контроллер стека ===
 
=== Контроллер стека ===
 
Контроллер стека производит конструкцию из планеров, необходимую стекам для произведения push или pop, осуществляет перемещение символов.
 
Контроллер стека производит конструкцию из планеров, необходимую стекам для произведения push или pop, осуществляет перемещение символов.
===Некоторые конструкции===
+
==Некоторые конструкции==
Ниже приведены некоторые конструкций игры, с помощью которых построены вышеупомянутые элементы.
+
<b>Пчелиная королева</b><br>
 
+
[[Файл:Queen_bee.png|350px]]<br>
====Пчелиная королева====
+
Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.<br><br>
[[Файл:Queen_bee.png|350px]]
+
<b>Buckaroo</b><br>
 
+
Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.<br><br>
Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.
+
<b>Pentadecathlon</b><br>
 
+
[[Файл:Pentadecathlon.png|500px]]<br>
====Buckaroo====
 
Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.
 
 
 
====Pentadecathlon====
 
[[Файл:Pentadecathlon.png|500px]]
 
 
 
 
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
 
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
 +
<br>
 
}}
 
}}
 
== См.также ==
 
== См.также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: