On Fri, Aug 16, 2019 at 11:05 AM Bruno Marchal <[email protected]> wrote:
> > > The fact that there is a universal Diophantine polynomial is rather > extraordinary. It means that all proofs that some machine do something can > be verified in less than one hundred operations (of addition and > multiplication). From this it can be shown that all (halting) computations > can be done in less than one hundred operations. This means that the > “dynamical content of a computation” can be limited to 100 operations, and > all the rest will belong to statical description of (expectedly) very > gigantic numbers and very long multiplications. > Maybe this is what I was missing. When you say "very gigantic numbers", how large are they? Are they on the order of the memory requirements of the computation * the number of computational steps? Or something along those lines? If so, then I can more easily see how any computation could be equivalent to the evaluation of a Diophantine equation. Before it seemed like cheating, a short-circuit to compute (or at least verify) anything far more easily than usual. Is it the case then, that evaluating the universal Diophantine for some halting program is expected to take as long for a Turing machine to compute as for that same Turing machine to perform the computation? > > There has been some period where I thought this could refute > computationalism. I don’t think it is a threat, even if that is weird. It > is weird that you can test x^(y ^(z^(t^…..^r))))…) = r with 10^1000 nested > exponentiations by only 100 additions and multiplications using only much > less variable/numbers. Some notorious logicians thought that this would > just be impossible, and took some time to discourage the search for a > diophantine polynomial computing (just with addition and multiplication) > the exponential (Julia Robinson already showed that this would lead to the > solution). > > This theorem suggests also that consciousness is mainly in the number > relations, not in the operation emulating the computation, but this we > already knew: it makes it more striking. > Indeed. I think I am now starting to grasp this (at least if the numbers involved, and cost of evaluating the polynomials is as large as I think the might be). > > The theorem is proved in the quite remarkable presentation by Martin > Davis, in the Scientific American (I think) of the > Putnam-Davis-Robinson-Matiyazevic's theorem (the universality of > diophantine polynomials) . It has been reprinted in an appendice in the > Dover edition of its “Computability and Unsolvability” book. > Thanks for the reference, do you happen to know if it is one of these? https://www.scientificamerican.com/author/martin-davis/ Was it titled "Hilbert's 10th Problem" ? Jason > I will, soon or later, make a summary of all the “concrete” universal > machinery (the phi_i and w_i) that we have encountered (mainly, Boolean > Graph + Clock/Delay, Elementary Arithmetic, Diophantine Polynomial > Equation, Turing Machine, Register Machine (coffee-bar), LISP, > lambda-expression and the combinators). Each have their own phi_i and w_i, > but all phi_i and w_i obeys the same fundamental “computational” laws, > largely captured by the combinatory algebras and the Models of Lambda > Calculus). > > But to get the intensional nuances, the simplest way consists in using the > phi_i and w_i directly. > > Basically everything follows from two facts, here below, about all > “acceptable” universal machinery (enumeration of the partial computable > function. Note that a total (everywhere defined) function is a particular > case of a partial function): > > - 1) it exist a computable function s such that for all number *x*, *y*, > and *i*, *phi_i (x,y) = phi_s(i, x) (y)* > > (*s* parametrises *x* on *i*) It is the SMN theorem > (here the simplest S21 theorem) > > - 2) it exist a universal number *u* such that for all number *x*, *y* > *phi_u(x,y) > = phi_x (y).* > > A lot can be deduced from this. I build a self-regeretaig program > (planaria) using a generalisation by John Case, of the Recursion theorem of > Kleene, which can be proved in five line from just the SMN theorem. > The whole logic of self-reference comes from the fact that PA (ZF, …) can > prove those theorems in arithmetic. > > > That richness has some price, and the universal machine brings a lot of > mess in in (Arithmetical) Platonia, but that mess is also highly > structured, which help when deriving a measure on the computational > histories. > > Bruno > > > > > > > > > > > > > Thank you. > > Jason > > >> >> Note that the parallel worlds are given by perpendicular states. They >> should be called the perpendicular universes. Once two >> “universes/histories" are not perpendicular they can interfere >> “statistically”, and they are inter-reachable “probabilistically” through >> appropriate measurements/interactions. That imposes also some symmetries. >> >> >> Bruno >> >> >> > -- > 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/CA%2BBCJUhL6we1S5Uiq9x_hJAN3PCih_M5-HZBTqgUEDav_1rMcQ%40mail.gmail.com > <https://groups.google.com/d/msgid/everything-list/CA%2BBCJUhL6we1S5Uiq9x_hJAN3PCih_M5-HZBTqgUEDav_1rMcQ%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/545A94B0-C86D-4F2A-B4BB-25800125C60E%40ulb.ac.be > <https://groups.google.com/d/msgid/everything-list/545A94B0-C86D-4F2A-B4BB-25800125C60E%40ulb.ac.be?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/CA%2BBCJUhnM_89ZKThHC98CcLeX0dtPD9QKRjqURZaK_k_VG36YQ%40mail.gmail.com.
