Машина Тьюринга для транспонирования булевых матриц

Условие 2
Принцип работы 2
Точный алгоритм работы 3
Текст программы с комментариями и доказательством 4
Таблица состояний 12
Протокол вычисления для заданного аргумента 14
Подсчёт времени 18

Квадратная матрица m×m A=(a_ij), a_ij∈{0,1}, представляется перечислением строк, разделённых символом *.
Вход имеет вид: a_11 a_12…a_1m*a_21 a_22…a_2m*…*a_m1 a_m2…a_mm
Выход: транспонированная матрица AT в виде
a_11 a_21…a_m1*a_12 a_22…a_m2*…*a_1m a_2m…a_mm

Текст программы с комментариями и доказательством

Начало цикла q1. Предположим, что i-1 строк AT сформировано. Формируем i-тую строку AT. Для этого нужно взять i-ые элементы из каждой строки A (то же самое, что i столбец). Ищем первую незаменённую цифру. Так как заменённые цифры обозначены буквами, то ищем просто цифру. Найденную цифру помечаем как стоящую на своём месте, буквой, потому что это всегда элемент главной диагонали.
q11->q2aR
q10->q2bR
q1c->q1cR
q1d->q1dR
q1*->q1*R
Так как для формирования одной строки AT нужно взять один столбец A, то есть по одному элементу из каждой строки A, для формирования i-1 строк AT будет взято i-1 элементов из каждой строки A.
Лента изменится таким образом:
Было:
^
…………………….
*

……………………..
aij
…
aim
*
…
*
…
^

Станет:
^
…………………….
*

……………………..
aij
…
aim
*
…
*
…
^

/

Если встретилась пустышка, то больше нет необработанных цифр, и
осталось только сделать обратную замену букв на цифры.
q1^->q11^L
Здесь начинается цикл q2.
...

Таблица состояний

Если команды нет, оставлен комментарий.
...

Протокол вычисления для заданного аргумента

Вход: ^100*111*110^

Протокол вычисления (на ленте жирным курсивом с подчеркиванием выделено исходное состояние и вызванное им изменение):
q11->q2aR
q20->q20R
q20->q20R
q2*->q3*R
q31->q5aL
q5*->q5*L
q50->q50L
q50->q50L
q5a->q7aR
q70->q10aR
q100->q100R
q10*->q10*R
q10a->q2dR
q21->q21R
q21->q21R
q2*->q3*R
q31->q5aL
q5*->q5*L
q51->q51L
q51->q51L
q5d->q5dL
q5*->q5*L
q50>q50L
q5a->q7aR
q70->q10aR
q10*->q10*R
q10d->q10dR
q101->q101R
q101->q101R
q10*->q10*R
q10a->q2dR
q21->q21R
q20->q20R
q2^->q4^R
q40->q40L
q41->q41L
q4d->q4dL
q4*->q4*L
q41->q41L
q41->q41L
q4d->q4dL
q4*->q4*L
q4a->q1aR
q1*->q1*R
q1d->q1dR
q11->q2aR
q21->q21R
q2*->q3*R
q3d->q3dR
q31->q5aL
q5d->q5dL
q5*->q5*L
q51->q51L
q5a->q7aR
q71->q9aR
q9*->q9*R
q9d->q9dR
q9a->q2cR
q20->q20R
q2^->q4^L
q40->q40L
q4c->q4cL
q4d->q4dL
q4*->q4*L
q4a->q1aR
q1*->q1*R
q1d->q1dR
q1c->q1cR
q10->q2bR
q2^->q4^L
q4b->q1bR
q1^->q11^L
q11b->q110L
q11c->q111L
q11d->q110L
q11*->q11*L
q11a->q111L
q11a->q111L
q11d-.
...