> On 21 Aug 2019, at 18:04, Jason Resch <jasonre...@gmail.com> wrote:
>
>
>
> On Fri, Aug 16, 2019 at 11:05 AM Bruno Marchal <marc...@ulb.ac.be
> <mailto:marc...@ulb.ac.be>> 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?
To emulate a part of a long computation, the numbers will be absolutely
gigantic, a bit like a description of your digital state. Imagine you want to
simulate only our cluster of galaxies, you will need something like the
description of the state of that cluster. To emulate the entire multiverse will
asks for much less information, like a “vacuum state” and the equations. But in
arithmetic you have both, and with some luck, the least programs are the
“winner”. This would explain why the physical laws are easy to compute when we
accept to do some approximations, and very hard to compute when we want all
details exact.
> Are they on the order of the memory requirements of the computation * the
> number of computational steps? Or something along those lines?
They need apparent big amount of contingent information, when we emulate a
subpart of the whole physical reality. That can can explicitly give the number
of computational steps, but it use also the content of the special current
memories of the person, or system, to be emulated.
>
> 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?
Yes. You can derive this from the “intensional Church-Turing thesis”. Not only
all universal machinery compte exactly the same (partial and total) computable
functions, but they can emulate each other, that is, each universal machine can
compute each computable function in exactly the same way. You can find a
diophantine polynomial emulating (simulating exactly) a pattern of of the game
of life, itself emulating a Fortran programs, etc. When they do that, they take
the same time, up to some mutiplicative constant (which is not first person
accessible, and that explain why we can start from any universal machinery).
Implementation is always defined relatively to a universal machinery. It
happens that the physical reality is Turing complete, so we have a notion of
physical implementation. That is still a bit of a mystery. Today, we can’t
claim that Mechanism has evacuated all “white rabbits”, but note that this is
the case also in quantum field theory, despite the theory of renormalisation
which solves the problem partially (I think).
>
>
> 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).
Let me give you a universal system of polynomial Diophantine equations. It is
“short” as we use many variables, and we allow a degree bigger than 4 (4 is
enough, but then you need much more variables), and we allow more than one
equation. The variables range on the non negative integers (= 0 included)
There are 31 unknown variables: 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.
The number X is in the recursively enumerable set W_Nu iff phi_Nu(X) stop if
and only if there are number A, B, C, … Th, La, Ta, such that:
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
That is just incredible!
Searching all solutions A, B, C, D … ( for all X and Nu) is equivalent with a
universal dovetailing.
>
>
> 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/
> <https://www.scientificamerican.com/author/martin-davis/>
> Was it titled "Hilbert's 10th Problem” ?
Yes. The appendice of the last editions of his book “computability and
unsolvability", notably published by Dover, is a reprint, slightly ameliorated
(I think), of his paper in the Scientific American. It is a more readable proof
than the original by Matiyazevic (itself built from the work of Putnam, Davis,
and Julia Robinson).
The book by Daniel E. Cohen “Computability and Logic” contains also a nice
proof of Matiyazevic’s result, but is more concise and asks for a lot of work.
What is nice is that it gives the (already extraordinary and quite enough for
our use of this) Robinson theorem that the exponential Diophantine equation
(where we allow exponentiation of variable in the “polynomials” is Turing
universal. The remaining problem solved by Matyazevic was to show that 2^x is
polynomial diophantine.
Bruno
>
> 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 everything-list+unsubscr...@googlegroups.com
>> <mailto:everything-list+unsubscr...@googlegroups.com>.
>> 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 everything-list+unsubscr...@googlegroups.com
> <mailto:everything-list+unsubscr...@googlegroups.com>.
> 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 everything-list+unsubscr...@googlegroups.com
> <mailto:everything-list+unsubscr...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/everything-list/CA%2BBCJUhnM_89ZKThHC98CcLeX0dtPD9QKRjqURZaK_k_VG36YQ%40mail.gmail.com
>
> <https://groups.google.com/d/msgid/everything-list/CA%2BBCJUhnM_89ZKThHC98CcLeX0dtPD9QKRjqURZaK_k_VG36YQ%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 everything-list+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/B9837672-35CA-4F8B-A349-9D07B1B84988%40ulb.ac.be.
