> On 16 Aug 2019, at 19:06, Jason Resch <[email protected]> wrote: > > > > On Wed, Aug 14, 2019 at 5:02 AM Bruno Marchal <[email protected] > <mailto:[email protected]>> wrote: > >> On 12 Aug 2019, at 23:36, Jason Resch <[email protected] >> <mailto:[email protected]>> wrote: >> >> In "The Universal Numbers. From Biology to Physics" Bruno writes >> >> "The universal dovetailing can be seen as the proofs of all true Sigma_1 >> propositions there exists x,y,z such that P_x(y) = z, with some sequences of >> such propositions mimicking the infinite failing or proving some false >> Sigma_1 propositions." >> >> This is something I was thinking about recently in the context of universal >> Diophantine equations. It seems more correct to me to say these equations >> don't themselves represent the execution traces of the programs, but rather >> represent proofs of the outputs of programs. >> >> This can be seen from the fact that the work of verifying a Diophantine >> equation requires only a finite and constant number of arithmetical >> operations, while the computation itself could involve much more work, in >> terms of arithmetical steps. >> >> > > > We have to distinguish > > - a computable function (from N to N, say), That is an infinite object, which > can be represented by an infinite set (the set of input-output). That set is > often called the “graph” of the function. We can show that if the function is > computable, its graph is mechanically generable (recursively enumerable). > Such a set can be described by a sigma_1 sentence (that is a sentence having > the shape {y such that ExP(x, y)}. > > Does the identity between a computation (in terms of discrete steps with > counterfactual behavior), and its representation as the set of all inputs to > outputs imply that the Blockhead (giant state table brain) possesses > consciousness of the same form as the incrementally processed computation? > Perhaps I just have too myopic of a view of what computation is from my > familiarity with programming.
You cannot identify a computation and a representation of that computation. So the answer is no: the blockhead or the infinite look-up table does not process a computation. Now, if in a theory, say ZF, you can define that representation of computation and prove that it represents a computation, then it in the model at that theory, it might make sense to say that it proves the existence of a computation, but the computations cannot be identified with its representation, even if the proof of the existence of that representation can be used to prove the existence of a computation, but only if that is proved itself in the theory (and that the theory is consistent, so that it has a model, where the computation will exist or be realised). > > > - The code of a computable function. That is a finite object (representable > using some word or numbers, or finite set, …). I use usually the word > “digital machine” for this. It is the (virtual) body of the machine. It is > finitely describable. > > - a computation. That is either a finite or an infinite thing, usually > representable by a sequence of numbers or words, called the trace of the > computation). Some author call “computation” only the computations which > halt, and thus are finite, like Martin Davis in the book “Computability and > Unsolvability). Other like Daniel E. Cohen, and me most of the time, admits > the term “computation” for non halting, and thus infinite, one. > > With, this you can guess that when you have an halting computation, you have > automatically a proof of a sigma_1 sentence (like the sentence saying that > some input-output (x,y) belongs to the graph of that function, or that x > belongs to its domain). > > Unfortunately, the reciprocal is not necessarily true. We can find a proof of > a sigma_1 sentence which would not be a computation, like an indirect proof > by a reduction ad absurdum which can be a non constructive proof of an > existential statement. Such a proof would state that a computation is > halting, without executing that computation. > > So, proofs (of sigma_1 sentence) are not necessarily a computation, and as > such will not belong to the universal dovetailing directly, although the > universal dovetailing will emulate some subjects doing those non-constructive > proof, but that gives a computation emulating a reasoning process, and that > reasoning process does not need to be a computation. > > Inversely, as I said, a computation can be seen as a proof of a sigma_1 > sentence. There is a theorem which makes this precise: the normal form > theorem of Kleene, which shows that there are computable (and elementary, > primitive recursive, if people remember the definition) U and T such that if > f(x) is a computable function, computed by the code z, then > > y = f(x) = U(the least c (T(z, x, c)). > > T(z, x, c) is Kleene’s predicate. It says that z is the Gödel number of a > (partial) computable function, x is the input given to the machine with code > z, and y is an halting computation given by the machine with code z when > applied to x. > U is the result extracting function, which gives the output y from the > computation c. Usually U just take the last line of the computation, for > example. This results shows that you can always program a computable function > with one “while”, or that you can always well structure a code (suppress all > the “goto”-like instruction by just one “while”. > > I think this fact (of implementing any program with a single loop) explains > both why recursive functions are Turing complete and why CPUs can work by > simply repeating the application of some electrical circuit over and over > again. The enumeration of all partial recursive functions is Turing complete/univeral (by definition), and one partial recursive function (the universal one) is Turing complete/universal, also by definition. (The term “complete” is reserved for theories, and “universal” is used for function or machine). Now, some CPU might implements more than one loop, for reason of efficiency. > > > >> So is it right to say that the proof of the result of some computable >> function is different from the computable function itself? > > So, the proof is different from the computable function, and from its code. > But the computation (if it halts on some input) will provide gives a proof > that x belongs to its domain, or a proof that (x, y) belongs to its graph, if > y = U(c) like above. > > Note that if a proof is sufficiently constructive, it will be (equivalent) to > a computation. > > Constructive proof of sigma_1 sentences can be seen as equivalent to halting > computation. > > Halting computation can be seen as equivalent to (constructive) proof. > > > >> In other words, a fixed Diophantine equation, regardless of the values of >> its variables, does not itself yield conscious mind states, though it points >> to the existence of another object in math (the universal machine) whose >> operation would yield the conscious mind states? > > > Diophantine polynomial are Turing universal, so there is a specific > Diophantine polynomial which is universal. > There is a universal Diophantine polynomial equation, like there is universal > Turing machine, a universal combinators, a universal lambda expression, a > universal game of life pattern, etc. Now, such an equation (combinators, > machines, pattern) can be seen as a code. It is a finite static thing, and > there is no consciousness associated with it per se, but there will be a > consciousness associated to the verifying process if that polynomial equation > as this or that particular number as solution. > > > > While I agree and understand that universal Diophantine polynomial solutions > have the same form as any computable set, is the Diophantine equation more > correctly viewed a computation, or as a proof of correctness for some > computation? In this case, the computation is either in the search of a solution of a (non universal) polynomial Diophantine equation, or in the solution itself of one particular *universal* Diophantine equation. The computation is always in the model, interpretation, or true relation, not in the number relation’s description in a theory. Keep in mind that a computation is an abstract *true* relation between numbers, or physical pieces, or anything which we accept as existing (and that depends on the base theory which is chosen). Now, by universality, we can chose any Turing complete theory, but once it has been chosen, we might need to carefully distinguish the level of “reality”. The universal diophantine polynomial equation is a finite object/program. Searching for all its solution (by a human, or by a game-of-life pattern in some bract space) will be equivalent with the running of a universal dovetailer. It is unfortunately easier to confuse a computation with one of its description, that a number with one of its description, but it is the same type of confusion, on a more sophisticated notion, though. I guess we will have opportunities to come back on this. > In the other thread you mentioned the fact that a nested exponentiation of > 1000 terms can be verified in 100 additions and multiplications. Are these > 100 additions and multiplications truly a sufficient reenactment of the > computational relation in the same form necessary for consciousness Yes. The computation will be in the act of doing those addition and multiplication. You will need to do that already in some model of a Turing complete theory, be it a physical universe, or the arithmetical reality, etc. > (is it the arithmetical truth of the relation that is conscious, or the > processing of information by the computation that is conscious), It is in the processing, but the point, with the universal things, is that the processing is itself in the number relations, the one involving some universal system. > is there really no important difference between the Diophantine proof and the > constructive proof generated by the operation of a Turing machine? There is a difference of level. The true existence relatively to you will depend where you are emulated, a bit like in the explanation of how a virtual typhoon can make you wet. You need to be emulated at the right level. > > (Note, I first learned of and was blown away by the possibility of verifying > any computation in constant time, as it pertains to practical applications in > the form of "zk-SNARKs" (zero knowledge, succinct non-interactive argument of > knowledge) https://www.youtube.com/watch?v=nS3smRAfUd8 > <https://www.youtube.com/watch?v=nS3smRAfUd8> > https://eprint.iacr.org/2013/507.pdf <https://eprint.iacr.org/2013/507.pdf> > they have numerous practical applications but are computationally difficult > to create (but easy to check)). Most of the time, verifying that something meet a specification is far easier than finding that something. But that is still relying on complex conjectures. > > >> >> I am just trying to develop a more clear picture in my mind of the relation >> between arithmetic, proofs, computational traces, and mind states. > > Yes, it can be confusing, not mentioning the confusion between a mathematical > object or statement and their syntactical description. That is even more > confusing for the notion of (halting) computation, which is a finite object, > yet still different from all its finite description. The computation is in > the relation (eventually definable in arithmetic) between token (number) > which makes that description describing a computation (which is an abstract > relation). > > You ask in a sequel: > >> Another comment/question: >> >> "with some sequences of such propositions mimicking the infinite failing or >> proving some false Sigma_1 propositions." >> >> Assuming the undecidability of the Mandelbrot set, does this undedicability >> have the same implications as the above "mimicking the infinite failing or >> proving some false Sigma_1 propositions"? In a poetic manner of speaking, >> does the shape of the Mandelbrot set's edge somehow mirror the shape of >> non-computable functions in the UD? > > That is plausible. Unfortunately, to my knowledge, this is still an open > problem for the Rational Mandelbrot set (the problem of deciding if (a+bi) > with a and b rational belongs to the Mandelbrot set. > > For the “Real” Mandelbrot set (with a and b real) the corresponding problem > has been solved for a special notion of computability with respect to a ring > (or a field), by Blum, Smale and Shub(*). But of course, in that case a+bi > might be an infinite object, and does not represent programs (there is no > “Church-Thesis” for the notion of computability with real numbers: there are > many non equivalent definitions). The work of Blum & Al. is more interesting > for Numerical Analysis than for Number theology or Digital Mechanist > Metaphysics. > > > >> >> Can we infer anything about the existence of all computations from the >> mathematical existence of the complete Mandelbrot set alone? > > Yes, but only trivially. The Mandelbrot assumes the Complex Plane, which is > Turing universal, because it is an extension of first order analysis + a mean > to define the natural numbers and their addition and muliplication. laws. > > But if the conjecture above, on the rational Mandelbrot set, is true, and if > the undecidability is of the usual type (creative set, not simple set, in the > sense of Emil Post), then the Mandelbrot set becomes a compact description of > the universal dovetailing, or of any UD* (the complete running of some UD). > That would be nice, but that is still an open problem. Solving the case on > the real does not help solving the case on the natural numbers. > > Thanks for the background and explanation. Is it the case then that any > undecidable (creative?) set is a compact description of universal > dovetailing? By compact, I meant it in the usual topological-metrical sense. The Mandelbrot set is compact because you can enclose it is a circle. It is bounded geometrical object. It does not apply to set per se. But that is a detail. Now, a set can be undecidable, but not Turing complete (creative). That has been found by Emil Post, with his notion of “simple set”, which are undecidable, but not complete. The complement C of a complete set T is productive: C is constructively not recursively enumerable (RE). It has RE subset, and for each RE subset w_i included in C you can mechanically generate a counter-example: un element g(i) which is not inT, nor in w_i. The complement C of a simple set S is immune (more complex than productive), it has no recursively enumerable subset at all. All attempt to build a w_i in C will cross (intersect) C soon or later. A creative set cannot explore the full universe, but can send more and more powerful rocket exploring it, and for each rocket it can build a more powerful one, like we can extend PA or ZF in the transfinite. A simple set can only build rockets falling back on the ground! > Would Chaitin's constant also qualify as a compact description of the > universal dovetailing (though being a single real number, rather than a set > of rational complex points)? It does not. In fact Chaitin’s set (or “real number”) is not creative (Turing universal) but “simple", in that Post sense given above. You can’t compute anything with Chaitin’s number. It is like a box which contains all the gold of the universe, but there is no keys to open that box. But “Post's number” , which decimals says if the nth program, in an enumeration of programs without inputs, stop or not, is creative, and “equivalent” with a UD* (seen properly in the right structure). But the term ”compact” does not really apply here, unless perhaps you write the digits in smaller and smaller font so that you can write it all on one page. You can look at Chaitin’s number as a maximal compression of Post’s number. Post number is deep, in Bennett sense, where Chaitin numbers is shallow and ultra-random. Chaitin’s number is the Post’s number with all the redundancies removed. You cannot do anything with it, except gives a non constructive proof of Gödel’s incompleteness (which was already in Emil Post, but without that “probability” interpretation of “simplicity”. An interesting paper, that Brent points to me some years ago, which shows this and more is the paper by Calude and Hay: "Every Computably Enumerable Random Real Is Provably Computably Enumerable Random" (arXiv:0808.2220v5). Here: https://arxiv.org/abs/0808.2220 That paper is also useful to see that PA can prove the existence of universal numbers, computations, … (without assuming anything in physics, which could help some people here). But it is a bit technical. It also assume that ZF is arithmetically sound, which I believe, but is not that obvious, especially with Mechanism! Both Chaitin and Post numbers contains all the secrets (of the universal dovetailing), but Chaitin’s number, by removing all the redundancies, is unreadable, and just as good as total randomness or mess. Post’s numbers on the contrary is comprehensible by all universal machines, so to speak. Put in another way: with Post numbers, there is full hope for a decent measure on the relative computational histories. With Chaitin’s number, there is no measure at all, like if all computational histories were unique, somehow. This does not mean that Chaitin’s number is not interesting for Mechanism. I think it will play some role in the thermodynamic of the computationalist physical reality, but not in its origin (which Post’s number does). Bruno > > Jason > > > Bruno > > (*) Blum L., Cucker F., Shub M., Smale S. Complexity and Real Computation, > 1998, Springer Verlag, New-York. > > > > > > > -- > 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 view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/CA%2BBCJUgsDyggp7k2DKrA1Fm0GYDprzH8ffDhWC%3DxK9Tc%3DazuXw%40mail.gmail.com > > <https://groups.google.com/d/msgid/everything-list/CA%2BBCJUgsDyggp7k2DKrA1Fm0GYDprzH8ffDhWC%3DxK9Tc%3DazuXw%40mail.gmail.com?utm_medium=email&utm_source=footer>. -- 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 view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/BC86765B-733E-41AB-97DA-0D99E03112F6%40ulb.ac.be.
