4
$\begingroup$

The language in question is $L = \{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\}$.

Attempt 1

Suppose $L$ is decidable. Let $M_1, M_2, \ldots$ be the Turing machines in $L$. Now construct a new Turing machine $M$ that works as follows:

  • on input of length $n$ run $M_n$ and output the opposite answer

On the one hand, $M \in L$ since it halts in the appropriate time. On the other hand, $M \notin L$ because it is different from every machine in $L$. Therefore $L$ is undecidable.

Is this correct?

Something that bothers me: I think I am only using the fact that there are countably many Turing machines; I never used the fact that there is some TM that decides $L$.

Attempt 2

As suggested, here's a new Turing machine $M'$:

M'(M,x,1^n):
    if M is not a valid Turing machine then halt
    otherwise
        run M(x) for 100n^2+200 steps
        if it halts, then run forever
        otherwise halt

Ask oracle: does $M'(M,x, 1^n)$ halt on all inputs within $100n^2+200$ steps?

If yes, then $M$ doesn't halt on input $x$.

If no, then some input causes it to loop forever, which means $M$ halted on $x$ in a certain amount of time.

This would allow us to decide the halting problem, which we know is undecidable.

Is this correct? If so, I still think of the details are a bit fuzzy... For example, it's a bit unclear to me as to what happens with the inputs $M$ and $x$ are very large...

$\endgroup$
  • $\begingroup$ Intuition: this problem answers a harder question than the regular Halting problem! $\endgroup$ – Raphael Dec 19 '16 at 12:13
  • $\begingroup$ You are right to be bothered; you don't have a proof. Hint: Given $M$, define a machine $M'$ so that $M'$ halts after at most 100n² + 200 steps if and only if $M$ halts at all. $\endgroup$ – Raphael Dec 19 '16 at 12:15
  • $\begingroup$ Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have little to work with. Let me direct you towards our reference questions which cover your problem in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Your question may then be reopened. Good luck! $\endgroup$ – Raphael Dec 19 '16 at 12:15
  • $\begingroup$ @Raphael I have added another potential solution based on your comment. $\endgroup$ – theQman Dec 19 '16 at 15:35
  • $\begingroup$ By the way, see here (and links there) as well as here. $\endgroup$ – Raphael Dec 19 '16 at 18:39
2
$\begingroup$

The fundamental reason for this is because your function $100n^2+200$ is $\Omega(n)$. Additionally, this result holds for any function $f\in\Omega(n)$.

Your problem is that you can't just "run $M_n$". It's possible to describe a turing machine that runs a specific machine, but to have the turing machine depend on the input requires that you actually compute the machine you're using. This is actually equivalent to the negation of what you are trying to prove, and additionally makes $M$ take longer so that it won't halt in the correct amount of time in the case that $M_n$ does even if you had an algorithm to find $M_n$.

Assuming you are using $M$ in your second attempt as a general TM rather than the one for attempt one, then the problem here is the same (except it's caused by the fact that the machine has to use some extra time to compute which step it's one rather than compute the machine it will simulate). Normally, this problem wouldn't come into play if you do $O(f(n))$ analysis because your new TM $M'$ would still run within a constant time factor of the old one, but in your problem you have to be a bit more clever.

If you know a bit of complexity theory, you can do that by using the linear speedup theorem, which basically says that given a TM which runs in at least linear time $f(n)$ you can create one with a constant factor $r>0$ as small as you'd like that runs in time $r\cdot f(n)$. The drawback is that the tape input is no longer just $0$'s and $1$'s but will also include some added symbols, but the same methods can prove this for any $f\in\Omega(n)$, so it's still a pretty neat result.

$\endgroup$
1
$\begingroup$

You can simply apply Rice's theorem, since the class of languages

$$\mathcal{S} = \{ L \mid L \; \text{is a language decided by a TM with time complexity } 100n^2 + 200 \}$$

is non-trivial.

$\endgroup$
  • 1
    $\begingroup$ Rice's theorem is not applicable, because the language $L$ is not a semantic property of Turing machines. In other words, $L$ from the OP is not the same as $\{M:\text{The language of $M$ is in $\mathcal S$}\}$. If the time bound in the OP is changed to some constant, the language $L$ becomes decidable but $\mathcal S$ is still non-trivial. $\endgroup$ – kne Mar 6 '18 at 15:28

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.