0

Rice's theorem says that there is no computable method F(m,p) to determine, if given as input a TM m, and some non-trival property p, if the language accepted by m has property p. To quote another source, "...you can infer from Rice's Theorem [that]... it is undecidable to determine whether a given TM accepts a finite or infinite number of inputs. It is undecidable to determine whether a given TM accepts only prime numbers, and so on."

Are there any results related to Rice's Theorem, but pertaining specifically to when m is only allowed to run a finite number of steps C (possibly expressed in code as some function, possibly exponential, of the actual length of m).

I understand this rules out infinite loops. But considering the two examples from the first paragraph, how would you determine if an arbitrary TM even without endless loops accepted a finite or infinite number of inputs. Same with determining if it accepts only primes.

Actually, to correct the first paragraph above, I guess Rice is saying that even if the property being checked is constant (i.e. not an arbitrary input p as described) F its still undecidable. And certainly it's undecidable when p is arbitrary input. And I'm also thinking if p is arbitrary input, something like Rice's theorem would apply even if m was only allowed to run a finite number of steps (which I'm thinking may not apply to a constant P). Any results out there pertaining to this.

Of course if the number of steps C is really small, like 1, 2 or 3, that's very different from say, C > 1000.

Bill Cody
  • 33

3 Answers3

2

I will answer what I think your question is, though I could just be talking past you here.

As long as you have an actual fixed bound (possibly a recursive function of the input) on the finite number steps you are allowed to run, then all your checks become recursive: The procedure just runs the machine on the input for as many steps as allowed, and then examines what happened.

As an aside, I don't think it helps to think of the property $p$ as a variable as you do. You can identify a property that a collection of objects can or can fail to have, with a subset of that collection, and, you certainly can't try to give a Turing machine a set and expect anything to happen.

The way I think about Rice's theorem is in terms of index sets. A set $S\subseteq\mathbb{N}$ is an index set if for every $e \in S$, if $\varphi_e$ and $\varphi_i$ compute the same function (i.e. $e$ and $i$ code Turing machines which halt on precisely the same inputs, and agree with each other on everything they halt) then $i\in S$. An index set is our best way to try to talk about properties of recursive functions instead of the different ways you can program a computation of that function.

Anyway, with this Rice's theorem can be stated as: The only recursive index sets, are the empty set, and the set of all Turing machines.

With all this, you can see why Rice's theorem doesn't do anything when you do things like restrict to only computing for some bounded number of steps: Whether or not a particular Turing machine does some given thing in the first $k$ steps, is not a property of the function that Turing machine computes, it can depend on the particular implementation. Another good example is the class of Turing machines with $\leq n$ states, this is recursive, but it doesn't contradict Rice's theorem, as this is not an index set by the padding lemma.

