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

Для начала, в конце слова поставим #. Вернёмся обратно до начала и возьмём первый элемент, отметим его штрихом, дойдём до первой звёздочки, его тоже отмечаем и идём направо до пустышки. Вместо пустышки поставим тот элемент, который запоминали. Вернёмся влево до отмеченной звёздочки и идём направо, берём первый не штрихованный элемент и доходим до первой звёздочки справа от этого элемента, а затем отмечаем эту звёздочку и идём направо до пустышки, ставим элемент, который запоминали. Когда взяли все первые элементы каждой строки, то идём направо до конца, вставим в конец звёздочку. Наш цикл продолжаем до тех пор, пока есть не заштрихованные элементы.