1. The problem statement, all variables and given/known data On the tapes of Turing machine recorded the number of vertices (n) in the binary system, the length of the desired cycle - k (in binary), and the adjacency matrix of the graph. Required to construct a Turing machine, which checks for the cycles of k-length in the graph, and show that the running time (number of steps before the transition to the final state) is bounded above by a polynomial in the variable n (k dependence can be, but we are not interested in it ). 3. The attempt at a solution The search of k-cycle can be done with Depth-first search algorithm or by k multiply of our adjacency matrix(if we found not zero values on the diagonal after k multiplication, then we have cycle with k-length) I think that it will be too hard to multiple matrix k times at Turing Machine, so the depth-first search algorithm will be easier. But I didn't thought that it will be that hard to store everything in mind while writing it (even with comments), so guys I need any kind of help from you with it, pleeease. So here is the depth-first search algorithm (I know that it's bad and not finished at all, but my mind gets every time burst up, when I start to think about all moments): I decided to take 4 tapes(empirically come after tries with 3 tapes): 1st tape - adjacency matrix 2nd tape - for current vertex (not binnary, but it should be) 3rd tape - for the marked vertices (not binnary, but it should be) 4th - for the cycle long (not binnary, but it should be) m1: l0110*1010*1101*0010* // l - lambda - the beginning of everything written on tape,* - separates rows of matrix(shows end of a row) m2: l1111* m3: l1111* m4: l111* And I should synchronize these tapes, so how finnally how I tried to do it(there maybe some errors, because of different thought that visited me while going further and further): //q1 - tries to find adjacent vertex in row q1(0,1,1,1) -> q1(0,1,1,1)(R,R,S,S) q1(1,1,1,1) -> q2(1,1,#,1)(R,S,S,R) //q2 mark adjacent vertex in a row, goes further till * and then with help of q3 we get to the adjacent vertex m1,m2,m3(tapes): q2(0,1,#) -> q2(0,1,#)(R,S,S) q2(1,1,#) -> q2(1,1,#)(R,S,S) q2(*,1,#) -> q3(*,1,#)(R,L,R) m1,m2: q3(*,1) -> q3(*,1)(S,L) q3(*,l) -> q4(*,l)(S,R) //q4 - should be used for finding next adjacent vertex q4(0,1,1,1) -> q4(0,1,1,1)(R,R,S,S) q4(1,1,1,1) -> q5(1,1,1,1)(R,R,R,S) //q5 - checks if we used to be in this adjacent vertex or not m2,m3: q5(1,1) -> q5(.,1)(L,L) q5(l,1) -> q6(l,1)(R,R) // q6 - if we didn't use to be in current vertex q5(l,#) -> q7(1,#)(R,R) //q7 - if we used to be in current vertex ... From this moment I started to rebate, because I couldn't simply compile all of this in my hand even with comments, because I had to many thoughts, but all of them could be done only separately, I cannot see the whole picture of the right algorithm. Maybe anyone can help me with it or send ready depth-first search algorithm or matrix multiple algorithm (I didn't find them after 2 hours of searching at google and yahoo) Thank you all very much in advance!