﻿ Constructing a Quineless Language

# Constructing a Quineless Language

On various websites devoted to the world of quines, there are words to the effect that there exists a quine in any Turing-complete language capable of outputting an arbitrary computable string.  For example, David Madore's page on quines states:

The interesting thing is that writing a quine does not depend on any kind of hack such as being able to read a source file, or even being able to represent quotes in several different ways. Any programming language which is Turing complete, and which is able to output any string (by a computable function of the string as program — this is a technical condition that is satisfied in every programming language in existence) has a quine program (and, in fact, infinitely many quine programs, and many similar curiosities) as follows by the fixed-point theorem.

The term "fixed-point theorem" refers to several mathematical theorems, all of which guarantee in certain conditions that a function has a fixed point, i.e. an element of the function's domain that maps to itself.  The fixed-point theorem that's relevant here is Kleene's recursion theorem. The 'function' being considered is the language's evaluation mechanism, which maps the program code to the output generated by it.  (This is a highly simplistic view, of course.)

But the statement, in its simplified form at least, isn't exactly true; indeed there is a simple means of generating a counter-example.

## How It's Done

Take any programming language satisfying the supposedly sufficient criteria.  Then modify it so that, until an input or output operation has actually been executed, any instruction to output a character equal to the first character of the program code is ignored.  Of course, if this character is output as the first character of a string or number, then the same rule applies.

This is most easily implemented for a language in which output is performed by built-in instructions, and not by external libraries or inline assembly.  Otherwise, certain mechanisms must be put in place to trap all possible methods of outputting, which can be difficult.  An alternative to trying to do this is to deprive the modified language of access to these features, and throw in a built-in means of output if it doesn't have one already.

Of course, the ability of the new language to generate and output an arbitrary string is not hindered.  The same code that is a quine in the original language can be output by a program in the quineless version, but the program must be modified so as not to begin with the first character of the output.  This can be done by a simple modification to the existing program, by inserting a comment or no-op code at the beginning.

Of course, if we were to write a program that outputs the program code excluding the comments, then this certainly does not constitute a quine, even more so since when its output is fed back into the interpreter/compiler, the first character it attempts to output will be rejected.

What about the null program?  This constitutes a (trivial) quine in any language in which an empty source code file is a null program.  This can be avoided by modifying the language so that an empty source file is either illegal or treated specially, i.e. it would output a non-empty string, be it random or defined.

Of course, it is cheating to request any input before producing the output, as is to use any (usually platform-dependent) "clear screen" or "form feed" codes to remove the initial output.

What about non-user input?  For example (to some extent):

• file input
• the system clock
• incoming communications through a modem or network
• access to memory that may contain data from outside of the program
• various operating system API, BIOS or hardware calls
• a random number generator, if any form of non-user input is used to seed it

While these are still sources of input, the fact that they are not user input means that the user need not know that the input operations are happening.  (A similar argument applies to inputs on the state of the moment, e.g. whether a key is being held down, the position of the mouse cursor or whether a disk is in a drive, although these may be under direct user control.)  If we wish to preserve the ability of the language to translate arbitrary input data into arbitrary output data that is computable from it, then such non-user input would have to count as input, such that it neutralises the restriction on the first output character.  However, since the user need not know that it is happening the program could effectively circumvent the restriction by taking input but not actually using it.  Such a program may appear (to somebody reading the code) to use non-user input, but actually manipulate what it receives until it becomes constant.  Since it is probably impossible in the general case to determine algorithmically if the program really doesn't use any of its input before outputting, the only sure solution is to remove all access to non-user input.  This would mean that all input comes from the user.  We can get away with this, since the ability to receive non-user input is not a criterion for Turing completeness, and the same data could equally be processed if it comes from the user input stream instead.

## Someone Else's Idea

Since I first wrote this piece, ais523 on the Esolang wiki proposed an alternative idea for a quineless language that is Turing complete and capable of outputting an arbitrary string.  The idea is:

• If the program is empty, report an error.
• If the first character of the program is a quotation mark, output the entire program except for the first character.
• Otherwise, interpret the program as an Iota program.

This relies on the fact that Iota is Turing complete, but incapable of performing any output.  The second case provides the ability to output an arbitrary string.

But this could be considered cheating.  Although the resulting language is Turing complete, it cannot in any way take advantage of Turing completeness to generate output.

## Resolution

Can these ideas coexist with any conditions that guarantee the existence of quines?

Most Turing-complete programming languages have a property we can lay our hands on: There exists a program to implement every Turing-computable function mapping input strings to output strings.  By concerning ourselves only with languages having this property, we can avoid degenerate cases such as ais523's idea above.  However, restricting ourselves in this way would also exclude all languages with output but no input capability.  There is probably a suitable formulation to cover such languages as well, but that's an aside.  The fact that there exist languages with the aforementioned characteristic is sufficient that quineless languages can be created, by my approach, that still have this characteristic.

The quote from David Madore's page talks of "Any programming language which is Turing complete, and which is able to output any string (by a computable function of the string as program — this is a technical condition that is satisfied in every programming language in existence)".  Admittedly, it took me a while to figure out what was meant by the parenthesised bit.  Now I realise it must mean that there exists a Turing-computable function that, given a string to be output, will return a program in the given language that outputs the string.

It would appear that more than this is necessary.  Indeed, at face value, the counter-examples that have been discussed are counter-examples even to this statement.  I reckon the real statement is this:

Any programming language capable of implementing every Turing-computable function mapping input strings to output strings, and for which the mapping from Turing-computable functions to programs is itself Turing-computable, has a quine.

It may not be possible to determine in advance the first character of the output in order to avoid using it as the first character of the program.  For example, take an unsolved mathematical problem, such as Goldbach's conjecture or whether there are any odd perfect numbers.  You wish to write a program that will output a character depending on the first solution found – in such a way that it could be any character.  If Goldbach's conjecture is true or there are no odd perfect numbers, then the program would loop forever.  This is itself a Turing-computable calculation.  However, one cannot be sure which character should be output first in order to avoid using it as the first character of the program.  Of course, one can write two programs and know that at least one of them works as intended, but that isn't sufficient for the statement of Kleene's recursion theorem.

In summary, the property the quineless language lacks is the Turing-computability of the program to generate an arbitrary string by an arbitrary Turing-computable algorithm.  In the absence of this, Kleene's recursion theorem cannot be applied, and so there is no contradiction between the theorem and the quineless nature of the language that has been constructed.