Constant language

A constant language or constant semantics is a trivial language with a constant behavior. As a language, any string is acceptable and recognition trivially succeeds; as a programming system, there is only one action which the system can perform.

Constant languages are usually jokes. Sometimes the humor is in the output of the behavior, particularly when interpreted as a meme in a natural language. Other times, the humor is in an unexpected behavior which is technically possible on a standard computing machine but not usually available as a programming primitive.

A constant language sidesteps the central questions of computability by being too simple for computation. No effort is required to decide whether an input ought to succeed; instead, it trivially always succeeds.

For constant semantics that produce an output string "like this", we will write ConstantLanguage("like this").

Quine avoidance

When considered as a mapping from inputs to outputs, a constant language may incidentally have a quine. For example, the constant language Nope. has the quine "Nope." A constant language is quine-avoiding when it has a special case specifically to ensure that no quines exist. For example, the quine-avoiding constant language No.pe. is like Nope., but maps "Nope." to "No." Note that quine avoidance always creates a symmetry; No.pe. maps "No." to "Nope."

For quine-avoiding constant languages that normally are "like this" except with a special case "for that", we will write QuineAvoiding("like this", "for that").

Computational complexity

Generally, a constant language is too trivial to have a grammar; when all strings in a language are accepted, it does not matter precisely how any individual string is structured. As such, constant languages are NONE-complete: they are complete for the set of no languages whatsoever, and not for any larger natural complexity class.

A quine-avoiding constant language does have to decide whether its input matches its special case. The precise circuit complexity will depend on the length of the potential quine, but in all cases it will be in LOGSPACE.

Formalism

Let L be a language: a set of strings. The constant semantics on L is the unique function c : L → 1. We can map this to any label s, represented by the element elt(s) : 1 → S, with standard composition; obtaining the map c;s : L → S which is constantly s. When S is a subset of L then this naturally extends to an endomorphism L → L.

Similarly, a quine-avoiding constant language is a function c : L → 2 which detects potential quines. It has a pair of labels s and q in L, represented by elt(s) and elt(q) : 1 → L, which we'll pair up into a single mapping sq : 2 → L. We merely require that elt(s);c;sq = elt(q) and elt(q);c;sq = elt(s); in words, c ensures that s and q don't map to themselves, but to each other. Note that s and q are symmetric; a quine-avoiding language can be thought of as having a special case for almost all inputs, or for only finitely many inputs.