2
$\begingroup$

$\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\}$

I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first is undecidable then building an instance of the first problem starting from the second, ie asking if a machine M that executes an input n stops after a time $f$$(n)$ is like asking if it stops at all and then M ⊆ HALT. However there is something that does not convince me in this demonstration because it seems quite naive and I don't think that this is enough to prove that this language is undecidable. In addition the exercise it is taken from a chapter of a text in which the oracles are introduced, is it possible to prove this language undecidable by means of oracles? I would appreciate your help, thanks.

$\endgroup$
4
$\begingroup$

You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $M$ belongs to your language then it also belongs to halt. But the converse doesn't hold, and $L \subseteq HALT$ doesn't imply anything about $L$ (for example, $\emptyset \subseteq HALT$, yet $\emptyset$ is decidable).

In other words, your proof doesn't work. It doesn't prove anything.

Your goal is to show that using an oracle to $L$ (your language), you can decide the halting problem; hence if $L$ were decidable, then so would HALT be, contrary to the known fact that HALT isn't decidable.

In fact, we can show that $L$ is coRE-hard. This means that there is a computable reduction that takes a description of a Turing machine $M$ and outputs a description of another Turing machine $M'$ such that:

  1. If $M$ halts on the empty input then $M'$ doesn't run in time $f(n) := 100n^3 + 300$.
  2. If $M$ doesn't halt on the empty input then $M'$ does run in time $f(n)$.

The construction goes as follows. On input of length $n$, $M'$ simulates $M$ on the empty input for $g(n)$ steps, where $g(n)$ is a function to be determined, which tends to infinity. If $M$ halts within $g(n)$ steps, $M'$ goes into an infinite loop, and otherwise $M'$ halts. We choose $g(n)$ so that the simulation runs in time $f(n)$. (Depending on the exact Turing machine model, we might be able to take $g(n) = n$ or so.)

If $M$ doesn't halt then, by construction, $M'$ also halts within $f(n)$ steps. If $M$ does halt, then for large enough $n$, $M'$ will never halt, and in particular won't halt within $f(n)$ steps.

The language $L$ is also coRE: we can enumerate machines not in $L$ by running all machines on all inputs, and outputting the description of a machine once it doesn't stop within $f(n)$ steps on some input of length $n$. This shows that $L$ is coRE-complete.

$\endgroup$
  • $\begingroup$ thank you for your exhaustive answer. I easily understood the demonstration of the belonging of the language to coRE but i miss the exact point in which the undecidability of L is proved and in particular the way in which this is established through oracles ... $\endgroup$ – Yamar69 May 23 at 19:12
  • 1
    $\begingroup$ It’s not established through oracles. It’s established through a many-one reduction, which is a much weaker notion. $\endgroup$ – Yuval Filmus May 23 at 19:14

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.