= <NAME> ДЗ 2

#set par(
  justify: true,
)

= Задача 1
Постройте (многоленточную) машину Тьюринга, возвращающую 1, если входное слово $x_1$ $x_2$ . . . $x_n$ ∈ ${0, 1}^*$ является палиндромом (т. е. $x_1$  $x_2$ . . . $x_n$ = $x_n$ $x_(n−1)$ . . . $x_1$), и 0 в противном случае. Машина должна работать за время $O(n)$.

== Решение:
Машина переписывает входное слово на рабочую ленту, потом один курсор остатеся в конце переписанного слова на рабочей ленте, а на входной возвращается в начало, затем оба курсора начинают синхронное движение - на входной ленте сначала, на рабочей с конца слова, - сравнивая символы по одному, таким образом движентся через все слово, если путь пройден, то слово полиндром, если на каком-то шаге символы не совпадают, то выводи 0. Сложность - 3 полных прохода по слову в худшем случае (туда обратно при копировании и один проход при сравнении) - $O(n)$.

Пусть у нашей машины 3 ленты: входная, рабочая и выходная, куда просто запишем результат. 

$sum = {0, 1}$

$Gamma = {▷, ◁, \#, 1, 0}$

$Q = {q_0, q_"copy", q_"go_back", q_"compare", q_"f"}$

$delta:$
- $q_0 vec(▷, \#, \#) -> q_"copy" vec(, \#, \#) vec(+1, 0, 0)$
- $q_"copy" vec(x_i, \#, \#) -> q_"copy" vec(, x_i, \#) vec(+1, +1, 0)$  -- копируем слово на рабочую ленту; $x_i$ - i входной символ
- $q_"copy" vec(◁, \#, \#) -> q_"go_back" vec(, \#, \#) vec(-1, 0, 0)$ -- когда дошли до конца, возвращается
- $q_"go_back" vec(x_i, \#, \#) -> q_"go_back" vec(, \#, \#) vec(-1, 0, 0)$
- $q_"go_back" vec(▷, \#, \#) -> q_"compare" vec(, \#, \#) vec(+1, -1, 0)$ -- когда вернулись в начало, начинаем сравнение
- $q_"compare" vec(0, 0, \#) -> q_"compare" vec(, 0, \#) vec(+1, -1, 0)$
- $q_"compare" vec(1, 1, \#) -> q_"compare" vec(, 1, \#) vec(+1, -1, 0)$
- $q_"compare" vec(0, 1, \#) -> q_"f" vec(, 1, 0) vec(0, 0, 0)$  -- если символы разные, то записываем 0 в выходную ленту и завершаемся
- $q_"compare" vec(1, 0, \#) -> q_"f" vec(, 0, 0) vec(0, 0, 0)$

- $q_"compare" vec(◁, \#, \#) -> q_"f" vec(, 0, 1) vec(0, 0, 0)$ -- если дошли до конца, то записываем 1 в выходную ленту и завершаемся.



= Задача 2
Докажите, что множество вычислимых на одноленточных машинах Тьюринга функций не изменится, если разрешить машине любые целочисленные сдвиги (т. е. инструкции вида $q a arrow.r.bar q'a'n$, где $n$ — произвольное целое число; при этом «программа» $δ$ остается конечной). Достаточно описать, как эмулируется шаг «расширенной» машины на обыкновенной.

== Описание эмуляции:
Длина эмулируемого шага - своего рода параметр машины, он заранее задан для конкретной машины и конечен. Тогда мы можем перебрать n шагов через n внутренних состояний машины в качестве счетчика и шагнуть нужное количество раз. 

Например, пусть n = 5 и мы делаем шаг $q a_i arrow.r.bar q'a'_i n$, его эмуляция будет выглядеть следующим образом:
- $q a_i -> q_1 a'_i $ +1
- $q_1 a_(i+1) -> q_2 a_(i+1)$ +1  -- здесь $a_(i+1)$ - любой следующий символ на ленте, в том числе и \#
- $q_2 a_(i+2) -> q_3 a_(i+2)$ +1 
- $q_3 a_(i+3) -> q_4 a_(i+3)$ +1 
- $q_4 a_(i+4) -> q_5 a_(i+4)$ +1 
- $q_5 a_(i+5) -> q' a_(i+5)$ 0  -- останавливаемся на n символе и переходим в требуемое состояние.