
Taking advantage of the fact that the next month of quineas passes on Habré (see, for example, the
Kleene's fixed point theorem: quineas or
multilingual quineas ), I would venture to tell one of my own stories. It will not have such complications and obstructions, as in the mentioned topics, so this text can be perceived as Friday entertainment.
It happened almost a quarter of a century ago, in an era of a lack of universal computerization and the Internet. I somehow had a question - is it possible to write a program that displays its own text? At that time, none of my friends knew the words “quine”, and I could not look at Wikipedia “for lack of it” (c).
I tormented myself on this task for a week, but I still won it. The program turned out to be clumsy, long, but it met the requirement. Terribly proud of myself, I began to offer this task to all my friends. Along the way, I had to clarify the conditions - you cannot read from the file, the program should not be empty. Usually after this comrades for a long time thought.
However, one of the friends instantly replied to me that this, they say, was elementary, and immediately gave me the required program that met the set conditions.
It turned out that I still missed one important and, it seemed, the obvious condition. However, without his explicit mention of the problem really becomes trivial. Nevertheless, even in the modern article about quayns
in Wikipedia, this condition is somehow absent. Want to know what the condition is?
The program was like this:
program quine; var i:byte; begin randomize; for i:=1 to 91 do write(chr(random(255))); end.
Here, the language is Pascal, but I hope the idea is clear: there was no condition that the program should display its own text
each time it was run .
The given program each time displays a random sequence of 91 characters. The likelihood that this will result in the text of the original program is extremely small. However, this probability is non-zero!
')
In many articles (especially mathematical ones), the set of computer programs and algorithms is intentionally narrowed down by considering only deterministic (or computable) functions. But a lot of imaginable programs are much wider.
Of course, the program given here refers us to
the “endless monkey theorem” theorem , which states that an abstract monkey, striking randomly at the keys of a typewriter for an indefinitely long time, will sooner or later print any specified text (in particular, “Hamlet” Shakespeare).
In addition to various doubts of a philosophical nature of the truth of this theorem, most of which can be read from this article in Wikipedia, there are practical difficulties with the implementation of this quine. Even if we allow the computer to work for an unlimited amount of time, it is possible that the text of the program will never be printed. The fact is that the operators randomize and random provide pseudo-random numbers, and by no means generate a real random sequence. Therefore, it may well be that the sequence of characters we need will never appear due to this pseudo-randomness.
Nevertheless, the originality of this approach to the task deserves attention!
Ps. Read about this decision with the words of a friend mentioned here, as well as other stories from his life here:
Quine Pascal