> On 25 Jun 2018, at 02:54, Jason Resch <[email protected]> wrote: > > > > On Fri, Jun 22, 2018 at 5:41 AM, Bruno Marchal <[email protected] > <mailto:[email protected]>> wrote: > >> On 20 Jun 2018, at 14:55, Jason Resch <[email protected] >> <mailto:[email protected]>> wrote: >> >> >> >> On Tue, Jun 19, 2018 at 11:36 AM, Bruno Marchal <[email protected] >> <mailto:[email protected]>> wrote: >> >>> On 17 Jun 2018, at 02:18, Jason Resch <[email protected] >>> <mailto:[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). >> >> >> Do you have some references that you would recommend for someone wanting to >> learn more about combinator laws and how they lead to universality? > > I would simply recommend Smullyan’s book “How to mock a mocking bird?”, which > proves in details the Turing universality of the combinators. > > > > Thank you! I actually had a copy of this on my shelf, but I had yet to read > it. I'll start tonight. :-) > > > >> Is the above the same thing as a Y-combinator, or some more specific >> equation in lamda calculus or combinatorial logic? I wish to lean more. > > The Y combinator is the fixed point of Yx = x(Yx). All fixed point equation > can be solved in combinatory logic. The Y combinator can be used to program > the “definition by primitive recursion”, but, as Smullyan shows well, you can > easily start from scratch and use the Dxyz = T(xx)yz trick. You need to be > able to eliminate variables from combinations, but this too is well explained > by Smullyan. His last book “A Beginner’s Further Guide to Mathematical Logic” > contains a rather detailed summary of his book “How to Mock a Mocking Bird”. > I have some rare text by Rosser, in French, on the combinators, which are > very good, but uneasy to find, but maybe in second hand bookshop, notably his > “Deux Esquisses de Logique”. > The classical treatise is the North Holland book by Barendrecht. Not to > mention the historical, a bit verbose, treaties by Curry and Feys (Feys was a > teacher of religion in secondary public Belgium school). > > > > > Thanks for those references. I want to get an intuitive feel for how "Kxy = > x and Sxyz = xz(yz)" achieves universality so succinctly compared to > arithmetic equations. I will first see how far Smullyan's book takes me. > >> >> >> 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 >> >> >> >> I don't quite follow what W_Nu is here. > > The domain of the function phi_Nu. Nu is just a natural number, and phi_i is > an enumeration of all partial computable functions. You can generate it by > generating all programs (of one variable) in any programming language. > > > >> >> I am guessing from the context that this means for a given machine/program >> Nu, and input X, this equation has a solution IFF Nu halts given X as input, >> but I am not sure what it means to say X is in W_Nu. > > You got it. It means nothing more than the Nu-th program P_Nu (or simply Nu) > stops on input X. > It can be proved that the W_i (the domain of the phi_i) enumerates all > recursively enumerable set. > > > >> >> >> >> 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 >> >> >> >> Very nice. Where is this from? (Is there a paper that gives these equations?) > > Yes. > > Perhaps this one. I have only an incomplete photocopy, and it might be > another paper by Jones. > You might find it also in Matiyazvic’s book. > > "Three Universal Representations of Recursively Enumerable Sets" > > James P. Jones > The Journal of Symbolic Logic, Vol. 43, No. 2 (Jun., 1978), pp. 335-351 > > > > > Great! Thank you. > > This brings up a side question I was curious about. Did you ever publish your > source code for the UD? > It would be cool to write down the equation that implements the UD, with "Nu > = UD". A kind of "god" equation. > > Here is another interesting question, in theory is it possible to create a > 2-dimensional image (in the spirit of Mandelbrot's fractals), where the X and > Y cells are "Nu" and "X" respectively, and the color of each (X,Y) cell is > based on how rapidly the machine halts (perhaps on some logarithmic basis) or > black if it not determined to not halt? > > If I'm not mistaken, I believe in the past you had hinted that you had the > idea that the Mandelbrot set might itself be universal (in its > computations?). I was curious if you could provide some further explanations > about this. > > > > >> >> >>> >>> 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. >> >> >> >> I guess the problem I am having is that Phi_Nu(X) doesn't halt, then it has >> no solution. So what can be said about programs like the UD which don't >> halt, other than that there exists no solution to the above equations when >> "Nu = the UD". Would it be better to establish the trace of the UD by >> having "Nu" be a program that outputs the state of the UD at time "X", thus >> the equation still captures the UD and all its computations, but now with a >> halting program whose solutions match the solutions to the Diophantine >> equation? > > If you do that, you will need to ask infinitely many question to that UD, for > it to emulate all programs. It is better to let it generates the X too, so > you have no more any tasks to do, after pushing “enter”. > > But if there are no solutions to the polynomial for machines that don't halt, > it seems there is no distinction between a so-called "valid combination of > inputs" and a completely arbitrary combination of inputs (if this makes > sense). Or is it the case that enumerating all possible combinations of > inputs somehow still implements the never-halting computation? > > Of course W_u is the empty set, for that UD = u. But in this case, you are > not interested in its empty domain, only in its execution. > Now, you can also consider a W_k, say, such that W_k generates all states > accessible by the UD. In that case, the W_k emulates itself the UD. > > > > Ahh okay. This makes sense to me and can more succinctly be described as the > set of infinite solutions to the equation is equivalent to the infinite > execution of the UD. > > >> >> But perhaps it's better to just leave Nu a free variable, and get all the >> halting computations as solutions. Is this what you mean by the "leaves of >> the UD"-- those programs that halt? > > Well, I could, but you can take the intermodeidate steps of the computations > too. There are different ways to proceed. Davis’ “Unsolvability and > computability” defines computations by halting computations. Daniel Cohen use > arbitrary computations. As long as you get all states, the UD will do its > job, with the right redundancy. > > > What did Danial Cohen mean by "arbitrary computations”?
Stopping and non stopping one. Martin Davis defines computations by halting computation, making them equivalent to true sigma_1 sentences. It ease some proofs, like it eases the UD first person probability problem. > > >> >> How do you define a "sigma1 true sentence"; is a sigma1 sentence just >> statements/asserts of arithmetical relations that can be true or false? > > It is a arithmetical statement equivalent with ExP(x), with P sigma_0, that > is recursive (total computable). > > Any machine capable of proving all true statements with that shape is Turing > universal, and any Universal machine or machinery is complete for such > statement. Robinson Arithmetic RA (Peano arithmetic without induction) is > such a theory. It is Turing universal, but it is not Löbian, as it cannot > prove, unlike PA, its own Turing universality. > > OK? > > > So if they are everything provable by a machine, are they equivalent to a > recursive enumeration of everything probable [provable, I guess] under some > axiomatic system? Do sigma1 sentences assume any particular axiomatic system? The truth of the sigma_1 sentences can be proved in any Turing complete theory, like RA, PA, ZF, etc. They all proves the same sigma_1 sentences (up to their translation of course). If you want, "provable by a Turing complete theory” is equivalent to “computable with a Turing machine”. Sigma_1 provability is yet another formalism for computability, with the advantage that it is embed in the provability realm (much richer than computability, but not universal with respect to *proof*, by Gödel’s theorems). 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.
