- #1

Nick93

- 1

- 0

## 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!

Last edited: