Re: Are proofs equivalent to dovetailing computations?

['Brent Meeker' via Everything List]

On 8/24/2019 1:35 PM, Jason Resch wrote:


That seems more like the arithmetical explanation of the quantum
indeterminacy. The thermodynamics would be more related to some
identification of the length of a finite computation and its code.
A short code leading to a long computation would contain more
energy than a short code leading to a short computation, up to
some constant. But the length of the computation is not enough,
and it is better to use the depth of it (following Bennett). The
UD would have infinite “energy", like arithmetic, but the program
“10 GOTO 10” despite leading to an infinite computation has
basically no energy at all.


Do you envision there being any special properties (for instance, in 
the amplifications of the measure) of those programs shorter than the 
dovetailer, in terms of their contribution to to the statistics of the 
machine psychology?


I'd like to know what the "statistics" are.  Given all these values 
floating around there can be infinitely many statistics formed.


Brent

--
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/f95baf8d-60d6-2858-86f9-64bfbc2c63a8%40verizon.net.

Re: Are proofs equivalent to dovetailing computations?

[Jason Resch]

On Sat, Aug 24, 2019 at 4:52 AM Bruno Marchal  wrote:

>
> On 24 Aug 2019, at 00:23, Jason Resch  wrote:
>
>
>
> On Sat, Aug 17, 2019 at 5:17 AM Bruno Marchal  wrote:
>
>>
>> On 16 Aug 2019, at 19:06, Jason Resch  wrote:
>>
>> 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”.
>>
>
>
> If Chatin's number is a maximally compressed Post's number, what makes one
> creative and the other simple, or one a representation of dovetailing and
> the other not?  Both require infinite computing resources dovetailing on
> all computations in order to generate them (don't they?).  I think I am
> missing something here.
>
>
> Chaitin’s number is the result of the computation, which consists in
> compressing the Post’s number, and making it totally unreadable. The result
> of a computation is not equivalent with the computation leading to that
> result. (That’s why the Adam machine which compute a very long time to get
> the answer 42 is funny :). It can be shown that such computations exist.
> Some predicate can be arbitrarily hard, despite they will answer 0, or 1.
> That can be proved by diagonalistation.
>

Perhaps 42 is the answer to life the universe and everything.  I computed
that it requires 42 characters (bytes) of Chaitin's constant to encode the
first Googol digits of Post's number: Log(10)/Log(2) * 100 / 8 =
41.524101125

That's less space than this sentence requires. ;-)




>
>
>
>
>
>>
>> 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
>>
>
> From the abstract: "We also prove two negative results: a) there exists a
> universal machine whose universality cannot be proved in PA"
>
> This is surprising to me.  I thought it was generally easy to prove
> something is Turing universal, simply by programming it to match some other
> universal machine.  I will have to read it to see how.
>
>
> Even if this method works for some big, but finite sample of numbers, that
> would not be equivalent to proving that the machine does its work.
>
> By Rice theorem, we have something more general. The set of number x such
> that phi_x computes the factorial function (say) is not computable. We
> cannot test if a program compute factorial or not. You can guess that such
> a program would solve all halting problems. Imagine the program search for
> a proof in ZF of the Riemann hypothesis, and if you find it output the
> usual factorial (n). If you decide algorithmically if that code computes
> the factorial function, you would be able to solve mechanically if Riemann
> hypothesis is true.
> But you can also prove Rice theorem directly, using the second recursion
> theorem. If you can decide if a program compute some given function, you
> could use them to build a recursive permutation without fixed point, which
> cannot exist by the recursion theorem.
>
> Most attributes of programs are non computable.
>
>
>
>
>
>>
>> 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 

Re: Are proofs equivalent to dovetailing computations?

[Bruno Marchal]

> On 24 Aug 2019, at 00:23, Jason Resch  wrote:
> 
> 
> 
> On Sat, Aug 17, 2019 at 5:17 AM Bruno Marchal  > wrote:
> 
>> On 16 Aug 2019, at 19:06, Jason Resch > > wrote:
>> 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”.
> 
> 
> If Chatin's number is a maximally compressed Post's number, what makes one 
> creative and the other simple, or one a representation of dovetailing and the 
> other not?  Both require infinite computing resources dovetailing on all 
> computations in order to generate them (don't they?).  I think I am missing 
> something here.

Chaitin’s number is the result of the computation, which consists in 
compressing the Post’s number, and making it totally unreadable. The result of 
a computation is not equivalent with the computation leading to that result. 
(That’s why the Adam machine which compute a very long time to get the answer 
42 is funny :). It can be shown that such computations exist. Some predicate 
can be arbitrarily hard, despite they will answer 0, or 1. That can be proved 
by diagonalistation.




>  
> 
> 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 
> 
> From the abstract: "We also prove two negative results: a) there exists a 
> universal machine whose universality cannot be proved in PA"
> 
> This is surprising to me.  I thought it was generally easy to prove something 
> is Turing universal, simply by programming it to match some other universal 
> machine.  I will have to read it to see how.

Even if this method works for some big, but finite sample of numbers, that 
would not be equivalent to proving that the machine does its work.

By Rice theorem, we have something more general. The set of number x such that 
phi_x computes the factorial function (say) is not computable. We cannot test 
if a program compute factorial or not. You can guess that such a program would 
solve all halting problems. Imagine the program search for a proof in ZF of the 
Riemann hypothesis, and if you find it output the usual factorial (n). If you 
decide algorithmically if that code computes the factorial function, you would 
be able to solve mechanically if Riemann hypothesis is true.
But you can also prove Rice theorem directly, using the second recursion 
theorem. If you can decide if a program compute some given function, you could 
use them to build a recursive permutation without fixed point, which cannot 
exist by the recursion theorem.

Most attributes of programs are non computable.



>  
> 
> 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.
> 
> I view Chatin's number as Post's number compressed so greatly you 

Re: Are proofs equivalent to dovetailing computations?

[Jason Resch]

On Sat, Aug 17, 2019 at 5:17 AM Bruno Marchal  wrote:

>
> On 16 Aug 2019, at 19:06, Jason Resch  wrote:
>
> 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”.
>


If Chatin's number is a maximally compressed Post's number, what makes one
creative and the other simple, or one a representation of dovetailing and
the other not?  Both require infinite computing resources dovetailing on
all computations in order to generate them (don't they?).  I think I am
missing something here.


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

>From the abstract: "We also prove two negative results: a) there exists a
universal machine whose universality cannot be proved in PA"

This is surprising to me.  I thought it was generally easy to prove
something is Turing universal, simply by programming it to match some other
universal machine.  I will have to read it to see how.


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

I view Chatin's number as Post's number compressed so greatly you need to
run a Busy_beaver(N) number of steps to decompress N bits.  Is this
accurate?


>
> 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).
>
>
Could you clarify the meaning of the thermodynamics of computationalist
physical reality?  Is it equating physical randomness with the limit of the
infinite complexity of the dovetailing computations?

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

Re: Are proofs equivalent to dovetailing computations?

[Bruno Marchal]

> On 19 Aug 2019, at 03:25, Russell Standish  wrote:
> 
> On Sat, Aug 17, 2019 at 12:17:38PM +0200, Bruno Marchal wrote:
>> 
>> 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.
> 
> That is incorrect. Lookup tables _are_ computations, and the algorithms
> go by the name "memoisation", and are a form of optimisation where
> space and time are traded.

Only for finite functions. An infinite look-up table is not an algorithm or 
machine. Programs, machines, algorithm are required to be finitely given. 

If we allow infinite look-up table, all functions from N to N becomes 
computable.

Bruno




> 
> 
> -- 
> 
> 
> Dr Russell StandishPhone 0425 253119 (mobile)
> Principal, High Performance Coders
> Visiting Senior Research Fellowhpco...@hpcoders.com.au
> Economics, Kingston University http://www.hpcoders.com.au
> 
> 
> -- 
> 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/20190819012547.GD20075%40zen.

-- 
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/4BB8E12C-6198-4EF6-8683-5131ABF34F22%40ulb.ac.be.

Re: Are proofs equivalent to dovetailing computations?

[Russell Standish]

On Sat, Aug 17, 2019 at 12:17:38PM +0200, Bruno Marchal wrote:
> 
> 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.

That is incorrect. Lookup tables _are_ computations, and the algorithms
go by the name "memoisation", and are a form of optimisation where
space and time are traded.


-- 


Dr Russell StandishPhone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellowhpco...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au


-- 
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/20190819012547.GD20075%40zen.

Re: Are proofs equivalent to dovetailing computations?

[Bruno Marchal]

> On 16 Aug 2019, at 19:06, Jason Resch  wrote:
> 
> 
> 
> On Wed, Aug 14, 2019 at 5:02 AM Bruno Marchal  > wrote:
> 
>> On 12 Aug 2019, at 23:36, Jason Resch > > 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 

Re: Are proofs equivalent to dovetailing computations?

[Philip Thrift]

Chaitin numbers of course can also be extended to the computational 
hierarchy (oracles, Turing jump iterations of the halting problem):

Super-Ω

https://en.wikipedia.org/wiki/Chaitin%27s_constant#Super_Omega
https://royalsocietypublishing.org/doi/pdf/10.1098/rsta.2011.0319

@philipthrift

On Friday, August 16, 2019 at 6:31:31 PM UTC-5, Russell Standish wrote:
>
> On Fri, Aug 16, 2019 at 12:06:32PM -0500, Jason Resch wrote: 
> > 
> > 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)? 
> > 
>
> Related to this, on page 218 of Li and Vitanyi's "Introduction to 
> Kolmogorov Complexity and it Applications", right under corollary 3.6.2 is 
> the statement: 
>
> "Moreover, for all axiomatic mathematical theories that can be 
> extressed compactly enough to be conceivably interesting to human 
> beings, say in fewer than 10,000 bits, [the first 10,000 bits of the 
> Chatin probability Ω] can be used to decide for every statement in the 
> theory whether it is the true, false or independent. ... Thus Ω is 
> truly the number of Wisdom, and 'can be known of, but not known, 
> through human reason' [C.H Bennett and M. Gardner, Sci 
> Am. 241:11(1979),20-34]". 
>
> Cheers 
> -- 
>
>  
>
> Dr Russell StandishPhone 0425 253119 (mobile) 
> Principal, High Performance Coders 
> Visiting Senior Research Fellowhpc...@hpcoders.com.au 
>  
> Economics, Kingston University http://www.hpcoders.com.au 
>  
>
>

-- 
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/743f85fb-6da9-4cda-888d-a806e987d86a%40googlegroups.com.

Re: Are proofs equivalent to dovetailing computations?

[Jason Resch]

On Fri, Aug 16, 2019 at 6:31 PM Russell Standish 
wrote:

> On Fri, Aug 16, 2019 at 12:06:32PM -0500, Jason Resch wrote:
> >
> > 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)?
> >
>
> Related to this, on page 218 of Li and Vitanyi's "Introduction to
> Kolmogorov Complexity and it Applications", right under corollary 3.6.2 is
> the statement:
>
> "Moreover, for all axiomatic mathematical theories that can be
> extressed compactly enough to be conceivably interesting to human
> beings, say in fewer than 10,000 bits, [the first 10,000 bits of the
> Chatin probability Ω] can be used to decide for every statement in the
> theory whether it is the true, false or independent. ... Thus Ω is
> truly the number of Wisdom, and 'can be known of, but not known,
> through human reason' [C.H Bennett and M. Gardner, Sci
> Am. 241:11(1979),20-34]".
>
>
What an incredible and fascinating discovery/insight.  I couldn't
understand it at first but did some searching and reading and came across a
detailed explanation.  The quote above seems to be based on an earlier work
by Charles Bennett, in "On Random and Hard-to-Describe Numbers" (
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.214.7866=rep1=pdf
).  In it I found another nice quote:

