> 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)}.

- 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 

- 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”.

> 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 

Constructive proof of sigma_1 sentences can be seen as equivalent to halting 

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.

> 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 

> 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.


(*) Blum L., Cucker F., Shub M., Smale S. Complexity and Real Computation, 
1998, Springer Verlag, New-York.

> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/CA%2BBCJUizGA5wN9KOLynozbovu0KpJjgf%3DA6jf24fMXdcr1fVTg%40mail.gmail.com
> <https://groups.google.com/d/msgid/everything-list/CA%2BBCJUizGA5wN9KOLynozbovu0KpJjgf%3DA6jf24fMXdcr1fVTg%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 

Reply via email to