> On 25 Jun 2018, at 02:54, Jason Resch <jasonre...@gmail.com> wrote: > > > > On Fri, Jun 22, 2018 at 5:41 AM, Bruno Marchal <marc...@ulb.ac.be > <mailto:marc...@ulb.ac.be>> wrote: > >> On 20 Jun 2018, at 14:55, Jason Resch <jasonre...@gmail.com >> <mailto:jasonre...@gmail.com>> wrote: >> >> >> >> On Tue, Jun 19, 2018 at 11:36 AM, Bruno Marchal <marc...@ulb.ac.be >> <mailto:marc...@ulb.ac.be>> wrote: >> >>> On 17 Jun 2018, at 02:18, Jason Resch <jasonre...@gmail.com >>> <mailto:jasonre...@gmail.com>> 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 everything-list+unsubscr...@googlegroups.com > <mailto:everything-list+unsubscr...@googlegroups.com>. > To post to this group, send email to everything-list@googlegroups.com > <mailto:everything-list@googlegroups.com>. > 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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
