Редактирование: Линейный клеточный автомат, эквивалентность МТ

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
==Определения==
 
==Определения==
{{Определение
+
{{Определение|definition=
| id=cellularautomaton
+
'''Клеточным автоматом''' (КА) <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</tex>, где
|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} \mid {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}|{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+1} \rightarrow S</tex> {{---}} функция перехода для <tex>A</tex>.
 
}}
 
}}
 
{{Определение|definition=
 
{{Определение|definition=
'''Линейным клеточным автоматом''' (ЛКА) (англ. ''linear cellular automaton'') называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток,
+
'''Линейным клеточным автоматом''' (ЛКА) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <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) называется такое состояние автомата клетки, что если автоматы клетки и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то они в них останутся.
 
}}
 
}}
 
{{Определение|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=
Строка 33: Строка 30:
 
{{Лемма
 
{{Лемма
 
|statement=Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат.
 
|statement=Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат.
|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>.
+
|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>.
 
}}
 
}}
  
Строка 39: Строка 36:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для произвольной <tex>(m, n)</tex> машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.
+
Для произвольной (m, n) машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.
 
|proof=
 
|proof=
[[Изображение:Mpneighbour.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]]  
+
[[Изображение:Neighbourhood.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]] Каждая клетка <tex>Z_T</tex> обладает множеством <tex>Q</tex> из <tex>M = max(n + 1, m + 1)</tex> состояний. Без потери общности, будем считать, что <tex>Q = \{ 0, 1, \dots , M - 1\}</tex>, так что <tex>(i + 1)</tex> будет сопоставляться символу <tex>x_i</tex> машины Тьюринга при <tex>0 \le i \le m - 1</tex>, а состояние <tex>(j + 1)</tex> будет соответствовать состоянию <tex>q_j</tex> машины Тьюринга при <tex>0 \le j \le n - 1</tex>. Ноль является состоянием покоя <tex>Z_T</tex> и не будет соответствовать символам и состояниям машины Тьюринга. Окрестность построим таким образом, чтобы выделять клетку, состояние которой <tex>Q_1 \in A = \{ 1, 2, \dots, m\}</tex> будет соответствовать символу машины Тьюринга из клетки, состояние которой <tex>Q_2 \in B = \{ 1, 2, \dots, n\}</tex> соответствует состоянию машины Тьюринга (окрестность клетки в таком КА показана на Рис. 1).
Каждому состоянию автомата клетки будет сопоставляться либо состояние автомата МТ, либо символ на ленте. Все клетки будут либо клетками ленты, расположенными в одном ряду, и в этом случае их состояние соответствует символу на ленте МТ, либо служебными клетками. Среди служебных клеток клетка <tex>h</tex> будет соответствовать головке MT и в каждый момент находиться над какой-то клеткой ленты, клетки <tex>a</tex> и <tex>b</tex> всегда будут указывать на клетки слева и справа от <tex>h</tex>. Остальные клетки будут находиться в состоянии покоя.  
+
 
 +
Таким образом, <tex>Z_T</tex> симулирует машину Тьюринга, используя конфигурацию, в которой оно <tex>"</tex>выглядит как<tex>"</tex> машина Тьюринга. Один ряд клеток в <tex>Z_T</tex> представляет из себя ленту машины Тьюринга {{---}} одна клетка <tex>Z_T</tex> для каждой клетки ленты, а одна клетка из соседнего ряда будет соответствовать головке МТ, и в каждый момент времени автомат будет выглядеть так, как показано на рисунке ниже. Клетки <tex>a</tex> и <tex>b</tex> всегда указывают на клетки слева и справа от головки <tex>h</tex> соответственно. Все остальные символы используются для хранения состояний: <tex>S_k \in A</tex> обозначает состояние клетки ленты на расстоянии <tex>|k|</tex> от головки по направлению знака индекса, <tex>P \in B</tex> обозначает состояние головки. Также определим клетки <tex>C_R</tex> и <tex> C_L</tex>, которые будут определять правый или левый конец используемой ленты. Все клетки кроме <tex>h</tex> и клеток ленты будут находится в состоянии покоя ноль, включая <tex>C_R</tex> и <tex> C_L</tex>.
 +
 
 +
Таким образом, при симуляции головка <tex>h</tex> будет двигаться, повторяя поведение головки соответствующей МТ, при этом менять состояние будут только клетки <tex>a, h, b, C_R, C_L</tex>, для которых необходимо определить функции перехода. Обозначим для них функцию перехода: если <tex>x_u, q_v</tex> {{---}} символ на ленте и состояние МТ, то переход будет иметь вид <tex>(x_u, q_v) = {x_p}X/q_q</tex>, где <tex>X</tex> {{---}} сдвиг влево <tex>L</tex> или вправо <tex>R</tex>. Состояния <tex>C_L</tex> и <tex>C_R</tex> необходимы для решения проблемы конца ленты: в общем случае машина Тьюринга работает с бесконечной лентой, в то время как поддержка начальной конфигурации построенного автомата конечна, и в некоторый момент пустые состояния закончатся. Чтобы этого не произошло, введены <tex>C_L</tex> и <tex>C_R</tex>, которые переводят спокойные клетки в состояния, соответствующие пустым символам ленты МТ.
  
Заметим, что это порождает следующую проблему: размер входных данных МТ конечен, следовательно поддержка начальной конфигурации конечна. Так как МТ в общем случае может не остановиться, то в какой-то момент может потребоваться расширить ленту. Поэтому необходимо ввести две дополнительных служебных клетки, при необходимости расширяющих ленту влево или вправо (то есть переводящих соседнюю слева/справа клетку в свое состояние, а сами переходящие в состояние, соответствующее пустой клетке ленты МТ).
+
[[Изображение:Tape.jpg|640px|thumb|center|Рис. 2. Эмуляция ленты МТ в КА]]
  
Построим окрестность, необходимую для корректной работы такого КА. Рассмотрев поведение МТ и зависимости клеток КА, получим, что минимальная по размеру окрестность имеет вид, представленный на Рис. 1.
+
Функция перехода имеет следующий вид:
  
[[Изображение:Mptape.jpg|640px|thumb|center|Рис. 2. Эмуляция ленты МТ в КА]]
+
[[Изображение:Transit.jpg|640px|thumb|center|Рис. 3. Функция перехода]]
  
Также определим в каждой клетке состояние <tex>w</tex>, соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние <tex>w</tex>, которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ.
+
Также определим в каждой клетке состояние <tex>w</tex>, соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния, эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние <tex>w</tex>, которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ.
 
}}
 
}}
  
