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

*From*: Jym <Jean-Yves.Moyen@xxxxxxxxxxxx>*Date*: Sun, 19 Mar 2006 10:01:23 +0100

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**:**How to use Rice Theorem to check if a function is undecidable or not?***From:*vmvictorvm

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

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

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

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

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

- Prev by Date:
**asymptotic analysis** - Next by Date:
**Particles flowing through a black box** - Previous by thread:
**Re: How to use Rice Theorem to check if a function is undecidable or not?** - Next by thread:
**Re: HEAP SORT** - Index(es):