1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Turing machine depth-first search algorithm

  1. Apr 15, 2013 #1
    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

    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)

    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

    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: Apr 15, 2013
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted