Turing machine depth-first search algorithm

[Nick93]

Homework Statement

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 ).

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!

 

[KataKoniK]

Thank you for your post regarding the construction of a Turing machine that checks for k-cycles in a graph. I would like to offer some guidance and suggestions for your attempt at a solution.

Firstly, I commend your effort in attempting to use a depth-first search algorithm to solve this problem. However, as you have mentioned, it may be challenging to implement this algorithm on a Turing machine due to the complexity of keeping track of all the necessary information on the tapes. Therefore, I would recommend considering a different approach.

One possible solution could be to use a Breadth-first search algorithm instead. This algorithm would require fewer tapes and may be easier to implement on a Turing machine. Additionally, you could also try breaking down the problem into smaller subproblems and using multiple Turing machines to solve each subproblem separately.

Another suggestion would be to try using a different representation of the graph, such as an adjacency list, which may be easier to work with on a Turing machine.

Lastly, I would suggest seeking help from other experts or colleagues in the field who may have more experience with this type of problem. Collaboration and exchanging ideas can often lead to more efficient and effective solutions.

I hope this helps and I wish you the best of luck in solving this problem.