On Wed, Aug 14, 2019 at 5:02 AM Bruno Marchal <marc...@ulb.ac.be> wrote:
>
> On 12 Aug 2019, at 23:36, Jason Resch <jasonre...@gmail.com> 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.
>
> - 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.
>
>
> 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 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 (is it the arithmetical truth of the relation
that is conscious, or the processing of information by the computation that
is conscious), is there really no important difference between the
Diophantine proof and the constructive proof generated by the operation of
a Turing machine?
(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://eprint.iacr.org/2013/507.pdf they have numerous practical
applications but are computationally difficult to create (but easy to
check)).
>
>
> 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? 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)?
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 everything-list+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/CA%2BBCJUgsDyggp7k2DKrA1Fm0GYDprzH8ffDhWC%3DxK9Tc%3DazuXw%40mail.gmail.com.
