Turing machine for unary encoded quadratic numbers

Question

I want to design a turing machine that accepts strings of the form $0^{n^2}$ where $n \geq 1$ and I want to give an implementation description for this. So I am thinking that the algorithm can go something like this: If we have $0^{1^2}$, we can just cross off that only $0$ and accept. If we have $0^{2^2}$, we can first scan and cross off two zeros and then scan again and cross off the last two zeros since there are four zeros total. And then for $0^{3^2}$, we have $9$ zeros, so in three scans we can just cross off three zeros.

So can anyone tell me if I have the right idea and how I can put this into an implementation description? What I can't think of is, how would it know though that it has just one zero, or 4, or 9, or 16 and so on?

Answer 1

A hint: $n^2 = 1 + 3 + 5 + 7 + \dots + (2n-1)$.

Answer 2

Imagine writing a "real" program like this:

boolean isQuadratic(String s) {
  if ( s == "0" )
    return true
  else if ( s == "00" )
    return true
  else if ( s == "000" )
    return true
  else if ...
    ...
  else
    return false
}

It's pretty clear that this can not work: there are infinitely many else if statements so you do not get a program at all. The same problem arises for Turing machines.

Think about how you would solve the problem in procedural pseudo code, without using high level API/abstractions, and working on an infinite tape (instead of getting a string of fixed length). Then translate this idea into the formalism of Turing machines.

Answer 3

I think your idea is workable (though there are other ways to do it), but there is still some work to be done to take care of "details".

But first, in order to use your idea, you have to know what is the value of $n$ for your input. And you do not know, and have no simple way to know. So you use the great trick of automata theory: you guess. You guess by using non-determinism. The first thing the automaton does is to enter a state where it write a sting of symbols $a$ on the tape. The state has non deterministic transitions so that it switches to a new state at some point, after writing some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols $O$.

You must keep carefully your string $a^n$ since it is your reference number for the computation. But you can use the TM to make as many copies as needed, using different symbols to avoid confusion. Basically, you will need one copy $b^n$ to implement a loop counter that erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you think hard.

And this is already help beyond a simple hint.

As stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to use non-determinism to guess (and check) ... and that makes life so much easier in automata theory.