Talk:Quine (computing)/Nontrivial IO-free quine

From Wikipedia, the free encyclopedia

1 Triviality questions
2 Just thinking loudly — I am a newby yet, maybe I confuse things
3 Examples
- 3.1 Combinatory logic
- 3.2 Recursive function theory
4 Notes

I have been thinking many of such things. A huge advantage of Ben-Arba's proposal above is the elimination of printing, output etc. How to eliminate the concept of “output”, (in general, all “unpure” imperative things) from the concept of quine? How to achieve a pure mathematical “idea” (in the Platonic sense) of notion quine? How to lift the concept of quine from a hacker's progamming thing to a mathematical (mathematical logic, metamathematical) concept?

My first quines were (for me) mathematical formulas, reduceable, evaluatable formulas. A mathematical formula which evaluates to its own “term representation”, “quotation”. More precisely, it is not expected to evaluate to its own term representation, but it should at least be equivalent to its term representation. Thus, no “actions” (printing, output) was involved in the concept.

I wrote my quine in combinatory logic. (My other quine, written in Haskell (programming language) used printing/output, but it could be rewritten to avoided any notion of output, printing etc. Then, it would be simply a Haskell term (of type String), which evalueted to a string, which was identical to the source code of the Haskell term. If the original program would use quoatation marks, then they would appear as preceeded by escape marks in the evaluated version. Or an equivalent trick would be needed (representation tricks).

[edit] Triviality questions

[edit] Special language

See HQ9+.

[edit] Identity tricks

Yes, question struck also me: what about trivial things? Is "Hello word" a quine? It is a legitime Haskell expression, and evaluates to “itself”. Or, regarding combinatory logic, is

$\mathbf{K}$

a quine? Also it evaluetes to itself: a basic combinator is already in normal form, it does not reduce any further! Eventually, what does “itself” mean? More exactly, what do underlying (till now, unspoken-of) notions “name of” vs “meaning of” mean?

In the chosen specific solution, I did not regard the above trivial things as quines (not even trivial ones). In this scheme,

would be a quine only if it wuold evaluate to

"1"

Also,

"Hello world!"

would be a quine only if it would evaluate to

"\"Hello world\""

And let us see an example also in combinatory logic:

$\mathbf K$

would be a quine only if it would be equivalent to

$\mathbf{leaf}\;\mathbf{true}$

because this “singleton” binary tree on booleans is the term representation (structural descriptive name, quotation) of $\mathbf K$ (if we use a “binary tree of booleans” representation scheme ^[1]).

[edit] Encoding tricks

Patricia's example (see also the previous messages to have the full context, but it the main point can be understood also in itself).

What about it? Can this triviality be made excluded by a sufficiently deep, general and abstract formalization? (And is it worth to do so?)

[edit] Empty quine?

In the leader (definition) part of the Quine article, another trivial solution is mentioned: empty quines.

[edit] Trees, and/or I/O-less

In #Combinatory logic and also in #Recursive function theory quines, this problem is simply out-of-paradigm:

In both approaches, a program is not conceived as a sequence, but as a tree, not allowing the possibility of “empty terms”.
In both approaches, no notion of I/O is at hand, thus, we have to resort to the “evauates or equals to ~~itself~~ its own term representation” solution. Besides that, even if we would represent things by sequences (e.g. list of three symbols), an empty list is represented not by “nothing”, obversely, by a not-basic combinator ^[2]. Thus, even if combinatory logic would consist of seqences, and even if an empty sequence would have sense in it, and even if it would do “nothing”, even then we would have to expect it to yield the term representation of $\mathbf{nil}$ , a non-basic combinator, neither it nor its term representation is “nothing”, “emptiness”.

[edit] Sequential, and/or I/O

Is an empty quine imaginable in more sequential algorithm schemes (e.g. Turing machine, Markov algorithm, register machine)? I simply do not know. I tried to think on this, but there came many things to think about, e.g.

an empty program may be invalid,
or possibly the empty string is not the representation of empty program;
besides all this, the possibility of I/O may make all this “not itself, but a term representation of itself” approach superfluous, etc.

What would some Turing machine, Markov algorithm, register machine quines look like? I know almost nothing about all these things (many things are totally other than in combinatory logic).

[edit] Just thinking loudly — I am a newby yet, maybe I confuse things

How to abstract the good Haskell and combinatry logic quines and grasp their essence? What differentiates them from trivial things? What is the main point? Maybe the followings:

we select a object languege,
and a metalanguage of it.
The desidarated quine will be a sentence of the object language,
Each object language sentence has a meaning and a name in the metalanguage. Both are expressed in the metalanguage, but they are conceptually rather different things. Let us think of the medic student, who (while preparing himself for the examination) wants to be in place of a bacterium: “Good for it, it knows the whole biochemistry, unlike me!”. Yes, meta language is another level of things. Returning to the topic of name vs meaning
- a name (e.g. a structural descritive name, see Alfred Tarski) in the metalanguage. That means, the metalanguage should have a name for each sentence of the object language. The main pont here: name, that means, the metalanguage can “call each sentence of the object language by name”. Metalanguage has many things, and above all that, also “individual names”, “personal names” for each object language sentence.
- a meaning, also expressed in the metalanguage. It is something that we think of as ”evaluating”, ”meaning of” a “writing”. The matalanguage is a rich thing, and its richness serves a.o. the purpose that we can express all possible intended meanings for which we originally planned our object language.
As mentioned, the desidarated quine is a sentence of the object language. Of course (as all sentences of the object language), also it has its own name (e.g. structural descriptive name) in the metalanguage. It has also its meaning, also expresses in the metalanguage
A quine is a sentence of the object language whose meaning (in metalanguage!) is the same (or can be made the same by the allowed deduction steps) as its name (also in metalanguage!)

[edit] Examples

Let us see some conrete ways for formalization of the notion of I/O-less quine. Maybe we can try to make generalizations and abstractions afterwards.

[edit] Combinatory logic

Let us see a concrete example. Let us use combinatory logic. Combinatory logic is a Turing complete thing (we can useitas a programming language),thus, we can express everything by it, what also in any other programing languages. We can make lists, booleans, binary trees etc.

Combinatory logic has a very simple syntax:

two base terms: $\textbf{K}$ , and $\textbf{S}$
a formation rule like thing: if x, y are combinatory logic terms, than (x y) is also one.

All this means, that we can represent the whole language (syntacticaly) by a binary tree datatype, whose leaves are of type boolean.

The evaluation rules of combinatory logic are a a very little more difficult, but no so hard, either.

Now, we write a combinatory logic program, which, when evalueated, becomes a binary tree of boolean leaves (let us remember, we are able to represent booleans and binary trees in combinatory logic!), and if we examine the resulting tree of bools, we see that it is exacly the representation of the program itsel (let us remember, all binary trees with boolean leaves can be regarded as representing a combinatory logic expression!)

Maybe I confuse everything. The combinatory logic quine works well, but I am not sure that my generalizations are correct. I am reading Tarski right now, it is fresh for me. Maybe things are more dificult (or more unified) than all this I have written. I don't know even exactly what plays the role of metalanguage and object language in my examples. Are they the same here? Is it important that Haskell and combinatory logic (and all programming languages used for a quine) can be the metalanguages of themselves? (Haskell knows strings, and strings can represent Haskell programs; combinatory logic knows trees and booleans, and trees + booleans can represent any combinatory logic term; recursive function theory knows natural numbers, and natural numbers can encode any recursive function theory term) Is some kind of reflexion required? I do not know. Tarski writes that there are objects languages rich enough to be able to represent an important subset of their metalanguage: the individual names denoting the expressions of the object language! Thus, in this case, the most important things relating the meta and object languages together:

we have already known, that a metalanguage can name the expressions of the object language (i.e. by structural descriptive names), thus, a subset of the metalanguage consists of “names” denoting expressions of the target language;
now a new thing to make things more interesting: in some cases, the target language may be rich enoung to be able to repesent exactly this subset of the metalanguage (described above).

Is this related to the topic of quines? I do knot know, either.

I know only that it is not required to achieve a self-interpreter. E.g. if I write a combinatory logic quine, I need not be able to implement lazy evaluation in combinatory logic itself. I have to be able represent combinatory logic terms in combinatory logic, but I need not to be able to evaluate combinatory logic terms in combinatory logic. Evaluation takes place only throgh the ultimate implementation laguage (e.g. C, Java, Haskell etc.) which will implement combinatory logic to run the quine. Maybe the main point is that reification is needed but a self-interpreter is not needed.

David Madore has a homepage on quines (Quines (self-replicating programs)), it says that it is the fixed point theorem (in the sense of mathematical logic, not that of analysis, see Kleene) that hides at the root of the concept of quine.

[edit] Recursive function theory

If we use natural numbers as a programming language (using recursive function theory), we can build also a quine. This programming language also has a reflexive feature: it can represent itself. Maybe that is a common feature in all quines?

Such a quine would be a program written in terms of recursive function theory: a huge function composed from zeros, incrementations, projections, generalised compositions, recursions, minimalizations (in Monk's notation, $\mathbf 0$ , $\mathbf s$ , $\mathbf U_{m,n}$ , $\mathbf B_{m,n}$ , $\mathbf R_m$ , $\mathbf\mu_m$ , and also their partial counterparts). This has

a meaning: a function of $\mathbb N^n \to \mathbb N$ or $\mathbb N^n \supset\!\to \mathbb N$
a name: because this huge expression is a tree-like thing, and a tree can be represented by a natural number, using clever number theory tricks (prime powers, also Chinese remainder theorem, also fundamental theorem of arithmetic etc.). See some details in Gödel numbering for sequences, although it does not discuss recursive datatypes.

And I could call a quine such a program (in recursive function theory),

whose meaning (a function of $\mathbb N^m \to \mathbb N$ or $\mathbb N^n \supset\!\to \mathbb N$ ) is of arity 0 (a function of $\mathbb N^0 \to \mathbb N$ ), thus, a costant, which can be regarded as an inhabitant of $\mathbb N$ , a natural number)
this number is at the same time a representation of a program (according to some previously fixed number theory tricks — used for representing recursive function theory “programs” with natural numbers),
and this program is exactly the program we are talking about, informally speaking, “it quotes exactly itself”!

[edit] Notes

^ In a rather informal (concise, but probematic) notation:

$\left\lceil\mathbf{K}\right\rceil \equiv \mathbf{leaf}\;\mathbf{true}$

$\left\lceil\mathbf{S}\right\rceil \equiv \mathbf{leaf}\;\mathbf{false}$

$\left\lceil \left(x y\right) \right\rceil \equiv \mathbf{branch}\;\left\lceil x\right\rceil\;\left\lceil y\right\rceil$

where $\mathbf{leaf}$ , $\mathbf{branch}$ (and also $\mathbf{true}$ , $\mathbf{false}$ ) are appropriate combinatory logic combinators implementing binary tree (and boolean) in combinatory logic. Of course — as Tarski mentions — using quoatation marks this way (using variables inside them, etc.) is very problematic. But I hope my intention is clear.
^ Lists may be realized in combinatory logic e.g. by using continuations. We expect reductions

$\mathbf{nil}\;c\;n\ \ge n$

$\mathbf{cons}\;h\;t\;c\;n \ge c\;h\;\left(t\;c\;n\right)$

where read h, t, c, n as metavariables for arguments head, tail, cons-continuation, nil-continuation — see foldr in Haskell, or catamorphisms of lists. Thus,

$\mathbf{nil} \equiv \mathbf{K}_*$

which can be defined by

$\left(\mathbf{K}\;\mathbf{I}\right)$

or maybe

$\left(\mathbf{S}\;\mathbf{K}\right)$