patternModerate
The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?
Viewed 0 times
thisproblemwhythewithhaltingdecidabledoesntheoremconflict
Problem
One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak):
A partial function from $\{0,1\}^$ to $\{0,1\}^$ is a function that is not necessarily defined on all its inputs. We say that a TM $M$ computes a partial function $f$ if for every $x$ on which $f$ is defined, $M(x) = f(x)$ and for every $x$ on which $f$ is not defined $M$ goes into an infinite loop when executed on input $x$. If $S$ is a set of partial functions, we define $f_S$ to be the boolean function that on input $\alpha$ outputs 1 iff $M_\alpha$ computes a partial function in $S$. Rice's theorem says that for every nontrivial $S$, the function $f_S$ is not computable.
Wikipedia states that languages of bounded time turing machines are EXPTIME complete. I expect this language looks something like $\{(\alpha,x,n) : M_\alpha $ accepts $x$ in less than $n$ steps$\}$. So let $M$ be some DTM that decides this bounded language in exponential time. It seems like this DTM is deciding some property for ALL turing machines, so my intuition tells me that Rice's theorem precludes such a decision. But obviously $M$ computes a total function.
What am I missing about the relation between this language and Rice's theorem?
A partial function from $\{0,1\}^$ to $\{0,1\}^$ is a function that is not necessarily defined on all its inputs. We say that a TM $M$ computes a partial function $f$ if for every $x$ on which $f$ is defined, $M(x) = f(x)$ and for every $x$ on which $f$ is not defined $M$ goes into an infinite loop when executed on input $x$. If $S$ is a set of partial functions, we define $f_S$ to be the boolean function that on input $\alpha$ outputs 1 iff $M_\alpha$ computes a partial function in $S$. Rice's theorem says that for every nontrivial $S$, the function $f_S$ is not computable.
Wikipedia states that languages of bounded time turing machines are EXPTIME complete. I expect this language looks something like $\{(\alpha,x,n) : M_\alpha $ accepts $x$ in less than $n$ steps$\}$. So let $M$ be some DTM that decides this bounded language in exponential time. It seems like this DTM is deciding some property for ALL turing machines, so my intuition tells me that Rice's theorem precludes such a decision. But obviously $M$ computes a total function.
What am I missing about the relation between this language and Rice's theorem?
Solution
The language
$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$
is not an index set, that is it is not of the form
$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$
for some set of (partial recursive) functions $P$, with $f_M$ the (partial) function computed by TM $M$. Rice's theorem makes statements only about such $L_P$; many "intuitive" rephrasings are not helpful. See also here.
Note that this is not only a technical detail here. Rice's theorem does not apply to
$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$,
either. Can you see why?
For every machine in $L$ you can easily construct many machines that accept the same language but run for more than $\langle M \rangle$ steps, and thus are not in $L$. Thus, $L$ is not an index set.
$L$ is decidable, using the same argument as for the original language we're discussing.
$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$
is not an index set, that is it is not of the form
$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$
for some set of (partial recursive) functions $P$, with $f_M$ the (partial) function computed by TM $M$. Rice's theorem makes statements only about such $L_P$; many "intuitive" rephrasings are not helpful. See also here.
Note that this is not only a technical detail here. Rice's theorem does not apply to
$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$,
either. Can you see why?
For every machine in $L$ you can easily construct many machines that accept the same language but run for more than $\langle M \rangle$ steps, and thus are not in $L$. Thus, $L$ is not an index set.
$L$ is decidable, using the same argument as for the original language we're discussing.
Context
StackExchange Computer Science Q#84945, answer score: 14
Revisions (0)
No revisions yet.