15
$\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).

Improve this question
$\endgroup$
3
  • $\begingroup$ 1) Do you assume a one-sided infinite tape? 2) What is Atm? $\endgroup$ Commented Aug 11, 2012 at 11:16
  • $\begingroup$ 1)Yes, 2)The acceptance problem. $\endgroup$ Commented Aug 11, 2012 at 12:06
  • $\begingroup$ Somewhat related Are all functions with constant space complexity in REG ? $\endgroup$ Commented Jul 21, 2016 at 7:37

2 Answers 2

Reset to default
12
$\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.

Improve this answer
$\endgroup$
5
  • $\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$ Commented Aug 11, 2012 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$ Commented Aug 12, 2012 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$ Commented Aug 12, 2012 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$ Commented Aug 12, 2012 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$ Commented Aug 12, 2012 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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ How do you account for nondeterministic machines? $\endgroup$ Commented Aug 11, 2012 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$ Commented Aug 12, 2012 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$ Commented Aug 12, 2012 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$ Commented Aug 12, 2012 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$ Commented Aug 12, 2012 at 16:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.