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.

Answer 2

As a proof I have created a Turing Machine implementation in APL.

Please see my implementation below: (There is probably a cleaner solution as I have just started learning APL)

step←{                                        ⍝ ⍵:    state head tape
    rule←(1⊃⍵) ((2⊃⍵)⊃3⊃⍵)⌷⍺                 ⍝ prod: new_symbol move new_state
    tape←(2⊃⍵) {(⍵×~M)+(⊃rule)×M←⍺=⍳⍴⍵} 3⊃⍵  ⍝ write symbol to tape
    head←(2⊃rule)+2⊃⍵                         ⍝ move head
    tape←head {1+(⍺⌈⍴⍵)↑¯1+⍵} tape            ⍝ extend tape to new head pos (+1 +¯1: pad with ones)
    (3⊃rule) head tape }
delta←4 2 3⍴1 0 3 1 1 2  1 0 4 1 1 1  1 0 3 2 0 3  1 0 4 2 0 4
init←1 1 (2 2 2 2)
delta step init              ⍝ single step
↑{delta step ⍵}\7⍴⊂init      ⍝ show 7 steps as matrix

In this implementation, delta contains all state transitions and init represents the initial state, head position and tape. The step function takes the state transition matrix delta and a configuration and calculates the new configuration.

---

To represent the configuration of a Turing machine, we need to keep track of the current state, head position, and contents of the tape. We can assign a number starting at one to each state, and represent the tape as a nested array in APL. The head position is simply an index into the tape array.

For example, the configuration (q2, [(a), a, a, ☐]) can be represented in APL as 2 1 (2 2 1). In my implementation, 1 on the tape means blank and all other numbers can be assigned freely.

To define the transition function, I used a 3-dimensional matrix that can be indexed as state symbol ⍴ delta to retrieve the matching transition rule. Each row contains the symbol to write, the head movement (¯1,0 or 1), and the next state.

---

As an example of a Turing machine, consider one that decides if the input has an even number of characters. This can be represented as M=(Q,Γ,δ), where:

• Q = {q0, q1, qacc, qrej}
• Γ = {☐ , a}
• δ has state transitions:
  • q0,☐ -> ☐,0,qacc
  • q0,a -> ☐,R,q1
  • q1,☐ -> ☐,0,qrej
  • q1,a -> ☐,R,q0
  • qacc,* -> *,0,qacc
  • qrej,* -> *,0,qrej

In APL, this looks like: delta←4 2 3⍴1 0 3 1 1 2 1 0 4 1 1 1 1 0 3 2 0 3 1 0 4 2 0 4

      ]DISPLAY delta
┌┌→────┐
↓↓1 0 3│
││1 1 2│
││     │
││1 0 4│
││1 1 1│
││     │
││1 0 3│
││2 0 3│
││     │
││1 0 4│
││2 0 4│
└└~────┘

The initial configuration on the tape is "aaaa", with q0 as the initial state: init←1 1 (2 2 2 2)

      ]DISPLAY init
┌→──────────────┐
│     ┌→──────┐ │
│ 1 1 │2 2 2 2│ │
│     └~──────┘ │
└∊──────────────┘

The output of the code is a matrix of configurations obtained step by step through the use of a scan, which evaluated the Turing machine.

      ↑{delta step ⍵}\7⍴⊂init
┌─┬─┬─────────┐
│1│1│2 2 2 2  │
├─┼─┼─────────┤
│2│2│1 2 2 2  │
├─┼─┼─────────┤
│1│3│1 1 2 2  │
├─┼─┼─────────┤
│2│4│1 1 1 2  │
├─┼─┼─────────┤
│1│5│1 1 1 1 1│
├─┼─┼─────────┤
│3│5│1 1 1 1 1│
├─┼─┼─────────┤
│3│5│1 1 1 1 1│
└─┴─┴─────────┘

The state is in the first column, the head position is in the second column, and the tape contents are in the third column.

The final configuration is a fixed point with state 3, which is the accepting state qacc. This verifies that "aaaa" has an even length.

Test for "aaaaa":

      ↑{delta step ⍵}\7⍴⊂1 1 (2 2 2 2 2)
┌─┬─┬───────────┐
│1│1│2 2 2 2 2  │
├─┼─┼───────────┤
│2│2│1 2 2 2 2  │
├─┼─┼───────────┤
│1│3│1 1 2 2 2  │
├─┼─┼───────────┤
│2│4│1 1 1 2 2  │
├─┼─┼───────────┤
│1│5│1 1 1 1 2  │
├─┼─┼───────────┤
│2│6│1 1 1 1 1 1│
├─┼─┼───────────┤
│4│6│1 1 1 1 1 1│
└─┴─┴───────────┘

State 4 is the rejecting state qrej. This indicates that "aaaaa" does not have an even length.

---

Try it here: https://tryapl.org/

Answer 3

Note that many languages are practically as good as Turing complete but not actually Turing complete. For example, in C and C++ sizes of integers and pointers are compile time constants. So typically you can’t have more than 16 billion billion addresses, which is no practical problem but makes it hard to claim C is Turing complete.

So you’d have to go very carefully through the definition of APL and show there are no size limitations.