A programming language
(alternatively, a computation
) is called Turing complete
if it is equivalent
to the Turing machine
model: any program
written in the language
can be simulate
d with some Turing machine, and every Turing machine can be simulated by some program written in the language.
The Church-Turing thesis states that any "interesting" computational model is Turing complete.
Since the (technical) theory of recursive functions is Turing complete, a programming language is Turing complete iff every program calculates some recursive function, and every recursive function may be calculated by some program in the language.
Primitive recursive functions are not Turing complete: they cannot express the Ackermann function. C and Pascal are Turing complete if we're careful to ignore some details (e.g. a C implementation must use pointers of some finite size sizeof(void *), implying it can only use some finite amount of data). Real programming languages are Turing complete only if we ignore the constraints of finiteness.