Throughout history philosophers and mystics have sought a compact key to
universal wisdom, a finite formula or text which, when known
and understood, would provide the answer to every question. The Bible, the
Koran, the mythical secret books of Hermes Trismegistus, and the medieval
Jewish Cabala have been so regarded. Sources of universal wisdom are
traditionally protected from casual use by being hard to find, hard to
understand when found, and dangerous to use, tending to answer more
and deeper questions than the user wishes to ask. Like God the esoteric
book is simple yet undescribable, omniscient, and transforms all who know
It. The use of classical texts to foretell mundane events is considered
superstitious nowadays, yet, in another sense, science is in quest of its
own Cabala, a concise set of natural laws which would explain all
phenomena. In mathematics, where no set of axioms can hope to prove all
true statements, the goal might be a concise axiomatization of all
“interesting” true statements.

Ω is in many senses a Cabalistic number. It can be known of, but not known,
through human reason. To know it in detail, one would have to accept its
uncomputable digit sequence on faith, like words of a sacred text. It
embodies an enormous amount of wisdom in a very small space, inasmuch as
its first few thousand digits, which could be written on a small piece of
paper, contain the answers to more mathematical questions than could be
written down in the entire universe, including all interesting finitely
refutable conjectures. Its wisdom is useless precisely because it is
universal: the only known way of extracting from Ω the solution to one
halting problem, say the Fermat conjecture, is by embarking on a vast
computation that would at the same time yield solutions to all other
equally simply-stated halting problems, a computation far too large to be
carried out in practice. Ironically, although Ω cannot be computed, it
might accidentally be generated by a random process, e.g. a series of coin
tosses, or an avalanche that left its digits spelled out in the pattern of
boulders on a mountainside. The initial few digits of Ω are thus probably
already recorded somewhere in the universe. Unfortunately, no mortal
discoverer of this treasure could verify its authenticity or make practical
use of it.


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

