ℒ

ℒ is a family of languages proposed by Chris Pressey in 2010 to explore questions of Turing-completeness, particularly in terms of which parts of a system constitute code, state and input. For every pair of a Turing-complete language L and a program P written in L that simulates a universal Turing machine (for example, by being an interpreter for a Turing-complete language), ℒ_(L,P) is a member of ℒ in which P is the only valid program, having the semantics described by L. That is, ℒ_(L,P) is a highly-restricted subset of L in which P is the only valid program.

A less mathematical and more programmer-oriented way of describing ℒ is to think of it as the set that contains:

• A dialect of Pascal that is so restricted that you can only write one program, utm.pas, in it;
• A dialect of Pascal that is so restricted that you can only write one program, underload.pas, in it;
• A dialect of Scheme that is so restricted that you can only write one program, BCT.scm, in it;
• A dialect of brainfuck that is so restricted that you can only write one program, utm.b, in it;
• and so forth.

ℒ is frequently written as "fancy L", in situations where 'ℒ' is difficult to type.

Computational class of ℒ

The question, then, is whether any given ℒ_(L,P) (henceforth ℒ, as the particular L and P are not relevant) is itself Turing-complete.

This is ultimately a philosophical (or at least terminological) question about the status of input when describing Turing-completeness. The language which P takes as input is Turing-complete, and as such, there exists a program in ℒ which is capable of, by some reasonable definition, implementing a universal Turing machine.

However, there is not a mapping from arbitrary Turing machines to ℒ programs, as there exists only one ℒ program. There is only a mapping of arbitrary Turing machines to inputs for ℒ programs (or, equivalently, (program, input) pairs).

The two most common conclusions of this quandry are:

• We consider (program, input) to be coupled for describing Turing-completeness, and as such, ℒ is clearly Turing-complete.
• We consider input to be separate from the language, and as such, a new term is needed to describe ℒ's computational class.

Aside

Chris Pressey explains this in terms of making a distinction between functions and computations. A Turing machine, or any language without input, may be universal in the sense of being able to be programmed to perform any computation any other machine can, but it cannot be programmed to compute any function at all -- because functions map a given (i.e. not known a priori) value to another value.

The term "Turing-complete" seems to have its roots in recursive function theory, where functions are an important concept for distinguishing computability problems; for instance, the Uniform Halting Problem is strictly "harder" than the Halting Problem, but defining the Uniform version of the problem requires a definition of "input". (It's "harder" because the input is universally quantified; in essence, a function represents an infinite number of possible computations.)

At the same time, it seems rather ungenerous to say that only functions, and not computations, can be Turing-complete, as that would mean that we (rather ironically) cannot call a universal Turing machine Turing-complete.

The languages in ℒ are intended to be on the "opposite" side of this spectrum from Turing machines. Graphically,

Turing machines:

CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
`------------- any computation you like --------------'

Conventional Turing-complete programming languages with I/O:

IIIIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
`-- any input you like --'`-- any function you like --'
(combine these and you get any computation you like)

ℒ:

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIF
`---------------- any input you like ----------------'^-- one function only: the universal function
(combine these and you get any computation you like)

One difference between a conventional TC language with I/O and a language in ℒ is that in the conventional language, you are allowed to write any function you like -- including one that ignores its input, and acts as an inputless computation. It is not possible to write such a program in a language in ℒ.

ℒ-equivalence

Given that the computational class of ℒ is unclear, but there are languages which are plainly within its computational class, we can create a new (and intentionally ambiguous) computational class to describe it. ℒ-equivalent machines are those abstract machines for which the ability to describe all universal Turing machines is predicated upon the status of input or some other state which may be considered external to the machine proper. The set of ℒ-equivalent machines is clearly a subset of Turing machines, but whether it is a proper subset is a matter of philosophy. A language is said to be ℒ-hard if there exists a program in that language which is in ℒ, and ℒ-complete if it is ℒ-hard and not otherwise Turing-complete.

Examples of languages which are ℒ-complete include ALPACA, Befunge/index.php, Interpret Esolangs and HQ9+B, as well as the language subsets implied by many Golf competitions.