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.


Relevant Pages

  • Re: Interesting bug
    ... >which the C64 derived). ... >So structured BASIC existed on the C64 or similar machines. ... the possibility of implementing structured programming languages on such ... Merely the practicality of having such implementations in the ...
  • Re: A 21st Century Apple II?
    ... It's certainly a benefit of resource constrained machines that quality ... when you consider total cost. ... It's also responsible for popularising many of the architectural ... since languages in popular use prior to that lacked ...
  • Re: suggest a new Star Trek TV show
    ... affected certain key alloys and made certain kinds of machines used by ... From a transporter pad to another pad, ... The Universal Translator is really good at languages that have already ... The Starship Enterprise leaves Earth to discover what's happened to the ...
  • Re: whats it worth to write a short program for polynomial multiplication?
    ... compile time, it is likely that the user will have to ... Most OO programming languages work that way. ... will also work on the POWER machines and related one. ...
  • Re: Challenge for lisp lovers....
    ... representation of numbers a particular language implementation uses. ... I do care about other languages. ... Lisp Machines were almost tied to a single ...