Редактирование: Линейный клеточный автомат, эквивалентность МТ
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
==Определения== | ==Определения== | ||
− | {{Определение | + | {{Определение|definition= |
− | |||
− | |definition= | ||
'''Клеточным автоматом''' (КА) (англ. ''cellular automaton'') <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</tex>, где | '''Клеточным автоматом''' (КА) (англ. ''cellular automaton'') <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</tex>, где | ||
* <tex>S</tex> {{---}} конечное множество, элементы которого являются состояниями <tex>A</tex>. | * <tex>S</tex> {{---}} конечное множество, элементы которого являются состояниями <tex>A</tex>. | ||
Строка 66: | Строка 64: | ||
Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны. | Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны. | ||
− | |||
− | |||
− | |||
− | |||
== Источники информации == | == Источники информации == |