Re: Are proofs equivalent to dovetailing computations?

[Russell Standish]

On Fri, Aug 16, 2019 at 12:06:32PM -0500, Jason Resch wrote:
> 
> 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)?
> 

Related to this, on page 218 of Li and Vitanyi's "Introduction to Kolmogorov 
Complexity and it Applications", right under corollary 3.6.2 is the statement:

"Moreover, for all axiomatic mathematical theories that can be
extressed compactly enough to be conceivably interesting to human
beings, say in fewer than 10,000 bits, [the first 10,000 bits of the
Chatin probability Ω] can be used to decide for every statement in the
theory whether it is the true, false or independent. ... Thus Ω is
truly the number of Wisdom, and 'can be known of, but not known,
through human reason' [C.H Bennett and M. Gardner, Sci
Am. 241:11(1979),20-34]".

Cheers
-- 


Dr Russell StandishPhone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellowhpco...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au


-- 
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/20190816233116.GX20075%40zen.

Re: Are proofs equivalent to dovetailing computations?

[Jason Resch]

On Wed, Aug 14, 2019 at 5:02 AM Bruno Marchal  wrote:

>
> On 12 Aug 2019, at 23:36, Jason Resch  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 

Re: Are proofs equivalent to dovetailing computations?

[Bruno Marchal]

> On 12 Aug 2019, at 23:36, Jason Resch  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 
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”.


> 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 

Re: Are proofs equivalent to dovetailing computations?

[Russell Standish]

On Tue, Aug 13, 2019 at 02:41:09AM -0700, Philip Thrift wrote:
> 
> If only there were a dovetailer to multiplex all one's duties. :)

They made a movie about that, starring Tom Hanks IIRC. Can't tremeber
the title, though...


-- 


Dr Russell StandishPhone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellowhpco...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au


-- 
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/20190814021139.GM20075%40zen.

Re: Are proofs equivalent to dovetailing computations?

[Philip Thrift]

If only there were a dovetailer to multiplex all one's duties. :)

@philipthrift

On Tuesday, August 13, 2019 at 4:08:28 AM UTC-5, Bruno Marchal wrote:
>
> Jason,
>
> Interesting and important questions. Unfortunately today I have family 
> duties … ,
>  I will answer in the evening or tomorrow. (Same for possible other posts),
>
> Best,
>
> Bruno
>
>
>
> On 12 Aug 2019, at 23:36, Jason Resch > 
> 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.
>
> So is it right to say that the proof of the result of some computable 
> function is different from the computable function itself?  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?
>
> I am just trying to develop a more clear picture in my mind of the 
> relation between arithmetic, proofs, computational traces, and mind states.
>
> 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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/1aa494e2-174f-4f99-bd13-926c7d341f88%40googlegroups.com.

Re: Are proofs equivalent to dovetailing computations?

[Bruno Marchal]

Jason,

Interesting and important questions. Unfortunately today I have family duties … 
,
 I will answer in the evening or tomorrow. (Same for possible other posts),

Best,

Bruno



> On 12 Aug 2019, at 23:36, Jason Resch  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.
> 
> So is it right to say that the proof of the result of some computable 
> function is different from the computable function itself?  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?
> 
> I am just trying to develop a more clear picture in my mind of the relation 
> between arithmetic, proofs, computational traces, and mind states.
> 
> 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 
> .
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/CA%2BBCJUizGA5wN9KOLynozbovu0KpJjgf%3DA6jf24fMXdcr1fVTg%40mail.gmail.com
>  
> .

-- 
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/378149E3-D089-434A-BC61-17D5B9711F18%40ulb.ac.be.

Re: Are proofs equivalent to dovetailing computations?

[Jason Resch]

On Mon, Aug 12, 2019 at 4:36 PM Jason Resch  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.
>
> So is it right to say that the proof of the result of some computable
> function is different from the computable function itself?  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?
>
> I am just trying to develop a more clear picture in my mind of the
> relation between arithmetic, proofs, computational traces, and mind states.
>
> Jason
>

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?

Can we infer anything about the existence of all computations from the
mathematical existence of the complete Mandelbrot set alone?

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