Constructing a Turing Machine for the min function

  • Thread starter trash
  • Start date
  • #1
14
0

Homework Statement


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


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

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.
 

Answers and Replies

Related Threads on Constructing a Turing Machine for the min function

  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
2K
Replies
3
Views
2K
Replies
0
Views
1K
Replies
1
Views
5K
  • Last Post
Replies
3
Views
907
Replies
4
Views
457
  • Last Post
Replies
11
Views
1K
Replies
11
Views
949
Top