Линейный клеточный автомат, эквивалентность МТ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность линейного клеточного автомата машине Тьюринга)
 
(не показано 12 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
==Определения==
 
==Определения==
{{Определение|definition=
+
{{Определение
'''Клеточным автоматом''' (КА) <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</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}|{n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}</tex>, называемое '''окрестностью''' (''neighborhood'') <tex>A</tex>. В данном определении полагается, что клетка всегда принадлежит своей окрестности.
+
* <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} \rightarrow S</tex> {{---}} функция перехода для <tex>A</tex>.
 
* <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=
 
{{Определение|definition=
'''Состоянием покоя''' (quiescent state) называется такое состояние автомата клетки <tex>c</tex>, что если автоматы клетки <tex>c</tex> и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то автомат <tex>c</tex> на следующем шаге останется в текущем состоянии.
+
'''Состоянием покоя''' (англ. ''quiescent state'') называется такое состояние автомата клетки <tex>c</tex>, что если автоматы клетки <tex>c</tex> и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то автомат <tex>c</tex> на следующем шаге останется в текущем состоянии.
 
}}
 
}}
 
{{Определение|definition=
 
{{Определение|definition=
'''Спокойной клеткой''' (quiescent cell) назовем клетку, автомат в которой перешел в состояние покоя.
+
'''Спокойной клеткой''' (англ. ''quiescent cell'') назовем клетку, автомат в которой перешел в состояние покоя.
 
}}
 
}}
 
{{Определение|definition=
 
{{Определение|definition=
'''Конфигурацией''' (configuraton) <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex> {{---}} шаг, после которого была получена конфигурация.  
+
'''Конфигурацией''' (англ. ''configuraton'') <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex> {{---}} шаг, после которого была получена конфигурация.  
 
Начальная конфиграция {{---}} <tex>c_0</tex>.
 
Начальная конфиграция {{---}} <tex>c_0</tex>.
 
}}
 
}}
 
{{Определение|definition=
 
{{Определение|definition=
'''Поддержкой''' (support) конфигурации <tex>c</tex> называется множество неспокойных клеток в ней. Обозначается <tex>sup(c)</tex>.
+
'''Поддержкой''' (англ. ''support'') конфигурации <tex>c</tex> называется множество неспокойных клеток в ней. Обозначается <tex>sup(c)</tex>.
 
}}
 
}}
 +
 
==Другое определение линейного клеточного автомата==
 
==Другое определение линейного клеточного автомата==
 
{{Определение|definition=
 
{{Определение|definition=
Строка 36: Строка 39:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для произвольной (m, n) машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.
+
Для произвольной <tex>(m, n)</tex> машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.
 
|proof=
 
|proof=
 
[[Изображение:Mpneighbour.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]]  
 
[[Изображение:Mpneighbour.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]]  
Строка 59: Строка 62:
 
{{Теорема
 
{{Теорема
 
|statement=Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.
 
|statement=Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.
|proof=Пусть эмулируется ЛКА с окрестностью радиуса <tex>d</tex> (из <tex>2d + 1</tex> клетки). Пусть в автомате клетки всего <tex>n</tex> состояний. Сопоставим каждому состоянию  алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетка ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь <tex>O(n^{2d+1})</tex> состояний {{---}} по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на <tex>d</tex> влево, затем на <tex>2d+1</tex> вправо, запоминая окрестность клетки, затем менять состояние текущей клетки соответственно поведению ЛКА, затем изменять окрестность, до тех пор, пока не поменяет правый терминал. При этом, если головка обрабатывает терминал, то после этого необходимо сдвинуться влево или вправо соответственно тому, какой терминал сейчас меняется, и поставить в текущую пустую клетку этот терминал. Такая МТ будет эмулировать заданный ЛКА.
+
|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.
+
* [[Линейный ограниченный автомат]]
 +
 
 +
== Источники информации ==
 +
* ''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:51, 10 марта 2019

Определения[править]

Определение:
Клеточным автоматом (КА) (англ. cellular automaton) [math]A[/math] размерности [math]d[/math] называется четверка [math] \langle {Z^d}, S, N, \delta \rangle[/math], где
  • [math]S[/math] — конечное множество, элементы которого являются состояниями [math]A[/math].
  • [math]N[/math] — конечное упорядоченное подмножество [math]Z^d[/math], [math]N=\{{n_j} \mid {n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}[/math], называемое окрестностью (англ. neighborhood) [math]A[/math]. В данном определении полагается, что клетка всегда принадлежит своей окрестности.
  • [math]\delta : S^{n} \rightarrow S[/math] — функция перехода для [math]A[/math].


Определение:
Линейным клеточным автоматом (ЛКА) (англ. linear cellular automaton) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из [math]2 \cdot r + 1[/math] клеток, находящихся на расстоянии не более [math]r[/math] от данной.


Определение:
Состоянием покоя (англ. quiescent state) называется такое состояние автомата клетки [math]c[/math], что если автоматы клетки [math]c[/math] и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то автомат [math]c[/math] на следующем шаге останется в текущем состоянии.


Определение:
Спокойной клеткой (англ. quiescent cell) назовем клетку, автомат в которой перешел в состояние покоя.


Определение:
Конфигурацией (англ. configuraton) [math]c_i[/math] КА называется распределение состояний автоматов по клеточному пространству, где [math]i[/math] — шаг, после которого была получена конфигурация. Начальная конфиграция — [math]c_0[/math].


Определение:
Поддержкой (англ. support) конфигурации [math]c[/math] называется множество неспокойных клеток в ней. Обозначается [math]sup(c)[/math].


Другое определение линейного клеточного автомата[править]

Определение:
Линейным клеточным автоматом [math]A[/math] назовем бесконечную ленту, в каждой клетке которой записан некоторый автомат. На вход автомату в клетке [math]i[/math] подается вектор из состояний автоматов в клетках с [math]i - r[/math] по [math]i + r[/math] включительно.
Лемма:
Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат.
Доказательство:
[math]\triangleright[/math]
Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как [math]D[/math]. Построим автомат [math]B[/math] следующим образом: множеством вершин [math]B[/math] будет объединение множеств вершин автоматов из [math]D[/math], переходы между вершинами [math]u[/math] и [math]v[/math] будут совпадать с переходами [math]D_i[/math], если [math]u[/math] и [math]v[/math] соответствуют вершинам из [math]D_i[/math], иначе переход отсутствует. Начальным состоянием автомата будет состояние,соответствующее начальному состоянию автомата [math]D_k[/math], который был записан в текущей клетке. Очевидно, что поведение такого автомата будет совпадать с поведением [math]D_k[/math].
[math]\triangleleft[/math]

Эквивалентность линейного клеточного автомата машине Тьюринга[править]

Теорема:
Для произвольной [math](m, n)[/math] машины Тьюринга [math]T[/math] существует двумерный КА с окрестностью из семи клеток и клеточным пространством [math]Z_T[/math] с [math]max(n + 1, m + 1)[/math] состояниями, симулирующий ее в реальном времени.
Доказательство:
[math]\triangleright[/math]
Рис. 1. Окрестность клетки

Каждому состоянию автомата клетки будет сопоставляться либо состояние автомата МТ, либо символ на ленте. Все клетки будут либо клетками ленты, расположенными в одном ряду, и в этом случае их состояние соответствует символу на ленте МТ, либо служебными клетками. Среди служебных клеток клетка [math]h[/math] будет соответствовать головке MT и в каждый момент находиться над какой-то клеткой ленты, клетки [math]a[/math] и [math]b[/math] всегда будут указывать на клетки слева и справа от [math]h[/math]. Остальные клетки будут находиться в состоянии покоя.

Заметим, что это порождает следующую проблему: размер входных данных МТ конечен, следовательно поддержка начальной конфигурации конечна. Так как МТ в общем случае может не остановиться, то в какой-то момент может потребоваться расширить ленту. Поэтому необходимо ввести две дополнительных служебных клетки, при необходимости расширяющих ленту влево или вправо (то есть переводящих соседнюю слева/справа клетку в свое состояние, а сами переходящие в состояние, соответствующее пустой клетке ленты МТ).

Построим окрестность, необходимую для корректной работы такого КА. Рассмотрев поведение МТ и зависимости клеток КА, получим, что минимальная по размеру окрестность имеет вид, представленный на Рис. 1.

Рис. 2. Эмуляция ленты МТ в КА
Также определим в каждой клетке состояние [math]w[/math], соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние [math]w[/math], которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ.
[math]\triangleleft[/math]
Теорема:
Для произвольной [math](m, n)[/math] машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, [math]max(m + 1, n + 1)[/math] состояниями, эмулирующий эту МТ в реальном времени.
Доказательство:
[math]\triangleright[/math]

Лента будет иметь следующий вид:

Рис. 4. Эмуляция ленты МТ в ЛКА
Доказательство и построение автомата аналогично предыдущей теореме.
[math]\triangleleft[/math]
Теорема:
Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.
Доказательство:
[math]\triangleright[/math]
Пусть эмулируется ЛКА с окрестностью радиуса [math]d[/math] (из [math]2d + 1[/math] клетки). Пусть в автомате клетки всего [math]n[/math] состояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетке ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь [math]O(n^{2d+1})[/math] состояний — по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на [math]d[/math] влево. Затем левый терминал будет переноситься на [math]d[/math] клеток влево, а для каждой клетки правее нового положения левого терминала будет запоминаться ее окрестность, затем будет изменяться ее состояние соответственно поведению ЛКА. И так для всех клеток, пока не встретится правый терминал. В этом случае необходимо перенести его на [math]d[/math] клеток вправо и продолжить менять клетки до его следующего вхождения. Затем перейти к следующей фазе. Такая МТ будет эмулировать заданный ЛКА.
[math]\triangleleft[/math]

Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны.

См. также[править]

Источники информации[править]

  • A.R. Smith IIISimple Computation-Universal Cellular Spaces, Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971.
  • M. DelormeAn Introduction to Cellular Automata, July 1998.