patternMinor
is L = {<M> | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?
Viewed 0 times
suchthatstackoverflow
Problem
L is the language of all turing machines that its computing time on all inputs is O(n^2).
my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make sure that there is no word W such that M halts on it after n^2 steps, you need to scan all words in the universe - infite search....
However, is the language in CO-RE ?
my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make sure that there is no word W such that M halts on it after n^2 steps, you need to scan all words in the universe - infite search....
However, is the language in CO-RE ?
Solution
This problem is not in RE nor in coRE.
First, your intuition that it's not in RE is correct, although note that very crucially - it's just an intuition, and not a direction for a proof!
However, your intuition breaks down for co-RE due to the specification being $O(n^2)$ and not $n^2$ exactly.
Let's start by proving that the language is not in coRE, by a reduction from $HALT_{TM}=\{\langle M,w \rangle: M$ halts on $w\}$.
Given input $\langle M,w \rangle$, the reduction outputs $\langle D \rangle$, where $D$ is a TM that given input $x$, ignores it and simulates $M$ on $w$. I'll leave it to you to prove correctness, but note that if $M$ halts on $w$, then it does so in constant time (i.e. independent of $x$, of course). Use this and the asymptotic notation $O(n^2)$ to conclude correctness.
Proving that the language is not in RE is a bit trickier. The reduction itself is quite standard. We reduce from $HALT_{\overline{TM}}=\{\langle M,w \rangle: M$ does not halt on $w\}$.
Given input $\langle M,w \rangle$, the reduction outputs $\langle K \rangle$, where $K$ is a TM that given input $x$, computes the length $|x|$, and then simulates the run of $M$ on $w$ for $|x|$ steps. If $M$ halts on $w$ during this time, $K$ goes into a non-halting loop. Otherwise, $K$ halts.
The correctness of this reduction is based on the observation that computing $n=|x|$ can be done in time $O(n\log n)$, and that simulating $M$ on $w$ for $n$ steps also takes $O(n\log n)$ time. This is not trivial, and follows by a clever use of a universal TM.
First, your intuition that it's not in RE is correct, although note that very crucially - it's just an intuition, and not a direction for a proof!
However, your intuition breaks down for co-RE due to the specification being $O(n^2)$ and not $n^2$ exactly.
Let's start by proving that the language is not in coRE, by a reduction from $HALT_{TM}=\{\langle M,w \rangle: M$ halts on $w\}$.
Given input $\langle M,w \rangle$, the reduction outputs $\langle D \rangle$, where $D$ is a TM that given input $x$, ignores it and simulates $M$ on $w$. I'll leave it to you to prove correctness, but note that if $M$ halts on $w$, then it does so in constant time (i.e. independent of $x$, of course). Use this and the asymptotic notation $O(n^2)$ to conclude correctness.
Proving that the language is not in RE is a bit trickier. The reduction itself is quite standard. We reduce from $HALT_{\overline{TM}}=\{\langle M,w \rangle: M$ does not halt on $w\}$.
Given input $\langle M,w \rangle$, the reduction outputs $\langle K \rangle$, where $K$ is a TM that given input $x$, computes the length $|x|$, and then simulates the run of $M$ on $w$ for $|x|$ steps. If $M$ halts on $w$ during this time, $K$ goes into a non-halting loop. Otherwise, $K$ halts.
The correctness of this reduction is based on the observation that computing $n=|x|$ can be done in time $O(n\log n)$, and that simulating $M$ on $w$ for $n$ steps also takes $O(n\log n)$ time. This is not trivial, and follows by a clever use of a universal TM.
Context
StackExchange Computer Science Q#88956, answer score: 5
Revisions (0)
No revisions yet.