Is APL a Turing-complete language?

Question

On the Wikipedia page for APL, I haven't been able to find any mention of the language being Turing-complete, although it does (to my incomplete understanding of TC) appear to be capable of performing any possible calculation.

Can anyone elucidate?

Answer 1

^{(elaborating on my comment)}

In general, most programming languages and many domain specific languages are Turing-complete. In practice, you need to design a language very carefully to have it be non Turing-complete (hence, nearly all programming languages are Turing-complete). When someone tells you: this language Foo is not Turing-complete you need to be very suspicious and require a proof of that fact. For most programming languages, ask yourself about the Halting problem (if it applies, that language is Turing complete)

Look also for accidental Turing-completeness, it is amusingly instructive.

APL is Turing-complete because it has conditionals, branching, and recursive functions. It is also Turing complete because you could code in APL a Random-Access-Machine interpreter.

Notice that Turing-completeness is a theoretical abstraction. In practice, all our digital computers (and even the entire Internet) are finite state machines; they have a finite amount of memory, e.g. 10¹⁴ bits for most laptops in 2015, so a finite, but enormous, state space. Even the entire quantum universe could be viewed as a gigantic finite state machine (pan-computationism, Planck units, ...).

But viewing most computers (or programming languages) as finite state machines is inadequate for most purposes. The Turing machine model (or its equivalents) is often more adequate. Learn also the Rice's theorem. Read also J.Pitrat's blog which has some interesting views.

Notice also that time complexity & combinatorial explosion & computational complexity matters usually much more than Turing-completeness. A program giving a result in billion years is useless.