Lambda the Ultimate

The Complexity Zoo

Please do not feed oracles to the complexity classes! These classes require a specially balanced diet to ensure proper relativization.

Way too often PL designers refer to Turing machine or other formalism as a benchmark of expressivity. For practical needs, though, the algorithmical complexity of programs is quite important. E.g., if the program takes O(n) steps on Turing machine, but O(2ⁿ) on my shining new rewriting engine, then it's time to doubt the usefulness of my engine in practice.
What are the well-known (classical) results relating complexity classes of programs expressed on different media (calculi/abstract machines/etc.)?
Or am I totally confused and there could not be such a thing?

I'm curious if there have been studies on the limits of semantic extensibility by computer programs. I'm not entirely sure how to phrase exactly what I mean. It's kind of like "what are the limits to how much 'environmental extensibility' a computer program can have?" I imagine the answer is related to type theory, somewhere along the lines of it being limitted based on predefined type information, but I'm not quite sure where to start looking.

This type of information would be useful when building models and meta-models, to know when "architectural astronauting" (to use a Spolsky term) isn't going to get you any more real benefits, anyway.

Sorry for the confused question. The concepts are a bit confused in my mind. Which is why I brought it here, because I imagine some of you know if anyone has done work in this area.

My knowledge in the area of languages is limited, that is why I am always visiting this site. Some of the papers, and terminology are very helpful and give me many 'over-my-head' interesting reads, so to the editors and commentors you have my thanks for the education.

I don't have a detailed grasp on introspection but I feel I have enough knowledge to appreciate its practicality. My main question arises from a seperation I see, in dealing with introspection, between so-called compiled languages like C, and C++, and dynamic languages like Python and Ruby. Does a language make sacrifices to gain the ability to introspect? And if so, what kind of sacrifices does it have to make? Can a languages like C or C++ gain introspection?

Though I guess the ultimate question would be, would languages like C and C++, and in turn their programmers, gain anything substantial from introspection?

I am sorry if my question is not completely clear, so please prod me with questions if the questions need to be refined for better answers.

Regards,

MJ Stahl