On 28 Jan 2015, at 08:21, 'Chris de Morsella' via Everything List wrote:
From: [email protected] [mailto:[email protected]
] On Behalf Of John Clark
Sent: Monday, January 26, 2015 2:23 PM
To: [email protected]
Subject: Re: Why is there something rather than nothing? From
quantum theory to dialectics?
On Sun, Jan 25, 2015 'Chris de Morsella' via Everything List <[email protected]
> wrote:
> I agree it is devilishly hard to produce a truly random stream
and a lot of brain power has gone into trying to do so, because of
the strategic importance of doing so.
>>It's not merely hard it can't be done, you will never be able to
produce true randomness in a computer with just software, you'll
need to add a hardware gadget for that.
Yes, granted but the best pseudo random algorithms can produce
pretty good facsimiles that would be very hard to differentiate from
a true random stream.
> Ten divided by three results in a non-computable number
Ten divided by three is a computable number, Turing meant something
else by a non-computable number. There are algorithms that will
allow you to compute a decimal that is arbitrarily close to 10/3 or
the square root of 2 or PI or e, or any other real number that has a
name; tell me how close you want to get (provided the distance isn't
zero) and I'll give you a finite decimal for it. But Turing proved
that most numbers on the Real number line, nearly all in fact, are
not like that at all; there are no algorithms that can even give
approximations for them.
I realize now, I should have used the term irrational number.
It's sort of ironic that although these non-computable numbers are
vastly, in fact infinitely, more common than the computable numbers
that everybody is familiar with nobody can point to and name a
single one of them... well Chaitin managed to name one and called it
Omega, but he couldn't point to it.
Well, there are many others, more simple than omega. Take any
programming language, generate all the programs, on all finite imputs
by lexicographical order (= by length, and by alphabetical order for
those having the same length). This gives P_0, P_1, P_2, ... Then the
sequence of b-inary digit defined by saying that the nth digit is 0 if
P_n stops, and 1 if it does not stop gives an example of non
computable sequence. Or list the sequence which says if P_i is the
program computing a total (everywhere defined on N) function (I assume
the programs without the inputs here): this leads to a different non
computable sequence.
Note that with the first sequence as Oracle, you can still not compute
the second (but with the second, you can compute the first). Both are
non-computable sequence, but the second one is more "non-computable"
than the first.
The non-computable is thus organized on a ladder of degrees of non-
computability. This was studied by turing, notably, and there is en
entire field consecrated to the study of degree of unsolvability/non-
computability.
The computable is a very small portion of the truth, and universal
machines are confronted to it, and they live on the border of the
computable and the non-computable.
It makes perfect sense for non-computable (I refreshed myself on
this) numbers to be vastly more numerous than computable numbers
(including irrational ones); when you begin to think of the kinds of
algorithms and program complexity to generate some randomly chosen
very large number – say a billion digit number -- without special
inside knowledge (e.g. no X - “the non-computable number”- is equal
to the number one less than X plus one… or anything of that nature)
A computable but irrational number is an algorithmic bull’s eye
really, the relatively rare case of a relatively simple recipe
cooking up this endless numeric soup.
The fact that nature exhibits only computable numbers, like pi, e,
gamma, etc. is rather strange, even with computationalism. Apparently,
our existence does not rely on oracle, others than the stopping
oracle, well emulated by ... time. (Thanks to that oracle, we know
that the program "earthly-dinosaurs" stopped!
IF QM is correct, then we can build a circuit generating "real
randomness", but it is not different from the first person
indeterminacy, like with an iterated self-duplication, which
illustrate without the quantum, that we can generate non computable
numbers in a way verifiable (in some sense) by collection of people,
like with quantum + Everett, but without assuming the quantum.
> take any local section of the stream – of square root of two is
instead very difficult to compress
That's true, the entire square root of 2 decimal expansion would be
easy to compress, but a local section of it, say just the digits
from digit 1000 to digit 2000, would be far more difficult to
compress.
Precisely, and another way of making the point I was trying to make
that point of view is often the critical driver of a contextual
complexity; e.g. the complexity of square root of 2 is low from the
bird’s eye point of view of the entire (infinite) output, but
becomes high for points of view constrained to local zones somewhere
along the infinite output stream.
This is not obvious. We may find an algorithm computing quickly
decimals at anyy place of a computable numbers. That has been proven
for the (transcendent) number PI, and it would be astonishing it could
not been proven for sqrt(2), but I have not heard if that has been
proved.
Bruno
Is there a algorithm that will produce just those digits that is
shorter than a list of those 1000 digits? Maybe there is, or maybe
not, Turing also proved that in general there is no way to know if
there is a algorithm that will produce a sequence of numbers that is
shorter than the sequence itself; and even if there is and you
happened to find a algorithm that worked Turing also proved that in
general there is no way to know if it is the shortest algorithm. .
Different chunks of the output stream may be compressible to varying
degrees (even if perhaps minutely varying degrees), but based on the
highly chaotic nature of this particular stream – to as far out as
it has been calculated by us – my guess is that there could be no
significant compression.
Turing was a math genius; information science owes him a great deal.
>> By "seemingly random" I assume you mean it came from a algorithm.
> Yes, it is not truly random, but the chunks have been randomly
scrambled in the transmission
OK.
>> How is the data stream scrambled, by another algorithm or a
physical random process such as radioactivity decay?
> Assume by some physical random process – assume for the sake of
discussion that the ordering of the packets has been truly scrambled.
OK
> Also need to assume that the key first packet containing the
portion of the number to the left of the ‘dot’ is explicitly
excluded from the transmission. Only packets of numbers are
transmitted; no other symbols.
OK
> now I am not sure, perhaps square root of two will leave subtle
patterns in the apparently random series that a clever algorithm
could pull out. This possibility increases as the chunk size
increases,
The square root of 2 has been calculated to, I don't know probably
about a trillion digits, but regardless of the chunk size if the
chunks were picked at random from the entire infinite sequence of
digits then the probability that any chunk you received came from
those first trillion digits that you would recognize would be zero.
And even supposing one of the chunks you got did contained a
sequence of 1000 digits that were identical to the first 1000 digits
of the square root of 2 that doesn't prove it came from a algorithm
that produces the square root of 2. It has been proven that any
finite sequence of digits you can name exists somewhere in the
decimal expansion of PI or e, your social security number will be
out there a finite distance into the expansion and so will the first
1000 digits of the square root of 2. So maybe the number they're
sending you didn't come from a algorithm for the square root of 2 at
all, maybe it came from a PI algorithm, or a e algorithm.
Exactly – you never know what algorithm, or even some other stretch
of the infinite output stream resulting from the infinite evaluation
of 2^(1/2). Any such coincidental knowledge could not lead back to
a proof, because it could be produced by an infinite number of
algorithms. The most that could be said is that the square root of 2
generates this given ordered set of digits at some given range of
its output. But correlation does not by itself prove causation.
Now supposing these unfortunate researchers began trying to build a
map of these data chunks mapping correlating regions of the vast
array of all of their known physical constants and math algorithms
trying to see by brute force correlation if a winner would emerge. I
feel that instead no winner would emerge. Many candidates would be
eliminated, if their output was predictable and any one of the
growing collection of perceived packets could be proved to be an
impossible series of values for that candidate; however the ones
that would be left would be very large (theoretically potentially
infinite).
No matter how many regions of correlation were found nothing more
could be said than that.
>> In other words will the recipient ever be able to predict what
the next digit will be?
> I was thinking more of the strong challenge of reassembling the
packets into their correct order; by working back to a proof of the
function that generated the output stream,
That would be pretty much the same thing, if you can reliably
predict the next digit you must have figured out what the algorithm
was that produced the digits..
Yes, I can see that.
-Chris
John k Clark
--
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 post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
--
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 post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
http://iridia.ulb.ac.be/~marchal/
--
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 post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
