9
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1. Especially for the hyperlink which probably applies here as well. However, I tried to contribute an "intuitive" analysis as an alternative answer anyway. $\endgroup$ – Jirka Hanika Dec 5 '17 at 10:16
6
$\begingroup$

The Rice theorem says that you can't tell anything about the ultimate behavior of a program when it is left to run to infinity - no matter how you classify programs, there will be two programs that will converge to the same ultimate behavior (computed function) although you classified them differently.

But letting the programs run to infinity is essential. To find out what they do in the first $n$ steps, you could just simulate them for the first $n$ steps and then terminate giving your verdict on how the program behaved. Similar simulation till infinity doesn't work because if the simulated program never terminates on a simulated input, your classifier will diverge as well, instead of providing a classification.

$\endgroup$
5
$\begingroup$

First, the words in your language aren't encodings of machines, they contain more information, so you can't directly apply Rice theorem. That said, Rice's theorem talks about the impossibility of reasoning about the function computed by a Turing machine (namely, whether it lies in some set $S$). This is not the case here, since as Raphael mentioned, there exist two machines $M,M'$ who compute the same function, but one lies in your language and the other doesn't (here I am ignoring the syntactical issue, and forget about the fact that $x,n$ are part of the input). The point is that the property you are looking at here is mechanical, and not semantic (the machines may compute the same function, but in a different way).

$\endgroup$
  • $\begingroup$ The first argument is formalistic but correct. The second argument confuses me (I'm not sure that I could define localness/globalness rigorously; and I don't know what it means to compute a function "from a set of functions"). $\endgroup$ – Jirka Hanika Dec 5 '17 at 9:31
  • $\begingroup$ The first argument is indeed merely syntactic, as Raphael mentioned in his answer. The local/global issue was meant to indicate the difference between reasoning about the result on a single input vs all inputs (I did not mean it in a formal sense, it may mean something else in a different context). Computing a function from a given set simply means that you ask whether the function computed by $M_\alpha$ is in $S$. $\endgroup$ – Ariel Dec 5 '17 at 9:56
  • $\begingroup$ The Rice theorem does NOT require one to reason about the machine's behavior on all inputs. For example, it's impossible to classify programs based on whether they will ultimately accept when run on input "5". Or rather, you can define such a classification which ignores the behavior on most inputs just fine, but the classification is still not recursive. $\endgroup$ – Jirka Hanika Dec 5 '17 at 10:00
  • $\begingroup$ This was indeed confusing, since one can define $S$ to be the set of functions who output $1$ on some fixed input. Thanks for raising the issue. $\endgroup$ – Ariel Dec 5 '17 at 10:24
3
$\begingroup$

Rice's theorem says that, for any nontrivial set $\mathcal{L}$ of languages, the set of Turing machines that recognize a language in $\mathcal{L}$ is undecidable. Wikipedia says that a specific language is decidable. So there's no contradiction.

$\endgroup$

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.