James
  • 5,443
  • Still processing your reply, but skipped ahead to conclusion: "you can see why Rice's theorem doesn't do anything when you restrict to only computing for some bounded number of steps...Another good example is the class of Turing machines with ≤n states, it doesn't contradict Rice's theorem" Are you saying that even with a bound on the number of steps, Rice's theorem still holds? I was thinking there would have to be something related to Rice's theorem, but not Rice's theorem itself. It occurred to me that if the property p is "Accepts specific string S" is decidable if m steps are bounded. – Bill Cody Jul 04 '15 at 06:41
  • Please note my edit on the above comment, thx. – Bill Cody Jul 04 '15 at 06:49
  • But I think I'm getting it -- Rice's theorem does nor pertain to what m does not halt on anyway, as the language of m (which Rice's theorem addresses) only concerns what m does halt on. – Bill Cody Jul 04 '15 at 06:53
  • 1
    Rice's theorem always holds, as it is a true fact, you may or not be able to apply it because whatever you are dealing with doesn't satisfy the hypotheses of the theorem. So, both "$M$ halts on $n$" and "$M$ doesn't halt on $n$" are not recursive, and the proof is by Rice's theorem (note course, that if one of those properties is recursive, the other is, by just flipping all accepts and rejects). However "$M$ halts on $n$ in $\leq s$ steps" or "$M$ does not halt on $n$ in $\leq s$ steps" are both recursive properties, the proof is not by Rice's theorem, you must exhibit a procedure. – James Jul 04 '15 at 06:59
  • Just to be clear, I understand that in Rice's Theorem, a language property cannot allude to properties of the program M itself (e.g the number of steps it takes). But the question was if you stop M after C steps, and just look at what is in its output register (I'm actually thinking in terms of URM's, btw) does Rice's theorem or a variant apply to that scenario. If you stop M after C steps its still correlates to some M' that is not bounded like that. Hopefully we're not talking past each other. I'm wondering though if you need to edit your last comment, or if its correct as it stands. – Bill Cody Jul 04 '15 at 07:18
  • (I don't have enough rep pts to upvote, but will mark as answer if something drastically better doesn't materialize, thx) – Bill Cody Jul 04 '15 at 07:28
  • @BillCody: I upvoted for you. =) – user21820 Jul 04 '15 at 08:01
  • @BillCody: I gave an answer that shows that the interpretation of "finite" in your question matters. Your specification of the existence of a computable bound makes the answer "no" but it could have been "yes" if there was an uncomputable bound! – user21820 Jul 04 '15 at 10:33
  • James, re your last comment -- was giving you a chance to edit it as I was dubous of its content, but if you're still reading this, here's the problems: – Bill Cody Jul 04 '15 at 17:08
  • You say "both 'M halts on n' and 'M doesn't halt on n' are not recursive, and the proof is by Rice's theorem." If you're only allowing M to run a certain number of steps before aborting it (then reading output register) then 'M halts on n' and 'M doesn't halt on n' are both recursive. You say, " However M halts on n in ≤s steps' or 'M does not halt on n in ≤s steps' are both recursive" I never said the "n in ≤s steps" restriction was part of the property p, as it's not allowed in Rice theorem. – Bill Cody Jul 04 '15 at 17:15
  • user21820, will study your answer now. – Bill Cody Jul 04 '15 at 17:16
  • Also James, I'm not trying to disprove Rice's Theorem. I know it applies wherever it applies. My question was to what extent and with what modifications it applies in the specific scenario I described. – Bill Cody Jul 04 '15 at 17:32
1

I guess an important point you're missing is that the following restrictions on the number of steps allowed are different:

  • finite
  • bounded by some recursive function of the input
  • bounded by some recursive function of the program and the input

The second and third is enough for output behaviour to be decidable, because you can just compute the bound first before executing the program on the input for the number of steps given by the bound.

The first is not enough. Namely, the question is whether there is a decider that decides correctly whether a recursive program accepts a non-trivial language. This decider is allowed to answer incorrectly on non-recursive programs. But such a decider still cannot exist if "non-trivial" means "includes one recursive program and excludes one recursive program". And exactly the same proof below for the usual undecidability theorem works. I marked the modifications in square brackets.

