Turing completeness
From Academic Kids

In computability theory a programming language or any other logical system is called Turingcomplete if it has a computational power equivalent to a universal Turing machine. In other words, the system and the universal Turing machine can emulate each other. The term derives from the name of mathematician Alan Turing who introduced the model of the universal Turing machine. (Under traditional hyphenation conventions, the adjective Turingcomplete should be hyphenated, but the noun Turing completeness need not be.)
While such machines may be physically impossible as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had indefinitely enlargeable storage. Charles Babbage's analytical engine would have been Turingcomplete if it had ever been built, but the first actual implementation appeared in 1941: the programcontrolled Z3 of Konrad Zuse. Its universality, however, was shown only much later, namely, by Raúl Rojas in 1998. The first machine known to be Turingcomplete was ENIAC. All modern computers are also Turingcomplete in this lax sense.
Turing completeness is significant in that every plausible design for a computing device so far advanced (even quantum computers) can be emulated by a universal Turing machine. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other computer is capable of (in other words, it is programmable). Note, however, that this says nothing about the effort to write a program for the machine or the time it may take to do the calculation.
It is hypothesized by some that the universe is Turingcomplete (see philosophical implications in the ChurchTuring thesis and digital physics).
See the article on computability theory for a long list of systems that are Turingcomplete, as well as several systems that are less powerful, and several theoretical systems that are even more powerful than a universal Turing machine.
Examples
All of the generalpurpose programming languages in wide use are Turingcomplete. This includes conventional imperative languages such as C and objectoriented languages such as Java. Languages designed for less common paradigms including functional languages such as LISP and Haskell, and logic programming languages such as Prolog are also Turingcomplete.
It is difficult to find examples of nonTuring complete languages, as these languages are very limited (see, however, machines that always halt). An example would be a series of mathematical formulas in a spreadsheet with no cycles. While it is possible to perform many interesting operations in such a system, this fails to be Turing complete as it is impossible to form loops. The macro language within Excel however is Turingcomplete. Another famous example is regular expressions, which are generated by finite automata. A more powerful but still not Turing complete extension of finite automata are formal languages.
One important result from computability theory is that it is impossible in general to find if a program written in a Turingcomplete language will continue executing forever or will stop within a finite period of time (see halting problem). One method of commonly getting around this is to cause programs to stop executing after a fixed period of time, or to limit the power of flow control instructions. Such systems are strictly not Turingcomplete.
Another curious theorem from computability theory is that there are problems solvable by Turingcomplete languages that cannot be solved by languages with finite looping capabilities (i.e. languages that guarantee any program will halt). This result is derived by, for example, Brainerd and Landweber using the PL and PL{GOTO} languages.
The untyped lambda calculus is Turingcomplete, but many typed lambda calculi, including System F, are not. The value of typed systems is based in their ability to represent most "typical" computer programs while detecting more errors.
Bibliography
Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
See also
 ChurchTuring thesis
 Algorithmic information theory
 Machines that always halt
 Stephen Wolfram's A New Kind of Science
 c2.com (http://c2.com/cgi/wiki?TuringComplete)de:TuringVollständigkeit