Turing machine depth-first search algorithm

  • Thread starter Nick93
  • Start date
  • #1
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:

Answers and Replies

Related Threads on Turing machine depth-first search algorithm

  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
5
Views
1K
Replies
9
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
2K
Replies
17
Views
3K
  • Last Post
Replies
2
Views
4K
Replies
1
Views
1K
Top