1
$\begingroup$

Contruct a Turing Machine that halts if and only if the tape it is on contains at least two '1's.

My attempt:

The gist of this turing machine is that it has to check all of the cells, and since it is infinite in both directions, one way of indexing it is a follows

Turing indexing

Thus it has occurred to me to write a pseudocode for the TM's behaviour like this:

n:= 0           //number of '1's encountered
i:= 0           //index
while(true)
{
  if(n==2)
    halt
  for k=0 upto i
  {
    check()
    if(i even)
      move left
    if(i odd)
      move right
  }
  i++
}

Where check is the function defined as follows:

check()
{
if(current cell contains 1)
  n++
}

But this seems really hard to implement as a turing machine, especially since there are two variables involved. My guess is that I am overthinking and there is a much cleaner, nicer and elegant solution.

So my question is: What would be a better solution?

$\endgroup$
0
$\begingroup$

I managed to solve it in the end. If anyone is interested, I left a diagram of the TM here Turing Machine

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.