The Kleene Fixed Point Theorem: Quine

Hello, hello. Recently there has been a lot of talk about quains, and even some theoretical spin-offs .
I will repeat for the author of the topic just mentioned: if you are familiar with CS, then there’s no point in reading - all this
you already know so well. And the article will answer the question - is it always possible to write a quine? More precisely, in any language?
Physicists will say that at all: if you can write both on a compiled C and on a brainfack, and someone writes in SQL, experience says that the answer to the question is yes. Mathematics also says yes.

Theorem 2

In any algorithmically complete programming language, you can write a program that prints its own code.
Definition: Algorithmically complete language — a language in which a Turing machine can be implemented, that is, any algorithm.

Introduction

All valid programs in any language can be numbered. For example, in lexicographical order. Can write
an algorithm that, by program code, will return its number, and vice versa. Both the first and second is done, for example, by enumerating all the lines starting from the short and finding among them the correct source codes.
And therefore I will identify the programs and their numbers.Programs will receive some numbers for input and output some output, and the areas of definitions and function values ​​will be subsets of natural numbers. The program and the algorithm will be synonymous.
')
Today I will prove two theorems.
Definition: a function from natural numbers to natural numbers that can be programmed is called a computable function. The scope of the function may not be all natural numbers. To program means to write an algorithm that, when it receives any of the numbers on which the function is defined, returns the value of the function and loops on the others.

Theorem 1 (on a fixed point)

For any everywhere definite computable function f, there exists a number n such that the algorithms n and f (n) compute the same function. That is, they will be at the same inputs or give the same answer in the end, or loop together. Such algorithms are called equivalent.
I paraphrase. If there is a program that receives the source code at the input and returns the source code, then you can choose a source that does not change in meaning after this conversion. (Execution time and so on can easily change, but not a calculated function.)

Evidence

To begin with, we will gradually build a scary algorithm.
Let the program U receive the input number n and interpret the algorithm with the number n at the input n.
I will formulate the last word by the second method: the algorithm U takes the source code of a certain program as input and starts it, passing its source code to the input.
That is, U (n): = n (n)
Now we will remake this program so that it never gets hung up (in fact, so far it may easily hang on some inputs), but in return it will not return exactly what it is now.
The new program V will work like this: if U (n) = m, then V (n) = k, and k is the number of the algorithm that calculates the same function as the algorithm with the number m. That is, V, receiving the input number n, returns the number of the algorithm equivalent to the algorithm number n (n). And if n (n) goes in cycles, then V (n) returns no matter what.
How to build a v:
First we compose a program W (n, x), which interprets the program n at the input x. That is, W (n, x): = n (x). It looks like a U.
Now, let V take the program U, rewrite it so that it ignores its input, and instead of the argument, it uses the hard-coded number n (program parameter V), then V recognizes the number of the obtained algorithm t, and then returns the program number W, into which also, instead of the first argument, the number t is rigidly substituted.

Pause.

It turned out difficult, this is the worst place. Step by step algorithm V:

• at the input we get the number n
• take the program code U and replace all references to the argument with the usual number n
• we get the number t created by the algorithm
• we take the function W and, instead of the first argument, we substitute the number t, thereby reducing this argument. This means that the program Wt (x) comes from one argument.
• get and return the number of the created algorithm

Let's write down what happened. Operator # will take the number. The operation of obtaining a code by number will be indicated in any way (just by brackets).

V (n): = #W (#U (n), x) = h

Let's take an algorithm with number h and run x at the input.
h (x) = V (n) (x) = W (#U (n), x) = U (n) (x) = n (n) (x)

Such an entry A (x) (y) everywhere here means that we substitute the number x in program A, and then turn the result back into the program and substitute the number y into it. It is easier to understand if we assume that programs accept and return source codes.

As we see, the algorithm with the number V (n) does indeed the same thing as the algorithm with the number n (n). This is the function we wanted. Also, it is clear that the program V does not interpret anything, but only receives numbers, and therefore cannot get stuck anywhere.

And the last step is to produce a fixed point for an arbitrary everywhere defined computable function f.
Take any algorithm F that computes f.
Construct the program G: = V -> F, that is, execute program V for input, and then transmitting the result to input F.
In other words, for any x, G (x) = F (V (x)) holds.
Required number: V (#G), that is, the output of the algorithm V, which was given the input of the number of the newly constructed program.
Check:
We substitute the argument x into the algorithm with the number V (#G).
V (#G) (x) = [by definition V] = G (#G) (x) = [by definition G] = F (V (#G)) (x)
Received the same as if they substituted x into the algorithm with the number F (V (#G)) = f (V (#G))
This is the definition of a fixed point. Programs with numbers V (#G) and f (V (#G)) do the same thing.
F does not obsess about the everywhere-defined condition of f, V and G are not obsessed by construction.
The desired number exists.

Quineas.

Thanks to those who mastered. I tried very hard to make it as clear and simple as possible, but the topic is rather complicated.

Theorem 2:
There is a program that displays your number.
Evidence:
We introduce the function S (n), which takes the program code with the number n, and returns the number of the program that trivially prints this code.
Those. S (n): = # (print "N"), where N is the program with the number n, "N" is its source as text.
This function is computable (we defined it algorithmically), is defined everywhere, which means it has a fixed point.
That is, such a number that the programs N and (print "N") do the same thing. The output of the program N is the same as the output of the program (print "N").

It is enough to remove the program numbers in all arguments, and we will get the same with the source codes themselves. After all, any data is a number, we know.

Conclusion

So it goes.
Hope that was interesting or useful. If the community is interested in this, I can write about the Rice theorem, the algorithmic completeness of Peano arithmetic (yes, arithmetic is stronger than the Turing machine. Although it is understandable), and other such nonsense.
If there are questions and something is not clear, write - I will answer everything I can.

Materials

Memory.
That seems to be a good lecture , but I only looked at the very beginning, I can not judge further on clarity. But it seems that the man is available explains. Only here you need to know the basics of the theory, including solvable \ enumerable sets and numbering. Well, plus a terribly long video.
Nothing on the topic of the article, but not requiring introductory study, I can not offer.
And if you want to understand, then read the books Vereshchagin-Shen - a very high-quality literature. But you need to go through the theory of sets, then mathematical logic, and then only the theory of algorithms.