Вычисление определителя матрицы 3x3, состоящей из нулей и единиц

На вход подаётся строка из девяти символов. Например:

110101011

1 1 0
1 0 1
0 1 1

Результатом работы алгоритма является значение определителя. В вышеприведенном примере:

-2

// | - обозначение начала ленты
// _ - обозначение пустого символа
// ! - обозначение конечного состояния
// 0 - обозначение начального состояния
//
// перед началом работы машина Тьюринга имеет вид:
// | _ _ _ _ _ _ _ _... - полубесконечная лента
// ^0                   - позиция каретки и начальное состояние
//
// программа состоит из команд:
// состояние, символ -> новое состояние, новый символ, переход каретки
//
// переход каретки обозначается: < - влево, > - вправо


0,| -> 10,|,>

10,0 -> 100,0,<
14,0 -> 100,0,<
18,0 -> 100,0,<
21,0 -> 200,0,<
25,0 -> 200,0,<
26,0 -> 200,0,<
32,0 -> 300,0,<
33,0 -> 300,0,<
37,0 -> 300,0,<

42,0 -> 400,0,<
44,0 -> 400,0,<
46,0 -> 400,0,<
50,0 -> 500,0,<
55,0 -> 500,0,<
57,0 -> 500,0,<
61,0 -> 600,0,<
63,0 -> 600,0,<
68,0 -> 600,0,<

100,| -> 20,|,>
200,| -> 30,|,>
300,| -> 40,|,>
400,| -> 50,|,>
500,| -> 60,|,>
600,| -> 70,|,>

100,_ -> 100,_,<
200,_ -> 200,_,<
300,_ -> 300,_,<
400,_ -> 400,_,<
500,_ -> 500,_,<
600,_ -> 600,_,<

100,0 -> 100,0,<
200,0 -> 200,0,<
300,0 -> 300,0,<
400,0 -> 400,0,<
500,0 -> 500,0,<
600,0 -> 600,0,<

100,1 -> 100,1,<
200,1 -> 200,1,<
300,1 -> 300,1,<
400,1 -> 400,1,<
500,1 -> 500,1,<
600,1 -> 600,1,<

10,1 -> 11,1,>
14,1 -> 15,1,>
18,1 -> 19,1,>
21,1 -> 22,1,>
25,1 -> 26,1,>
26,1 -> 27,1,>
32,1 -> 33,1,>
33,1 -> 34,1,>
37,1 -> 38,1,>
42,1 -> 43,1,>
44,1 -> 45,1,>
46,1 -> 47,1,>
50,1 -> 51,1,>
55,1 -> 56,1,>
57,1 -> 58,1,>
61,1 -> 62,1,>
63,1 -> 64,1,>
68,1 -> 69,1,>

11,0 -> 12,0,>
12,0 -> 13,0,>
13,0 -> 14,0,>
15,0 -> 16,0,>
16,0 -> 17,0,>
17,0 -> 18,0,>
20,0 -> 21,0,>
22,0 -> 23,0,>
23,0 -> 24,0,>
24,0 -> 25,0,>
27,0 -> 28,0,>
28,0 -> 29,0,>
30,0 -> 31,0,>
31,0 -> 32,0,>
34,0 -> 35,0,>
35,0 -> 36,0,>
36,0 -> 37,0,>
38,0 -> 39,0,>
40,0 -> 41,0,>
41,0 -> 42,0,>
43,0 -> 44,0,>
45,0 -> 46,0,>
47,0 -> 48,0,>
48,0 -> 49,0,>
51,0 -> 52,0,>
52,0 -> 53,0,>
53,0 -> 54,0,>
54,0 -> 55,0,>
56,0 -> 57,0,>
58,0 -> 59,0,>
60,0 -> 61,0,>
62,0 -> 63,0,>
64,0 -> 65,0,>
65,0 -> 66,0,>
66,0 -> 67,0,>
67,0 -> 68,0,>

11,1 -> 12,1,>
12,1 -> 13,1,>
13,1 -> 14,1,>
15,1 -> 16,1,>
16,1 -> 17,1,>
17,1 -> 18,1,>
20,1 -> 21,1,>
22,1 -> 23,1,>
23,1 -> 24,1,>
24,1 -> 25,1,>
27,1 -> 28,1,>
28,1 -> 29,1,>
30,1 -> 31,1,>
31,1 -> 32,1,>
34,1 -> 35,1,>
35,1 -> 36,1,>
36,1 -> 37,1,>
38,1 -> 39,1,>
40,1 -> 41,1,>
41,1 -> 42,1,>
43,1 -> 44,1,>
45,1 -> 46,1,>
47,1 -> 48,1,>
48,1 -> 49,1,>
51,1 -> 52,1,>
52,1 -> 53,1,>
53,1 -> 54,1,>
54,1 -> 55,1,>
56,1 -> 57,1,>
58,1 -> 59,1,>
60,1 -> 61,1,>
62,1 -> 63,1,>
64,1 -> 65,1,>
65,1 -> 66,1,>
66,1 -> 67,1,>
67,1 -> 68,1,>

19,_ -> 110,_,>
29,_ -> 210,_,>
39,_ -> 310,_,>
49,_ -> 410,_,>
59,_ -> 510,_,>
69,_ -> 610,_,>

110,1 -> 110,1,>
210,1 -> 210,1,>
310,1 -> 310,1,>
410,1 -> 410,1,>
510,1 -> 510,1,>
610,1 -> 610,1,>
110,0 -> 110,0,>
210,0 -> 210,0,>
310,0 -> 310,0,>
410,0 -> 410,0,>
510,0 -> 510,0,>
610,0 -> 610,0,>
110,_ -> 100,1,<
210,_ -> 200,1,<
310,_ -> 300,1,<
410,_ -> 400,0,<
510,_ -> 500,0,<
610,_ -> 600,0,<

70,1 -> 70,_,>
70,0 -> 70,_,>
70,_ -> 85,_,>

84,0 -> 83,_,>
84,1 -> 85,_,>
85,0 -> 84,_,>
85,1 -> 86,_,>
86,0 -> 85,_,>
86,1 -> 87,_,>
87,0 -> 86,_,>
87,1 -> 88,_,>
88,0 -> 87,_,>

83,_ -> 83,_,<
84,_ -> 84,_,<
85,_ -> 85,_,<
86,_ -> 86,_,<
87,_ -> 87,_,<

83,| -> 803,|,>
803,_ -> 813,-,>
813,_ -> 823,2,<
823,- -> !,-,<

84,| -> 804,|,>
804,_ -> 814,-,>
814,_ -> 824,1,<
824,- -> !,-,<

85,| -> 805,|,>
805,_ -> !,0,<

86,| -> 806,|,>
806,_ -> !,1,<

87,| -> 807,|,>
807,_ -> !,2,<