Does Hilbert’s tenth problem contradict an algorithmic universe?
The limits of algorithmic formalization
Hilbert’s tenth problem posed:
«Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.»
A diophantine equation is a polynomial equation with integer coefficients of which the possible integer solutions are sought. Evidently, an apparently non-diophantine equation is diophantine if it is equivalent to a diophantine equation or a system of diophantine equations. This happens with the exponential function, for example, which is diophantine because it is equivalent to a system of thirteen diophantine equations. If these thirteen equations have integer solutions, the exponential function has an integer solution.
But returning to Hilbert, the answer to his question is relatively simple. Suppose a non-recursive or non-computable set U. We know that such sets exist, even if they arise from recursive processes. For example, the function Σ(n), which defines the maximum number of ones written by a Turing machine with n states that eventually halts, is not recursive or computable. That is, we cannot establish an algorithm that can determine its values.
Well, suppose a nonrecursive set K similar or equal to U. And now suppose that k∈K if and only if it is a solution of a diophantal polynomial equation P(k), perhaps with more variables.
If we had an algorithm to determine whether each of the diophantine equations of P(k) has a solution, then we would also have an algorithm to determine whether or not any k is in K. And the latter is impossible, because K is noncomputable. Thus, Hilbert’s tenth problem has no solution and its answer is negative: there is no algorithm that allows us to determine whether any diophantine equation has a solution in integers.
This is not a relative limitation but an absolute one. It is not that we do not know such an algorithm but that it does not exist. Therefore, it sets limitations to knowledge, to our knowledge. This does not mean that we cannot find solutions to a diophantine equation, but that there is no finite method, no algorithm, to find them.
Years later, in the 1970s, Hilbert’s tenth problem was completed, by means of the Matiyasevich-Robinson-Davis-Putnam theorem which states:
«Every recursively numerable set is diophantine, and the converse.» Put in simplified form, a diophantine set is a subset of natural numbers that are solutions of a diophantine equation, which may have more variables. It is obvious that every diophantine set is recursively numerable, since it is a set formed by natural numbers. On the other hand, that every recursively numerable set is diophantine means that any set with natural numbers that we can number recursively is a solution of a diophantine equation, which can have more variables. But we know that there are such sets that are not computable, such as the set U mentioned above, which confirms the impossibility of achieving a general algorithm that can determine whether any diophantine equation has integer solutions.
The non-existence of the algorithm posed by Hilbert’s tenth problem to me raises very serious doubts about the possibility of the universe being strictly algorithmic (at least what we currently understand by algorithm), which obviously does not mean that it cannot be mathematical. If reality were just an algorithm and there are real phenomena that can be modeled by means of diophantine equations, then the algorithm that Hilbert asked about should exist. And it does not exist.
According to some non-Platonist tendencies in the philosophy of mathematics, concepts such as the continuum or the real numbers do not exist in physical reality, even though they may be useful to us in constructing our scientific theories. If we consider that the universe is discrete, finite and completely computable, then it must work only with natural numbers and thanks to an algorithm. But diophantine equations with integer coefficients and integer solutions fall within the landscape of the natural numbers, so the impossibility of being able to construct a universal algorithm that allows us to determine whether these equations have such solutions makes it clear that the algorithmization of everything is impossible. The formalization of everything through recursive procedures with a finite number of steps is not feasible, as Gödel already warned, destroying Hilbert’s dream.
But not only that. If some kind of universal algorithm were possible to be able to answer Hilbert’s tenth problem in the affirmative, that algorithm could not be what we currently call an algorithm, that is, a procedure with a finite number of steps in finite time, but would have to be an algorithm with an infinite number of steps in finite time. And this hints to us that concepts such as the continuum or the real numbers could have a representation in reality, being then computable, if and only if it can be designed at some point in time in such an algorithm. That is, if we assume the current definition of computability, the universe is not an algorithm, and if we intend the universe to be an algorithm, then the notion of computability must be extended.
Always trying to bring new ideas or new approaches to existing ideas.
Self taught.
Knowledge matters more than degrees.
Questions reveal more than answers.
