Re: How to use Rice Theorem to check if a function is undecidable or not?

On Sat, 18 Mar 2006 21:37:48 +0100, Joe Hendrix <jhendrix@xxxxxxxx> wrote:

Jym wrote:
Typical example of intensionnal property (in my sense) would be being
Ptime. This is clearly a property that depends on the program itself and
not on the function it computes.

Normally, PTIME is considered a property of languages, i.e. a language L
is in PTIME iff. there is a machine M and polynomial P(n) such that for
any string w, w \in L iff. M accepts w in time P(|w|).

Yes. Because we have a theory of functions/languages and not of algorithms/programs.

Of course, one could ask about whether a machine terminates on all
inputs in time equal to some polynomial of the input size, i.e., for a
machine M, decide if there is polynomial P(n) such that for all w,
M terminates in time P(|w|). But one does not normally write this as
PTIME. This property could be translated into a language property if we
consider languages over machines by defining a language LMP containing
machines with the polynomal termination property.

Just notice how the PTIMEness property (or other usaul complexity classes) is defined for languages/functions...

Let M \in PTIME_M be "there is a polynomial P such that for all w machine M terminates in P(|w|)".

Then we have L \in PTIME <=> \exists M \in PTIME_M deciding L.

Defining PTIME for languages requires one to use polynomial bounds on machines anyway, hence I believe it is rather logical to have a definitio of PTIME for machines that carry over to languages.

Moreover, any time one want to prove that a language belongs to PTIME, one (usually) build a machine belonging in PTIME_M as a proof... And that's also why finding lower bounds for languages complexity is so hard: you have to consider *all* machines computing the languages.

And when teaching algorithms, it always like "this program computes this function in time O(n log n),... hence we're speaking of complexities of machines again and not languages.

So, I agree that usually complexity classes are defined in terms of languages and not machines, but carrying the definition to sets of machines is both quite obvious and convenient.

--
Hypocoristiquement,
Jym.
.

• References: