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: Constructing a Turing Machine for the min function

  1. Sep 16, 2014 #1
    1. The problem statement, all variables and given/known data
    I'm trying to construct a Turing machine that after receiving two integers [itex]x,y[/itex] gives back the smaller one (or any of them if they are equal).

    2. Relevant equations
    I cannot use anything besides zeros and ones (I have seen that some people make turing machine using letters to keep track of the cursor). The infinite tape has only zeros, the inputs [itex]x,y[/itex] are given by the same quantity of 1's separated by a zero.
    Example: A input for [itex]min(x,y)[/itex] with [itex]x=4,y=3[/itex] would be [itex]\dots 00011110111000\dots[/itex] with infinite zeros on both sides of the tape.

    The result here would be [itex]\dots 0001111000\dots[/itex] with the cursor in the first one (standard position). This string can appear anywhere, there is no need for the former entries to be deleted.

    3. The attempt at a solution

    I haven't found a way to develop a proper algoithm to do what I want. My main idea was first copy both inputs, then in the copy take a [itex]1[itex] from the second input, take it to first non-zero entry of the first input in the copy and make it zero. If the second input is bigger than the first one the cursor will hit a [itex]1[itex] and the zero separating the inputs, otherwise it will hit a zero. In the first case I would return the cursor standard position of the original first input, in the second case the first entry is bigger or equal to the second one so I can move to the standard position of the second input.

    That's the my idea, but I have some problems to give a model since dealing with the copy machines and then going back to the original inputs is something I have some problems to figure out the way to do it.
  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