A

programming language (alternatively, a

computational

model) is called

*Turing complete* if it is

*equivalent* to the

Turing machine model: any

program written in the

language can be

simulated 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.