Линейный клеточный автомат, эквивалентность МТ — различия между версиями
(→Определения) |
м (rollbackEdits.php mass rollback) |
||
(не показано 38 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
==Определения== | ==Определения== | ||
− | {{Определение|definition= | + | {{Определение |
− | '''Клеточным автоматом''' <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> | + | | id=cellularautomaton |
+ | |definition= | ||
+ | '''Клеточным автоматом''' (КА) (англ. ''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>. | ||
− | * <tex>N</tex> {{---}} конечное упорядоченное подмножество <tex>Z^d</tex>, <tex>N=\{{n_j} | + | * <tex>N</tex> {{---}} конечное упорядоченное подмножество <tex>Z^d</tex>, <tex>N=\{{n_j} \mid {n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}</tex>, называемое '''окрестностью''' (англ. ''neighborhood'') <tex>A</tex>. В данном определении полагается, что клетка всегда принадлежит своей окрестности. |
− | * <tex>\delta : S^{n | + | * <tex>\delta : S^{n} \rightarrow S</tex> {{---}} функция перехода для <tex>A</tex>. |
}} | }} | ||
− | |||
{{Определение|definition= | {{Определение|definition= | ||
− | '''Линейным клеточным автоматом''' (ЛКА) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток, | + | '''Линейным клеточным автоматом''' (ЛКА) (англ. ''linear cellular automaton'') называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток, |
находящихся на расстоянии не более <tex>r</tex> от данной. | находящихся на расстоянии не более <tex>r</tex> от данной. | ||
+ | }} | ||
+ | {{Определение|definition= | ||
+ | '''Состоянием покоя''' (англ. ''quiescent state'') называется такое состояние автомата клетки <tex>c</tex>, что если автоматы клетки <tex>c</tex> и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то автомат <tex>c</tex> на следующем шаге останется в текущем состоянии. | ||
+ | }} | ||
+ | {{Определение|definition= | ||
+ | '''Спокойной клеткой''' (англ. ''quiescent cell'') назовем клетку, автомат в которой перешел в состояние покоя. | ||
+ | }} | ||
+ | {{Определение|definition= | ||
+ | '''Конфигурацией''' (англ. ''configuraton'') <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex> {{---}} шаг, после которого была получена конфигурация. | ||
+ | Начальная конфиграция {{---}} <tex>c_0</tex>. | ||
+ | }} | ||
+ | {{Определение|definition= | ||
+ | '''Поддержкой''' (англ. ''support'') конфигурации <tex>c</tex> называется множество неспокойных клеток в ней. Обозначается <tex>sup(c)</tex>. | ||
}} | }} | ||
Строка 17: | Строка 31: | ||
вектор из состояний автоматов в клетках с <tex>i - r</tex> по <tex>i + r</tex> включительно. | вектор из состояний автоматов в клетках с <tex>i - r</tex> по <tex>i + r</tex> включительно. | ||
}} | }} | ||
− | {{ | + | {{Лемма |
|statement=Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат. | |statement=Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат. | ||
− | |proof=Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как <tex>D</tex>. Построим автомат <tex>B</tex> следующим образом: множеством вершин <tex>B</tex> будет объединение множеств вершин автоматов из <tex>D</tex>, переходы между вершинами <tex>u</tex> и <tex>v</tex> | + | |proof=Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как <tex>D</tex>. Построим автомат <tex>B</tex> следующим образом: множеством вершин <tex>B</tex> будет объединение множеств вершин автоматов из <tex>D</tex>, переходы между вершинами <tex>u</tex> и <tex>v</tex> будут совпадать с переходами <tex>D_i</tex>, если <tex>u</tex> и <tex>v</tex> соответствуют вершинам из <tex>D_i</tex>, иначе переход отсутствует. Начальным состоянием автомата будет состояние,соответствующее начальному состоянию автомата <tex>D_k</tex>, который был записан в текущей клетке. Очевидно, что поведение такого автомата будет совпадать с поведением <tex>D_k</tex>. |
+ | }} | ||
+ | |||
+ | ==Эквивалентность линейного клеточного автомата машине Тьюринга== | ||
+ | {{Теорема | ||
+ | |statement= | ||
+ | Для произвольной <tex>(m, n)</tex> машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени. | ||
+ | |proof= | ||
+ | [[Изображение:Mpneighbour.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]] | ||
+ | Каждому состоянию автомата клетки будет сопоставляться либо состояние автомата МТ, либо символ на ленте. Все клетки будут либо клетками ленты, расположенными в одном ряду, и в этом случае их состояние соответствует символу на ленте МТ, либо служебными клетками. Среди служебных клеток клетка <tex>h</tex> будет соответствовать головке MT и в каждый момент находиться над какой-то клеткой ленты, клетки <tex>a</tex> и <tex>b</tex> всегда будут указывать на клетки слева и справа от <tex>h</tex>. Остальные клетки будут находиться в состоянии покоя. | ||
+ | |||
+ | Заметим, что это порождает следующую проблему: размер входных данных МТ конечен, следовательно поддержка начальной конфигурации конечна. Так как МТ в общем случае может не остановиться, то в какой-то момент может потребоваться расширить ленту. Поэтому необходимо ввести две дополнительных служебных клетки, при необходимости расширяющих ленту влево или вправо (то есть переводящих соседнюю слева/справа клетку в свое состояние, а сами переходящие в состояние, соответствующее пустой клетке ленты МТ). | ||
+ | |||
+ | Построим окрестность, необходимую для корректной работы такого КА. Рассмотрев поведение МТ и зависимости клеток КА, получим, что минимальная по размеру окрестность имеет вид, представленный на Рис. 1. | ||
+ | |||
+ | [[Изображение:Mptape.jpg|640px|thumb|center|Рис. 2. Эмуляция ленты МТ в КА]] | ||
+ | |||
+ | Также определим в каждой клетке состояние <tex>w</tex>, соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние <tex>w</tex>, которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement=Для произвольной <tex>(m, n)</tex> машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, <tex>max(m + 1, n + 1)</tex> состояниями, эмулирующий эту МТ в реальном времени. | ||
+ | |proof=Лента будет иметь следующий вид: | ||
+ | [[Изображение:Mplintape.jpg|640px|thumb|center|Рис. 4. Эмуляция ленты МТ в ЛКА]] | ||
+ | Доказательство и построение автомата аналогично предыдущей теореме. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement=Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга. | ||
+ | |proof=Пусть эмулируется ЛКА с окрестностью радиуса <tex>d</tex> (из <tex>2d + 1</tex> клетки). Пусть в автомате клетки всего <tex>n</tex> состояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетке ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь <tex>O(n^{2d+1})</tex> состояний {{---}} по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на <tex>d</tex> влево. Затем левый терминал будет переноситься на <tex>d</tex> клеток влево, а для каждой клетки правее нового положения левого терминала будет запоминаться ее окрестность, затем будет изменяться ее состояние соответственно поведению ЛКА. И так для всех клеток, пока не встретится правый терминал. В этом случае необходимо перенести его на <tex>d</tex> клеток вправо и продолжить менять клетки до его следующего вхождения. Затем перейти к следующей фазе. Такая МТ будет эмулировать заданный ЛКА. | ||
}} | }} | ||
+ | |||
+ | Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны. | ||
+ | |||
+ | ==См. также == | ||
+ | * [[Машина Тьюринга]] | ||
+ | * [[Линейный ограниченный автомат]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * ''A.R. Smith III'' {{---}} '''Simple Computation-Universal Cellular Spaces''', Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971. | ||
+ | * ''M. Delorme'' {{---}} '''An Introduction to Cellular Automata''', July 1998. | ||
+ | |||
+ | [[Категория: Теория вычислимости]] | ||
+ | [[Категория: Вычислительные формализмы]] |
Текущая версия на 19:42, 4 сентября 2022
Определения
Определение: |
Клеточным автоматом (КА) (англ. cellular automaton)
| размерности называется четверка , где
Определение: |
Линейным клеточным автоматом (ЛКА) (англ. linear cellular automaton) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из | клеток, находящихся на расстоянии не более от данной.
Определение: |
Состоянием покоя (англ. quiescent state) называется такое состояние автомата клетки | , что если автоматы клетки и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то автомат на следующем шаге останется в текущем состоянии.
Определение: |
Спокойной клеткой (англ. quiescent cell) назовем клетку, автомат в которой перешел в состояние покоя. |
Определение: |
Конфигурацией (англ. configuraton) | КА называется распределение состояний автоматов по клеточному пространству, где — шаг, после которого была получена конфигурация. Начальная конфиграция — .
Определение: |
Поддержкой (англ. support) конфигурации | называется множество неспокойных клеток в ней. Обозначается .
Другое определение линейного клеточного автомата
Определение: |
Линейным клеточным автоматом | назовем бесконечную ленту, в каждой клетке которой записан некоторый автомат. На вход автомату в клетке подается вектор из состояний автоматов в клетках с по включительно.
Лемма: |
Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат. |
Доказательство: |
Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как | . Построим автомат следующим образом: множеством вершин будет объединение множеств вершин автоматов из , переходы между вершинами и будут совпадать с переходами , если и соответствуют вершинам из , иначе переход отсутствует. Начальным состоянием автомата будет состояние,соответствующее начальному состоянию автомата , который был записан в текущей клетке. Очевидно, что поведение такого автомата будет совпадать с поведением .
Эквивалентность линейного клеточного автомата машине Тьюринга
Теорема: |
Для произвольной машины Тьюринга существует двумерный КА с окрестностью из семи клеток и клеточным пространством с состояниями, симулирующий ее в реальном времени. |
Доказательство: |
Каждому состоянию автомата клетки будет сопоставляться либо состояние автомата МТ, либо символ на ленте. Все клетки будут либо клетками ленты, расположенными в одном ряду, и в этом случае их состояние соответствует символу на ленте МТ, либо служебными клетками. Среди служебных клеток клетка будет соответствовать головке MT и в каждый момент находиться над какой-то клеткой ленты, клетки и всегда будут указывать на клетки слева и справа от . Остальные клетки будут находиться в состоянии покоя.Заметим, что это порождает следующую проблему: размер входных данных МТ конечен, следовательно поддержка начальной конфигурации конечна. Так как МТ в общем случае может не остановиться, то в какой-то момент может потребоваться расширить ленту. Поэтому необходимо ввести две дополнительных служебных клетки, при необходимости расширяющих ленту влево или вправо (то есть переводящих соседнюю слева/справа клетку в свое состояние, а сами переходящие в состояние, соответствующее пустой клетке ленты МТ). Построим окрестность, необходимую для корректной работы такого КА. Рассмотрев поведение МТ и зависимости клеток КА, получим, что минимальная по размеру окрестность имеет вид, представленный на Рис. 1. Также определим в каждой клетке состояние , соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние , которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ. |
Теорема: |
Для произвольной машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, состояниями, эмулирующий эту МТ в реальном времени. |
Доказательство: |
Лента будет иметь следующий вид: Доказательство и построение автомата аналогично предыдущей теореме. |
Теорема: |
Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга. |
Доказательство: |
Пусть эмулируется ЛКА с окрестностью радиуса | (из клетки). Пусть в автомате клетки всего состояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетке ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь состояний — по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на влево. Затем левый терминал будет переноситься на клеток влево, а для каждой клетки правее нового положения левого терминала будет запоминаться ее окрестность, затем будет изменяться ее состояние соответственно поведению ЛКА. И так для всех клеток, пока не встретится правый терминал. В этом случае необходимо перенести его на клеток вправо и продолжить менять клетки до его следующего вхождения. Затем перейти к следующей фазе. Такая МТ будет эмулировать заданный ЛКА.
Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны.
См. также
Источники информации
- A.R. Smith III — Simple Computation-Universal Cellular Spaces, Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971.
- M. Delorme — An Introduction to Cellular Automata, July 1998.