Rice's Theorem when only finite number of instructions run

Question

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.

Answer 1

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.

Answer 2

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