14
$\begingroup$

I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$.

For an integer $c>1$, and the following three problems:

  1. Is it true that for every input $x$, M does not pass the $|x|+c$ position when running on $x$?

  2. Is it true that for every input $x$, M does not pass the $\max \{|x|-c,1 \}$ position when running on $x$?

  3. Is it true that for every input $x$, M does not pass the $(|x|+1)/c$ position when running on $x$?

How many problems are decidable?

Problem number (1), in my opinion, is in $\text {coRE} \smallsetminus \text R$ if I understand correct since, I can run all inputs in parallel, and stop if some input reached this position and for showing that it's not in $\text R$ I can reduce the complement of Atm to it. I construct a Turing machine $M'$ as follows: for an input $y$ I check if $y$ is a history of computation, if it is, then $M'$ running right and doesn't stop, if it's not, then it stops.

For (3), I believe that it is decidable since for $c \geqslant 2$ it is all the Turing machines that always stay on the first cell of the stripe, since for a string of one char it can pass the first cell, so I need to simulate all the strings of length 1 for $|Q|+1$ steps (Is this correct?), and see if I'm using only the first cell in all of them.

I don't really know what to do with (2).

$\endgroup$
9
$\begingroup$

Any situation which asks whether a Turing Machine is confined to a finite section of the tape (say of length $n$) on a given input is decidable.

The argument works as follows. Consider the Turing Machine, the tape, and the position of the Turing Machine on the tape. All together these have a finite number of configurations. To be specific, there are only $t = n|\Gamma|^n|Q|$ possible configurations. $\Gamma$ is the set of tape symbols and $Q$ is the set of states. I'll continue to use the word "configuration" to describe the state of the Turing Machine combined with the state of the tape and its position on the tape for the remainder of this answer, but that is not standard vocabulary.

Run the machine, keeping track of all its past configurations. If it ever goes beyond point $n$, return "yes, $M$ passes position $n$". Otherwise, the machine is somewhere between 0 and $n$. If the machine ever repeats a configuration--its state, the symbols on the tape, and its position on the tape are identical to what they were before--return "no, $M$ never passes position $n$."

By the pidgeonhole principle, this has to happen in no more than $t+1$ steps. So all of the above is decidable; after at most $t+1$ simulated steps you get an answer.

A quick note on why this works: when the machine, the tape, and its position on the tape repeat themselves, there must have been a sequence of configurations between these repetitions. This sequence will happen again, leading to the same configuration one more time--the machine is in an infinite loop. This is because we're keeping track of every aspect of the Turing Machine; nothing outside of the configuration can have an impact on what happened. So when a configuration repeats, it will repeat again, with an identical series of configurations in between.

So confining the tape to a finite part of the string is decidable. Therefore, by iterating over all possible input strings, the problem is in $\text{coRE}$ for all three questions. You may have already realized this (between your ideas for 1 and 3 and Ran G's answer for 2 it seems solved completely anyway) but I figured it may be worth posting nonetheless.

$\endgroup$
  • $\begingroup$ "If the machine ever repeats a configuration [...] return 'no'" -- that is wrong. A nondeterministic machine might execute a loop a couple of times and then move on. $\endgroup$ – Raphael Aug 11 '12 at 23:36
  • 1
    $\begingroup$ We're talking about turing machines here which are not assumed to be nondeterministic. If it were nondeterministic, simulate the deterministic version. $\endgroup$ – SamM Aug 12 '12 at 0:44
  • $\begingroup$ Nice explanation. See also the first version of my answer (which I revise once I realized that the OP didn't quite ask it..) $\endgroup$ – Ran G. Aug 12 '12 at 1:26
  • $\begingroup$ @Sam: It works the other way round: unless otherwise assumed, a Turing machine may be nondeterministic. What is a "deterministic version"? If you mean a complete unfolding of choices, then a repeated configuration loses meaning as they may happen in different branches. $\endgroup$ – Raphael Aug 12 '12 at 9:06
  • 2
    $\begingroup$ @Raphael the standard way to do this is a configuration graph: the vertices are the same configurations that Sam defined, and there is a directed edge from configuration A to B if the NTM can move from A to B in a single step. The graph is finite and and whether the machine halts is a simple graph reachability question. This also shows that $\mathsf{NSPACE}(s)$ is a subset of $\mathsf{DTIME}(2^{O(s)})$ $\endgroup$ – Sasho Nikolov Aug 12 '12 at 10:27
4
$\begingroup$

(2) is very similar to (3) and the same reasoning you had for (3) applies here as well: note that machines that in $L_2$ have a strange property - they don't read the entire input (they never reach it's last $c$ bits.) And this is true for every input.

Ok, so now let's consider only inputs up to length $c$. For each one of them, there are only two options: the machine loops/halts w/o moving the head, or it moves the head. If it moves the head on some $x$ (with $|x|\le c$), that machine is not in $L_2$ due to that input $x$. Otherwise, I claim the machine is in $L_2$. Since it never moves the head - it has no idea what the size of the input is! this means it behaves the same for all the inputs of length $|x|>c$. Therefore, $L_2$ is decidable.

$\endgroup$
  • $\begingroup$ How do you account for nondeterministic machines? $\endgroup$ – Raphael Aug 11 '12 at 23:37
  • $\begingroup$ I didn't consider NTMs, but it should be quite the same. For all words of length up to $c$ the number of configurations the NTM can be in w/o moving the head is finite. $\endgroup$ – Ran G. Aug 12 '12 at 1:21
  • $\begingroup$ Yes, but your argument breaks down. You can not determine in finite time (by simple simulation) whether an NTM leaves a given position. $\endgroup$ – Raphael Aug 12 '12 at 9:08
  • $\begingroup$ @Raphael why not? can't you simulate the entire tree of configurations (of depth $|x|$) in a finite time $exp(|x|)$? $\endgroup$ – Ran G. Aug 12 '12 at 16:52
  • $\begingroup$ Why would depth $|x|$ be enough? $|Q|$ would make more sense. By then, the simulation has found a branch where $M$ leaves the first position, if there is any. $\endgroup$ – Raphael Aug 12 '12 at 16:55

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.