> On 17 Jun 2018, at 02:18, Jason Resch <[email protected]> wrote:
>
> In solving Hilbert's 10th problem
> <https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem> in the negative,
> the work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson
> culminated in 1970 with the MRDP theorem
> <https://en.wikipedia.org/wiki/Diophantine_set#Matiyasevich's_theorem> which
> concludes:
>
> Every computably enumerable set has a representation as a Diophantine
> equation <https://en.wikipedia.org/wiki/Diophantine_equation> (an equation
> involving only integer coefficients and variables).
>
> This shocked number theorists, because it meant simple equations involving
> nothing more than a few integer variables have the full power of Turing
> machines. In fact, it was shown by Yuri Matiyasevich that a universal
> Diophantine equation can be made with as few as 9 unknowns.
>
> Some examples:
> k is even if there exists a solution to: k - 2x = 0
> k is a perfect square if there exists a solution to: k - x^2 = 0
> k is a Fibonacci number if there exists a solution to: k^4 - k^2*x^2 - x^4 -
> 1 = 0
> (k+2) is a prime number if there exists a solution to the sum of: (these 14
> equations <http://mathworld.wolfram.com/PrimeDiophantineEquations.html>)
> k is a LISP program having output n, if the equation having variables: k, n,
> x1, x2, x3 ... x20000 (a polynomial having ~20,000 variables
> <https://arxiv.org/pdf/math/0404335.pdf>) has a solution.
> The universality of Diophantine equations means there are polynomial
> equations that compute things quite surprising, such as polynomials that have
> solutions of 0, IFF:
> One of the variables "k" is a valid MP3 file.
> One of the variables "k" is a JPEG image containing the image of a cat (where
> the equation implements the same computation as a neural network trained to
> recognize images of cats)
> For two of the variables "y" and "x", "y" equals a state of a chess board
> after deep blue makes a move given a chess board with a state of "x".
> For two of the variables "y" and "x", "y" equals the state of the Universal
> Dovetailer after performing "n" steps of execution.
>
> The last example seems to suggest to me, that pure arithmetical truth,
> concerning the solutions to equations, is identical to computation. That is
> to say, certain mathematical statements carry with them (effectively) Turing
> machines, and their executions.
Matiyazevic results is indeed quite impressive. It finishes an inquiry begun by
Davis and Putnam with important progress by Julia Robinson, and eventually
Matiyazevic got the proof, and its solved the 10th problem of Hilbert: there is
no mechanical procedure to tell if a diophantine polynomial equation has a
solution or not. (Assuming Church’s thesis, as Matiyzevic explains well in a
ten page section in his book).
>
> Just as all solutions to the deep-blue implementing equation is equivalent to
> the computations that Deep blue makes when evaluating the board, and all
> solutions to the cat recognizing equation are equivalent to the processing
> done by the trained neural network, all solutions to the LISP equation are
> equivalent to the execution of every possible LISP program (including the UD).
>
> Does this our conscious experience might be a direct consequence of
> Diophantine equations?
Yes. Although you could *equivalently* say that our conscious experience is a
direct consequence of the combinators laws Kxy = x and Sxyz = xz(yz). Which is
certainly shorter than providing a degree 4 universal Diophantine equation,
like below (I can’t resist):
(unknowns range on the non negative integers (= 0 included)
31 unknowns: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, W, Z,
U, Y, Al, Ga, Et, Th, La, Ta, Ph, and two parameters: Nu and X.
X is in W_Nu iff phi_Nu(X) stop if and only if
Nu = ((ZUY)^2 + U)^2 + Y
ELG^2 + Al = (B - XY)Q^2
Qu = B^(5^60)
La + Qu^4 = 1 + LaB^5
Th + 2Z = B^5
L = U + TTh
E = Y + MTh
N = Q^16
R = [G + EQ^3 + LQ^5 + (2(E - ZLa)(1 + XB^5 + G)^4 + LaB^5 + +
LaB^5Q^4)Q^4](N^2 -N)
+ [Q^3 -BL + L + ThLaQ^3 + (B^5 - 2)Q^5] (N^2 - 1)
P = 2W(S^2)(R^2)N^2
(P^2)K^2 - K^2 + 1 = Ta^2
4(c - KSN^2)^2 + Et = K^2
K = R + 1 + HP - H
A = (WN^2 + 1)RSN^2
C = 2R + 1 Ph
D = BW + CA -2C + 4AGa -5Ga
D^2 = (A^2 - 1)C^2 + 1
F^2 = (A^2 - 1)(I^2)C^4 + 1
(D + OF)^2 = ((A + F^2(D^2 - A^2))^2 - 1)(2R + 1 + JC)^2 + 1
END
>
> Can Diophantine equations for a single set of parameters model non-halting
> programs like the UD, or one must consider the set of of all possible
> parameters?
In this case we model the recursively enumerable set, and they are determined
by by the existence of the solutions when you fix Nu and X, the programs and
the argument. Phi_Nu(X). But you can take a Nu which is itself universal, and
then look only at all solution for each X, or, make X a dummy variable, and use
a Nu such that phi_Nu(X) is a universal dovetailer. Its “leaves” will enumerate
the true sigma_1 sentences, which emulates all dreams.
Bruno
>
> Jason
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected]
> <mailto:[email protected]>.
> To post to this group, send email to [email protected]
> <mailto:[email protected]>.
> Visit this group at https://groups.google.com/group/everything-list
> <https://groups.google.com/group/everything-list>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
