Примеры неразрешимых задач: задача о замощении — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Постановка задачи)
(Замощение половины плоскости)
(не показано 26 промежуточных версий 4 участников)
Строка 1: Строка 1:
{{Определение
+
[[Категория: Теория вычислимости]]
 +
 
 +
== Определения ==
 +
{| border="0" width="100%"
 +
|{{Определение
 
|definition=
 
|definition=
'''Полимино''' ('''полиомино''', '''polyomino''') - плоская геометрическая фигура, состоящая из <tex>n</tex> одноклеточных квадратов, соединенных по сторонам.
+
'''Полимино''' (англ. ''polyomino'') плоская геометрическая фигура, состоящая из <tex>n</tex> одноклеточных квадратов, соединенных по сторонам.
 
}}
 
}}
===Пример===
+
|[[file:Polyomino_example.png|300px|right]]
[[file:Polyomino_example.png|300px]]
+
|}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Замощение плоскости''' ('''tiling''') - представление плоскости в виде множества полимино.
+
'''Замощение плоскости''' (англ. ''tiling'') представление плоскости в виде множества непересекающихся полимино.
 
}}
 
}}
 +
Пусть дана плоскость <tex>S</tex> и набор полимино <tex>P</tex>, если <tex>\exists ~ f: N \times N \to P</tex> (говорящая по клетке, какому полимино она соответствует) тогда считается, что можно замостить плоскость <tex>S</tex> данным набором.
  
{{Определение
+
== Замощение четверти плоскости ==
 +
{{Шаблон:Задача
 
|definition=
 
|definition=
<tex>Tiling_n = \{(P_1, P_2,..., P_k) ~ | ~ \frac{1}{n}</tex> плоскости можно замостить<tex>\}</tex>.
 
}}
 
===Пример===
 
[[file:Tiling_example.png|300px]]
 
 
== Постановка задачи ==
 
 
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
 
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
 
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
 
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
 +
}}
  
 
{{Теорема
 
{{Теорема
Строка 26: Строка 27:
 
Задача о замощении четверти плоскости полимино неразрешима.
 
Задача о замощении четверти плоскости полимино неразрешима.
 
|proof=
 
|proof=
Сведём неразрешимую Halt к данной задаче.  
+
[[m-сводимость|Сведём]] задачу останова к данной задаче.  
 
Пусть дана [[Машина Тьюринга|машина Тьюринга]] <tex>M =\langle \Sigma, Q, \Pi, B  \in \Pi, s,\delta: Q \times \Pi \rightarrow Q \times \Pi \times \{ \leftarrow, \downarrow, \rightarrow \} \rangle</tex> и слово <tex>w \in \Sigma^*</tex>. Требуется определить, остановится ли данная МТ на входе <tex>w</tex>.
 
Пусть дана [[Машина Тьюринга|машина Тьюринга]] <tex>M =\langle \Sigma, Q, \Pi, B  \in \Pi, s,\delta: Q \times \Pi \rightarrow Q \times \Pi \times \{ \leftarrow, \downarrow, \rightarrow \} \rangle</tex> и слово <tex>w \in \Sigma^*</tex>. Требуется определить, остановится ли данная МТ на входе <tex>w</tex>.
  
Будем эмулировать процесс выполнения МТ путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения.
+
Для того, чтобы доказать неразрешимость задачи о замощении, для заданной машины Тьюринга <tex>M</tex> и слова <tex>w</tex> построим набор полимино, которым можно замостить четверть плоскости, если МТ не остановится на заданном слове. Если же МТ останавливается, то четверть плоскости полученным набором замостить невозможно.
Первый ряд заполняется начальной конфигурацией, а каждый следующий ряд соответствует следующей конфигурации.
+
 
 +
Будем эмулировать процесс выполнения МТ на входе <tex>w \in \Sigma^*</tex> путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения.  
 +
Первый ряд эквивалентен начальной конфигурации МТ, а каждый следующий ряд соответствует следующей конфигурации. Говоря простым языком, каждый ряд представляет из себя "снимок" состояния машины на соответствующем этапе выполнения.
  
 
[[Файл:Polyomino_init.png]]
 
[[Файл:Polyomino_init.png]]
 +
 +
На рисунке сверху изображены два вертикальных ряда полимино. Первый ряд соответствует МТ и слову <tex>w</tex>. Первое полимино соответствует паре из первого символа и начального состояния, все остальные — символам из <tex>w</tex>. Во втором ряду второе полимино соответствует паре из символа <tex>w[2]</tex> и состояния <tex>q</tex>. То есть МТ сделала переход <tex>\delta (s, w[1]) = \langle q, w[1], \rightarrow \rangle</tex>.
  
 
Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид:
 
Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид:
Строка 39: Строка 44:
  
 
На каждой стороне такого полимино находится определенное число выступов/впадин.
 
На каждой стороне такого полимино находится определенное число выступов/впадин.
Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить <tex>k \le |\Pi| + |Q| + |\Pi \times Q| + 1</tex>) – это и будет количество выступов/впадин находящихся на одной стороне полимино.  
+
Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить <tex>k \leqslant |\Pi| + |Q| + |\Pi \times Q| + 1</tex>) – это и будет количество выступов/впадин, находящихся на одной стороне полимино.  
  
  
Строка 46: Строка 51:
 
[[Файл:Polyomino_start.png]]
 
[[Файл:Polyomino_start.png]]
  
где <tex>*</tex> – уникальные числа для каждых соседних двух полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда.
+
где <tex>*i</tex> – уникальное число для каждой смежной пары полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда.
  
 
Далее строим полимино для всех элементов алфавита <tex>c \in \Pi</tex>:
 
Далее строим полимино для всех элементов алфавита <tex>c \in \Pi</tex>:
Строка 54: Строка 59:
 
В нем количество впадин слева равно количеству выступов справа. Такой тип полимино передает содержимое ленты МТ следующему ряду.
 
В нем количество впадин слева равно количеству выступов справа. Такой тип полимино передает содержимое ленты МТ следующему ряду.
  
Теперь построим полимино для функции перехода <tex>\delta (a, c) = \langle p, d, D \rangle </tex>, где <tex>q \in Q, p \in Q, c \in \Pi, d \in \Pi, D\in \{\leftarrow, \downarrow, \rightarrow \}</tex>:
+
Теперь построим полимино для функции перехода <tex>\delta (q, c) = \langle p, d, D \rangle </tex>, где <tex>q \in Q, p \in Q, c \in \Pi, d \in \Pi, D\in \{\leftarrow, \downarrow, \rightarrow \}</tex>:
  
 
[[Файл:Polyomino_delta.png]]
 
[[Файл:Polyomino_delta.png]]
  
На рисунке изображены (сверху вниз) полимино соответствующие значениям <tex>D = \{\leftarrow, \downarrow, \rightarrow \}</tex>. Вместе со следующим типом они эмулируют перемещение головки МТ.
+
На рисунке изображены (снизу вверх) полимино соответствующие значениям <tex>D = \{\leftarrow, \downarrow, \rightarrow \}</tex>. Вместе со следующим типом они эмулируют перемещение головки МТ.
  
 
Далее построим следующий тип полимино:
 
Далее построим следующий тип полимино:
Строка 66: Строка 71:
 
Эти полимино получают на вход символ алфавита <tex>c</tex> от предыдущего ряда и состояние <tex>p</tex> от соседнего полимино, а затем передает следующему ряду пару из состояния и символа.
 
Эти полимино получают на вход символ алфавита <tex>c</tex> от предыдущего ряда и состояние <tex>p</tex> от соседнего полимино, а затем передает следующему ряду пару из состояния и символа.
  
 
+
Построим последний тип полимино, характеризующих состояния <tex>\#_Y</tex> и <tex>\#_N</tex>:
Построим последний тип полимино, характеризующие состояния <tex>\#_Y</tex> и <tex>\#_N</tex>:
 
  
 
[[Файл:Polyomino_halt.png]]
 
[[Файл:Polyomino_halt.png]]
Строка 76: Строка 80:
 
Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.
 
Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.
  
Таким образом, четверть плоскости замостится тогда и только тогда, когда закодировання МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.
+
Таким образом, четверть плоскости можно замостить тогда и только тогда, когда закодированная МТ не останавливается на данном входе. Иными словами, есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.
 +
 
 +
Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения. Значит задача о замощении полимино не разрешима.
 +
}}
 +
 
 +
== Замощение половины плоскости ==
 +
 
 +
{{Теорема
 +
|statement=
 +
Задача о замощении половины плоскости полимино неразрешима.
 +
|proof=
 +
Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.
 +
 
 +
Например, можно сделать новое количество выступов/впадин <tex>k' = \mathrm{cur_k} + \mathrm{max_k}</tex>, где <tex>\mathrm{cur_k}</tex> {{---}} количество выступов/впадин у полимино, от которого образовалось текущее, <tex>\mathrm{max_k}</tex> {{---}} максимальное число выступов/впадин у полимино в первой четверти.
  
Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения.
+
[[Файл:Polyomino_bad_case.png]]
  
 +
Сделаем так для всех полимино кроме первого столбца. Для него добавим специальное соединение, к которому подходит только зеркально отраженное полимино.
 +
 +
[[Файл:Polyomino_init_2.png]]
  
Значит задача о замощении полимино не разрешима.
 
 
}}
 
}}
  
 +
== Замощение целой плоскости ==
 +
 +
{{Теорема
 +
|statement=
 +
Задача о замощении целой плоскости полимино неразрешима.
 +
|proof=
 +
Аналогично замощению половины плоскости.
 +
}}
 +
 +
== См. также ==
 +
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ| Задача о выводе в полусистеме Туэ]]
 +
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]
 +
* [[M-сводимость | M-сводимость]]
 +
* [[Неразрешимость исчисления предикатов первого порядка]]
 +
 +
== Источники информации ==
 
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%BC%D0%B8%D0%BD%D0%BE Полимино — Википедия]
 
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%BC%D0%B8%D0%BD%D0%BE Полимино — Википедия]
 +
* [https://www.cs.duke.edu/courses/fall08/cps234/projects/tilings.pdf The tiling problem]
 +
* [http://www.univ-orleans.fr/lifo/Members/Nicolas.Ollinger/talks/2008/03/turku.pdf The domino problem]
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Примеры неразрешимых задач]]

Версия 19:40, 8 января 2017


Определения

Определение:
Полимино (англ. polyomino) — плоская геометрическая фигура, состоящая из [math]n[/math] одноклеточных квадратов, соединенных по сторонам.
Polyomino example.png


Определение:
Замощение плоскости (англ. tiling) — представление плоскости в виде множества непересекающихся полимино.

Пусть дана плоскость [math]S[/math] и набор полимино [math]P[/math], если [math]\exists ~ f: N \times N \to P[/math] (говорящая по клетке, какому полимино она соответствует) тогда считается, что можно замостить плоскость [math]S[/math] данным набором.

Замощение четверти плоскости

Задача:
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много. Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.


Теорема:
Задача о замощении четверти плоскости полимино неразрешима.
Доказательство:
[math]\triangleright[/math]

Сведём задачу останова к данной задаче. Пусть дана машина Тьюринга [math]M =\langle \Sigma, Q, \Pi, B \in \Pi, s,\delta: Q \times \Pi \rightarrow Q \times \Pi \times \{ \leftarrow, \downarrow, \rightarrow \} \rangle[/math] и слово [math]w \in \Sigma^*[/math]. Требуется определить, остановится ли данная МТ на входе [math]w[/math].

Для того, чтобы доказать неразрешимость задачи о замощении, для заданной машины Тьюринга [math]M[/math] и слова [math]w[/math] построим набор полимино, которым можно замостить четверть плоскости, если МТ не остановится на заданном слове. Если же МТ останавливается, то четверть плоскости полученным набором замостить невозможно.

Будем эмулировать процесс выполнения МТ на входе [math]w \in \Sigma^*[/math] путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения. Первый ряд эквивалентен начальной конфигурации МТ, а каждый следующий ряд соответствует следующей конфигурации. Говоря простым языком, каждый ряд представляет из себя "снимок" состояния машины на соответствующем этапе выполнения.

Polyomino init.png

На рисунке сверху изображены два вертикальных ряда полимино. Первый ряд соответствует МТ и слову [math]w[/math]. Первое полимино соответствует паре из первого символа и начального состояния, все остальные — символам из [math]w[/math]. Во втором ряду второе полимино соответствует паре из символа [math]w[2][/math] и состояния [math]q[/math]. То есть МТ сделала переход [math]\delta (s, w[1]) = \langle q, w[1], \rightarrow \rangle[/math].

Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид:

Polyomino gen.png

На каждой стороне такого полимино находится определенное число выступов/впадин. Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить [math]k \leqslant |\Pi| + |Q| + |\Pi \times Q| + 1[/math]) – это и будет количество выступов/впадин, находящихся на одной стороне полимино.


Сначала построим набор полимино, который задаёт начальную конфигурацию:

Polyomino start.png

где [math]*i[/math] – уникальное число для каждой смежной пары полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда.

Далее строим полимино для всех элементов алфавита [math]c \in \Pi[/math]:

Polyomino alph.png

В нем количество впадин слева равно количеству выступов справа. Такой тип полимино передает содержимое ленты МТ следующему ряду.

Теперь построим полимино для функции перехода [math]\delta (q, c) = \langle p, d, D \rangle [/math], где [math]q \in Q, p \in Q, c \in \Pi, d \in \Pi, D\in \{\leftarrow, \downarrow, \rightarrow \}[/math]:

Polyomino delta.png

На рисунке изображены (снизу вверх) полимино соответствующие значениям [math]D = \{\leftarrow, \downarrow, \rightarrow \}[/math]. Вместе со следующим типом они эмулируют перемещение головки МТ.

Далее построим следующий тип полимино:

Polyomino delta2.png

Эти полимино получают на вход символ алфавита [math]c[/math] от предыдущего ряда и состояние [math]p[/math] от соседнего полимино, а затем передает следующему ряду пару из состояния и символа.

Построим последний тип полимино, характеризующих состояния [math]\#_Y[/math] и [math]\#_N[/math]:

Polyomino halt.png

Такое полимино имеет уникальное число выступов справа. Ни одно другое полимино из полученного набора не сможет к нему присоединиться, и процесс дальнейшего замощения будет невозможен.


Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.

Таким образом, четверть плоскости можно замостить тогда и только тогда, когда закодированная МТ не останавливается на данном входе. Иными словами, есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.

Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения. Значит задача о замощении полимино не разрешима.
[math]\triangleleft[/math]

Замощение половины плоскости

Теорема:
Задача о замощении половины плоскости полимино неразрешима.
Доказательство:
[math]\triangleright[/math]

Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.

Например, можно сделать новое количество выступов/впадин [math]k' = \mathrm{cur_k} + \mathrm{max_k}[/math], где [math]\mathrm{cur_k}[/math] — количество выступов/впадин у полимино, от которого образовалось текущее, [math]\mathrm{max_k}[/math] — максимальное число выступов/впадин у полимино в первой четверти.

Polyomino bad case.png

Сделаем так для всех полимино кроме первого столбца. Для него добавим специальное соединение, к которому подходит только зеркально отраженное полимино.

Polyomino init 2.png
[math]\triangleleft[/math]

Замощение целой плоскости

Теорема:
Задача о замощении целой плоскости полимино неразрешима.
Доказательство:
[math]\triangleright[/math]
Аналогично замощению половины плоскости.
[math]\triangleleft[/math]

См. также

Источники информации