Редактирование: Модели клеточных автоматов
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title= | + | '''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2%D0%BA_2020_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br> |
Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.<br> | Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.<br> | ||
Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). <br><br> | Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). <br><br> |