1
$\begingroup$

I'm kind of new to the theory of computation and I was working on this problem:

We say that a Turing machine $M$ uses $k$ squares of tape for an input string $w$ if and only if there exists a configuration $(q, u\underline{a}v)$ of $M$, such that starting with input $w$, $M$ yields $(q, u\underline{a}v)$ and $|uav| \geq k$.

Now show that the following problem is solveable: Given a Turing machine $M$, an input string $w$ and a number $k$ does $M$ use $k$ squares of tape with input $w$?

So the solution I came up with is this:

If it is solvable there has to be a Turing machine $M^*$ that decides $$U = \{\ll M\gg\ll w \gg \ll k\gg\ :M\ \text{uses}\ k\ \text{squares of tape with input}\ w\}$$

And I describe such a machine:

$M^*$ writes in it's tape $w$ and starts operating as $M$ would. After each step of $M$, $M^*$ counts the number consecutive squares of tape from the start of the tape until it finds an empty square, and if that number is $\geq k$ it goes into an accept state and halts. If not, it continues its operation as M would. If $M$ halts without having used at least $k$ steps, $M^*$ goes into a reject state. So $M^*$ decides $U$, and thus the problem is solveable.

So my questions are these:

Is my solution correct?, and

Is my description of $M^*$ precise, or say, good enough?

$\endgroup$
2
$\begingroup$

You are asking two different questions: whether your solution is correct, and whether the level of description of your Turing machine is appropriate. I will answer them separately.

Correctness Your Turing machine $M^*$ is not guaranteed to halt. In other words, your solution is incorrect. The missing observation is that if a Turing machine uses only space $k$, then there is an upper bound on the number of steps that it can run without getting into an infinite loop.

Level of description Here you should be asking two questions:

  1. What does it mean to describe a Turing machine?
  2. How do I prove that a certain language is decidable?

The level of description of Turing machines is a touchy subject. Usually they are described quite informally. The level of description should be such that in principle you could convert the informal description into a formal Turing machine. In practice, I suggest looking at some examples to get the general feel.

As to how to prove that a language is decidable, there is no need to describe a Turing machine. Decidability can be proved using any model of computation. In particular, you can use the "English" model of computation, in which you describe how to decide the problem in the English language (or in any other language). For example, you could say "Simulate $M$ on $w$, and if it ever uses more than $k$ space, immediately reject; otherwise, once $M$ halts, accept". (This is just your incorrect solution.)

$\endgroup$
  • $\begingroup$ Thanks for the answer! I get what you say for the level of description question, but I don't quite understand why my solution to the problem is incorrect. Could you maybe explain it a bit differently? $\endgroup$ – Da Mike May 5 at 16:58
  • $\begingroup$ Your machine won’t halt if $M$ used the correct amount of space but never halts. $\endgroup$ – Yuval Filmus May 6 at 0:44
  • $\begingroup$ So basically you say that if $M$ never uses $k$ spaces and runs forever my machine $M^*$ will never halt, right? Then I guess if $M$ is not recurisve, then the problem is not solvable. But the exercise I'm working on says to prove that it is solvable. So maybe they forgot to add that $M$ is recursive in the description of the exercise? $\endgroup$ – Da Mike May 6 at 8:23
  • $\begingroup$ The problem is perfectly solvable, just not with your solution. $\endgroup$ – Yuval Filmus May 6 at 11:08
  • 1
    $\begingroup$ That's the entire point of the question. I gave one possible option in the answer. Another possible option is to store all configurations of $M$, and to stop if a configuration repeats. Eventually either $M$ will use more than $k$ space, or a configuration will repeat. $\endgroup$ – Yuval Filmus May 6 at 13:46

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.