Turing-complete

A system (generally speaking, a programming language) is Turing-complete if it can do everything a Turing machine can do.

If, in the Chrysoberyl database, a programming language is labelled as Turing-complete, it means that it has been demonstrated in a (reasonably) formal way — as opposed to it being so uncontroversial that no one has bothered.

All Programming Languages in this Class

Commentary

Ah, Turing-complete! Turing-complete! Say it again; it's a little like a mantra in this part of the world. Turing-complete!

"Do everything a Turing machine can do..." This requirement is maybe stronger than you intuitively think, maybe weaker than you intuitively think.

Stronger, because machine languages, per se, are not Turing-complete, because they only have a finite number of memory locations to hold data in. No matter what machine language you have, I can always come up with some computational problem that it can't solve because it requires one more bit of data than you can hold.

(And this extends to languages like C as well — they assume so strongly that they are compiling to machine code that they adopt some of the finitist limitations of it.)

Weaker, because we can define systems that do things that Turing machines were never intended, or defined, to do: for example, produce output, accept input, wait for a specified duration in time, or feel emotions.

The whole Turing-completeness issue is actually fairly subtle, and I feel like I could write a book on it (or at least a rather fat pamphlet).