Написать программу машины Тьюринга

Написать машину Тьюринга. На вход подаются слова в алфавите {a, b, c}, разделенные пустым символом. Необходимо отсортировать эти слова в лексикографическом порядке методом вставок, команды машины нужно пояснить.

Пример: на вход подаются слова "bac cac acc", машина должна вывести "acc bac cac", при этом важно, чтобы вывод начинался с той же ячейки на ленте, с которой были записаны входные слова.

Машину необходимо предоставить в виде команд следующего вида: "q0, a -> q1, b, +1", где q0 - состояние, в котором находится машина, a - символ, который она читает, q1 - состояние, в которое машина переходит, при прочтении буквы a в состоянии q0, b - то, что пишется на месте прочитанной буквы, +1 - то, куда сдвигается считывающее устройство (-1 на одну ячейку влево, 0 остаться на месте, +1 на одну ячейку вправа)

Пример команды: "q1, b -> q2, b, +1". При прочтении буквы b в состоянии q1 перейти в состояние q2, написать вместо b b, перейти на одну ячейку вправо. Если нужен пример какой-то машины, оформленной должным образом, сообщите, предоставлю

пустые символы обозначаются так - "/\" (как '^', только по центру ячейки и больше). Изначально считывающее устройство находится на первой букве первого слова.