Изменения

Первый ряд заполняется начальной конфигурацией, а каждый следующий ряд соответствует следующей конфигурации.

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

На каждой стороне такого полимино находится определенное число выступов/впадин.

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

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

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

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

Теперь построим полимино для функции перехода <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>D = \{\leftarrow, \downarrow, \rightarrow \}</tex>. Вместе со следующим типом они эмулируют перемещение головки МТ.

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

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

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

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