Given any property $P$ on programs such that $P(M) = P(N)$ for any [recursive] programs M,N that have the same output behaviour (whether it halts and the output if it does) and [recursive] programs $T,F$ such that $P(T) = true$ and $P(F) = false$: $\def\qm{\operatorname{?}}$

  Given any recursive $D$ such that $D(M) = P(M)$ for any [recursive] $M$:

    Let $S = ( x \mapsto ( D( y \mapsto x(x)(y) ) \qm F : T ) )$.

    Then $S$ is recursive because constructing "$y \mapsto x(x)(y)$" is recursive and $D$ is recursive.

    Thus $S(S) = T$ or $S(S) = F$ [, and hence $S(S)$ is recursive].

    Also $S(S)$ and $y \mapsto S(S)(y)$ have equivalent output behaviour.

    Thus $S(S) = ( D( y \mapsto S(S)(y) ) \qm F : T ) = ( D(S(S)) \qm F : T ) = ( P(S(S)) \qm F : T )$.

    Thus $P(S(S)) = ( P(S(S)) \qm P(F) : P(T) ) = ( P(S(S)) \qm false : true ) = \neg P(S(S))$.

    Contradiction.

  Therefore there is no recursive $D$ such that $D(M) = P(M)$ for any [recursive] $M$.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • I'll just answer your post piecemeal as I read through it, if you don't mind. You say, "The second and third is enough for output behaviour to be decidable, because you can just compute the bound first before executing the program on the input for the number of steps given by the bound. The first is not enough" ----- Even the second and third are not enough if the property is something like, "only accepts primes" or "accepts a finite or infinite number of inputs" (see 3rd paragraph of OP). But if the property is "accepts some specific number N", then all three are recursive. – Bill Cody Jul 04 '15 at 18:36
  • My intuition for my purposes is to make C some humongous exponential function of say, the size of n and p combined. – Bill Cody Jul 04 '15 at 18:38
  • You say, "a decider still cannot exist if 'non-trivial' means 'includes one recursive program and excludes one recursive program'". You lost me here, because in the context of Rice's theorem "non-trivial" has a very specific meaning, namely, a property possessed by all TMs or by none of them. – Bill Cody Jul 04 '15 at 18:42
  • Edit to above: trivial (not non-trivial) means "a property possessed by all TMs or by none of them". (So non-trivial is the negation of that. Sorry). – Bill Cody Jul 04 '15 at 18:58
  • Nevermind, I see what you're saying regarding non-trivial. Let me just finish reading the whole thing, sorry. – Bill Cody Jul 04 '15 at 18:59
  • What if the number of steps C is just a constant value referenced in F, e.g. "986", "14000", "5" etc. That's would I take finite to mean (i.e. as opposed to some function of the size of m/input). I'm taking it you mean something different by "finite". But whether its a function or a constant value, it still gurantees m itself only runs a finite number of steps. – Bill Cody Jul 04 '15 at 19:09
  • @BillCody If you fix the number of steps independent of the size of the input, then there is a decidable characterization of the set of strings accepted by any machine $M$ within $C$ steps. Specifically, for any inputs $M,C$ this language is regular and we can compute a regex for it in doubly-exponential time. Thus we can decide whether it's finite or infinite, and we can answer the question about primes for most reasonable encodings. – Erick Wong Mar 16 '17 at 18:23
1

Maybe your question can be reformulated as follows: is there something like Rice's theorem, where not all Turing machines are allowed as inputs to the problem, but only the ones whose code explicitly make them halt after $2^n$ steps (or any computable fixed function of $n$)?

The answer is: yes, there is. It can be formulated more intuitively using programming languages rather than Turing machines. Take a programming language $P$ that has total programs only (programs halt on every input), and such that the set of valid programs is decidable. For instance, take the language consisting of primitive recursive definitions, or Turing machines with a clock that halts after $2^n$ steps on input $n$.

There is a characterization of the properties of functions that can be decided (by an arbitrary Turing machine), given a program in $P$ computing the function. Here are examples of decidable properties:

  1. Whether $f(0)=3$,
  2. Whether for all $n$ there is a program in $P$ of size at most $n$ that gives the same values as $f$ on inputs $0,1,\ldots,n$ (exercise!).

In 1. one can replace $0$ and $3$ by any other values. In 2. one can replace the size bound $n$ by $h(n)$ for any fixed increasing unbounded computable function $h$.

The characterization states that these are essentially the only decidable properties: the decidable properties are disjunctions of finite conjunctions of these basic properties.

So one can usually decide more than just particular values of the function (property 2. cannot usually be decided if one only has access to the values of $f$, rather than to a finite program in $P$), and the theorem precisely identifies the decidable properties. The precise statement of the result with the proof can be found here.

Mathieu
  • 11