Строка 56: Строка 56:
 
|statement=Для произвольной <tex>(m, n)</tex> машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, <tex>max(m + 1, n + 1)</tex> состояниями, эмулирующий эту МТ в реальном времени.
 
|statement=Для произвольной <tex>(m, n)</tex> машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, <tex>max(m + 1, n + 1)</tex> состояниями, эмулирующий эту МТ в реальном времени.
 
|proof=Лента будет иметь следующий вид:
 
|proof=Лента будет иметь следующий вид:
[[Изображение:Mplintape.jpg|640px|thumb|center|Рис. 4. Эмуляция ленты МТ в ЛКА]]
+
[[Изображение:Tape2.jpg|640px|thumb|center|Рис. 4. Эмуляция ленты МТ в ЛКА]]
Доказательство и построение автомата аналогично предыдущей теореме.  
+
Доказательство аналогично предыдущей теореме.  
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.
 
|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> клеток вправо и продолжить менять клетки до его следующего вхождения. Затем перейти к следующей фазе. Такая МТ будет эмулировать заданный ЛКА.
+
|proof=Пусть эмулируется ЛКА с окрестностью радиуса <tex>d</tex> (из <tex>2d + 1</tex> клетки). Пусть в автомате клетки всего <tex>n</tex> состояний. Сопоставим каждому состоянию  алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетка ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь <tex>O(n^{2d+1})</tex> состояний {{---}} по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на <tex>d</tex> влево, затем на <tex>2d+1</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.
 
 
 
[[Категория: Теория вычислимости]]
 
[[Категория: Вычислительные формализмы]]
 

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

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

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