In addition, I have seen relevant discussions when I watched Eternal Turing before. Here are some ideas about Diophantine Sets and Recursive Countable Sets.
To understand recursive enumerable sets, we must first understand Turing machines.
For the definition of Turing Machine, please refer to Wikipedia.
Personally, I prefer this definition, although it is not necessary:
Obviously, the role of is to describe and the role of is to configure. The former describes "paper tape", while the latter describes the present situation of Turing machine.
Therefore, the operation process of Turing machine can be considered as a "world line" produced by "free movement" under the action of putting a Turing point in a given initial position in Turing space and making it move again in an initial state, and there are three possibilities in the end:
Of course, this statement doesn't make much sense, but it looks "gorgeous".
If the Turing machine is finally accepted (of course, it stops), then its Turing space is called "output result", and correspondingly, the initial Turing space is called "input parameter".
Therefore, if we only pay attention to a picture with a head and a tail, the Turing machine looks like this: that is, it maps the input parameters to some functions of the output result, which is nonsense.
If we define the state in Turing space as the power set of finite nonempty symbol set, then Turing machine can obviously be regarded as a partial function that can map finiteness to another set of finiteness, namely:
Here is a collection of all acceptable input states of Turing machine. If an input state does not exist, the Turing machine may refuse and stop, or it will never stop.
Here, the acceptable input state set of Turing machine is called "ergodic enumerable set".
Similarly, if a set is called "ergodic enumerable", it means that there is a Turing machine, so that it happens to be the set of all acceptable input states.
The problem of undetermined downtime tells us that we can never find a universal Turing machine, so that it can tell us whether any Turing machine can stop at a given input state.
In other words, it is impossible for us to find a universal Turing machine, so that it can judge whether any input state is an acceptable input state of a Turing machine.
Therefore, this is equivalent to saying that there is no universal Turing machine that can help us judge whether a set is ergodic and enumerable.
On the other hand, let's look at the Diophantine series.
If the sum of the coefficients is an integer, all the shape equations are called "Diophantine equations". For example, our most common quadratic equation is Diophantine equation; Fermat equation is also a Diophantine equation, and we know that this equation has no integer solution.
The existence of integer roots of Diophantine equation is a very interesting and difficult problem. For example, Fermat equation has no integer roots.
Therefore, it is an interesting question whether there is an algorithm to automatically judge whether the Diophantine equation with arbitrary input has an integer solution. If there is, many problems, including Fermat's last theorem, can be easily solved.
Now, we extract all the coefficients from a Diophantine equation: there is always a parameter.
Next, we will fix some of these parameters (or none of them), and the other part will be variable parameters (integers only). A set of such variable parameters is called a "parameter set". The set of all parameter groups that can make Diophantine equation have integer solution is called Diophantine set of Diophantine equation.
That is to say, any element in the Diophantine set can guarantee that the corresponding Diophantine equation (including those fixed integer parameters) must have an integer solution, otherwise the Diophantine equation has no integer solution.
If there is a one-to-one correspondence between Diophantine sets and ergodic countable sets, it means that at least one Diophantine set cannot be judged by Turing machine, because ergodic countable sets are undecidable, which means that at least one Diophantine equation (all parameters are fixed) cannot be judged by Turing machine.
This is equivalent to saying that the answer to Hilbert's tenth question is no.
In order to prove (and falsify) Hilbert's tenth question, people have worked hard for a long time. The long-term cooperation between Davis, Putnam and Julia Robinson, the first female mathematician elected to the National Academy of Sciences in the United States, finally proved this point:
It was Russian mathematician Yuri Machiavelli who proved the last conjecture, that is, the existence of Jr.
So, four people joined together to prove that it is equivalent for Diophantine sets to traverse enumerable sets.
This is called MRDP theorem, also known as Machiavelli theorem.
After the introduction of history, let's talk about my personal thoughts.
This theorem is very interesting. It tells us two things:
Did you find out?
What is interesting here is that the Diophantine equation is obviously continuously differentiable's (although the Diophantine set has nothing to do with the independent variable of the corresponding function of the equation), and the Turing machine is a very obvious discrete object. These two completely different things at first glance have such a wonderful internal connection.
Moreover, more importantly, in our impression, Turing machines can do what equations and functions can do; But what Turing machine can do, equations and functions may not all be done. It seems strange that these two "functionally unequal" things require the same input parameters.
However, on second thought, it seems necessary. After all, there are as many Diophantine equations as there are Turing machines, both of which are Alef 0, so it seems normal to have such a mapping relationship.
In fact, the reason why the parameters of Diophantine function are used instead of input variables to correspond to the input state of Turing machine is because for polynomial functions such as Diophantine function, as long as the input variables are not infinite, it can always give integer output; But if the coefficient is not appropriate, then the equation may not find an integer solution. So it seems reasonable to use parameters instead of variables to correspond-we can even "guess" that those integer solutions may use the internal state or even output of the corresponding type of Turing machine to some extent, who knows.
I even guess that for any Turing machine that maps A input data to B output data, under any coding rules (mapping data to natural numbers), at least a set of Diophantine functions (integer coefficient polynomials) can be found to correspond to them one by one. There are B groups of Diophantine functions, and each group has an independent input variable.
But then, I think that such isomorphic mapping should not exist, because first of all, any such Diophantine function group must be mapped to a kind of Turing machine, and the characteristic of this kind of Diophantine function is that it can only output an integer for any input, that is to say, the Turing machine corresponding to each such Diophantine function group must be able to stop at the acceptance state for any input-but this is obviously not a situation that any Turing machine can satisfy, so there must be a Turing machine that cannot satisfy this.
So here again, the advantages of using the parameters of Diophantine function to correspond to the input of Turing machine are reflected.
Well, instead of obsessing about the surprise brought by this internal connection, let's consider this question:
Can these two sets be expanded?
Especially, in Diophantine approximation, we no longer require that the parameters of Diophantine equation must be integers, but can be arbitrary real numbers. In this way, all subsets of real coefficients that can make a Diophantine equation have integer solutions are "extended Diophantine sets" of Diophantine equations.
For example, the Diophantine set of this Diophantine equation is:
Its extended Diophantine set can be:
Obviously much larger, the former is only a subset of the latter.
However, such expansion does not seem to be "wild" enough. Let's look at the following:
It is a functional called Diophantine Functional, in which the sum of functions is called parametric function, and the function is a test function, which requires any subset of real numbers to be called "restricted domain" and any subset of another real number to be called "active domain". Assuming that the equation exists and holds, then the binary group is called a universal parameter group of the Diophantine Problem Group. The set of all universal parameter groups of is the "universal Diophantine set" of this Diophantine functional.
Note that the, and functions here are not required to be smooth or even continuous, so they can be piecewise functions. There is no requirement for active domain and restricted domain, and it can be a countable set, a discrete set (in both cases, the integral becomes sum) or a Hausdorff set. We can generally discuss the pan-Diophantine set by fixing the active domain and the restricted domain.
Obviously, when the pan-Diophantine set is a superset of the above-mentioned extended Diophantine set and Diophantine set.
Or, more formally:
Since the expansion of Diophantine set is very unrestrained, what about the expansion of ergodic countable set?
Or, it can be asked more accurately here, that is, how to play the extension of Turing machine.
In the previous definition of Turing machine, there are several discrete sets:
What if both sets are generalized?
Like this:
Taking any space as the base space, any element in the base space will directly produce an eigenspace (without discreteness and finiteness), which is called "external space". Then, there is a "particle" on the table, which corresponds to an element in the table and is called "position". There is also an "internal state" whose value is in the "internal state space".
Now, the bottom space, the external state space and the internal state space need not be discrete or limited, but can be any set.
Actually, it's a little fiber bundle, but it's different.
The transfer rule is the same as that mentioned above. First, change the external state of the particle position, then change the internal state of the particle, and then move the particle to a new position. Its function is a bit like the connection in differential geometry-but we don't require that this kind of motion can only move in adjacent positions, so it can be said to be a kinematic problem on the fiber bundle with wormhole structure added. Of course, we can also limit the position change here to move only in the neighborhood of the current point, just as the read-write head in the standard Turing machine can only move one space from left to right, which looks more like a kinematic problem, and the change of internal state and external state looks more like the work of master-slave communication and bottom manifold communication.
Once the particle's world line enters the "undefined" region, it is rejected and stopped-this can be compared with the singularity falling into a black hole.
It is also possible that particles move to a specific area on the bottom manifold, are accepted and stop-it can be compared to closing the universe and reaching the end of fate.
It is also possible that the world line of particles will never stop and keep spinning in a certain area-comparable to the open universe that will never end.
The initial state of this super Turing machine, that is, the initial state of the bottom manifold, can be compared to the state of the universe in BIGBANG.
Well, compared with analogical classification, space-time is certainly not a super Turing machine under this definition-probably not.
Now, the input state (and output state) of this super Turing machine is not a discrete set.
If it is a continuous space, such as a differential manifold, then the input state can be a curve or a surface on the graph. The external state of points outside this curve or surface is 0, and the external state of points on this curve or surface constitutes the input state.
Therefore, obviously, in theory, there can be a corresponding relationship between the Pan-Diophantine set and the acceptable input states here.
So, here's the question:
Is there always a one-to-one correspondence between the acceptable initial state of any of the above extended hyper-Turing machines and a pan-Diophantine set?
If you open a brain hole, it's like this:
Is there always a one-to-one correspondence between the initial state of the closed universe and the set of Pan-Diophantine graphs under any physical rules?
This brain hole is more unrestrained-although it is better and has no practical significance.
A joke is a joke, but the problem still exists.
We extend Diophantine set and Turing machine respectively to make them as "continuous" as possible, and then ask whether there is a one-to-one correspondence between the corresponding Pan-Diophantine set and the hyper-Turing recognizable set, just like between Diophantine set and Turing recognizable set.
Of course, I certainly can't answer this question now.
Let's look at something else.
Such as compressibility.
In the field of Turing machine, compressibility is related to the complexity of the algorithm, as follows:
Here we deliberately separate the Turing machine from its input parameters. The definition of k complexity of any string S is given above. If it is less than, then we say that S is compressible.
Now, let's try to transplant the problem to the Super Turing Machine (HTM).
We call this function the state function of the super Turing machine. The state function before the operation is called the initial state, which is the input state accepted by the super Turing machine. An element on the table is called the initial position, which means that the "particle" representing the read-write head will move from the initial position. If the particle finally moves to the specified "end position", it means that the super Turing machine stops in the acceptance state, and the state function at this time is called the final state.
Therefore, stopping at the recognized super Turing machine is the mapping:.
Below, we can define an energy function, which can define the energy of a state:
On the other hand, the transfer function itself can also be encoded. Although we don't know how to code it at present, it can be written formally, so its energy can be calculated as follows:
We can take the energy of the transfer rule of a super Turing machine as the energy of this super Turing machine, so that we can formally define the "algorithm complexity":
If so, then we say that the state function is compressible.
From an analogy point of view, compressible state means a state in which energy can be further reduced, and actually corresponds to a state in which entropy can be further increased. Therefore, in this system, the "thermodynamic entropy" and information entropy of the super Turing machine should be equivalent, and the incompressible state is "blackbody radiation".
Of course, again, this analogy is only suitable for opening a brain hole and has little practical significance.
Or, we can also look at incompressibility from an algebraic point of view, just like the idea of three points in ten wines:
A given set of functions is said to be compressible in the world if the following relationship holds:
That is, at least one function allows any data item to be derived from other data in a given set. We will record this relationship as.
In fact, this form of data is very common. For example, if we choose a D-dimensional vector space, there is only one vector addition in the function set, and the data set takes D basis vectors of this D-dimensional vector space. Because they are obviously linearly independent of each other, this data set cannot be compressed on the vector addition set.
Of course, there are many compressible sets. For example, now we use vector addition and vector multiplication to replace the function set in the above particles, and only need two basis vectors. The third basis vector can be obtained by the external multiplication of these two basis vectors, so it can be compressed.
Of course, the problem can be more complicated-assuming that the data set is incompressible on the function set, but if the data set is added, the set is compressible on the table, then this situation is very interesting.
We can construct a function like this:
Therefore, if it is compressible in the world, then.
Similarly, we can also construct a subset of, and all elements in can be constructed with AND function. We remember that it is a data set generated by a function, so it obviously exists. So we can define another function:
So this function represents the incompressible part of the data set, if.
These two functions can describe many characteristics of sum to some extent.
But how this property corresponds to Turing machine seems a bit confusing-if we change the function set here to all possible Turing machines, it is obvious that we can compress any integer set to leave no remainder, so in the case of Turing machine, we will ask to add the "length" of Turing machine itself.
But on the question of function, the "length" of function is unknown to us. Of course, we can encode the function as mentioned in the previous part, and then use the encoding length to represent the "length" of the function, but this will be very impure to indicate compressibility.
Lala wrote a lot of ideas when she looked at the correspondence between Diophantine set and recursive countable set, which were basically brain holes.
This piece feels very interesting, but unfortunately I haven't had time to look at it systematically.
This article abides by the CC BY-NC-SA 4.0 protocol for creative enjoyment.