# Show that the following language is undecidable

$$\{ 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.

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.

• 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 ... – Yamar69 May 23 '19 at 19:12
• It’s not established through oracles. It’s established through a many-one reduction, which is a much weaker notion. – Yuval Filmus May 23 '19 at 19:14