Re: Computing Randomness

From: Hal Ruhl <hjr.domain.name.hidden>
Date: Wed, 11 Apr 2001 08:32:51 -0700

Sorry I think an unedited version of this may have got out by mistake. I
have not seen it get posted so perhaps it did not. Again if it did I am sorry.

Dear Juergen:

At 4/10/01, you wrote:
>Hal, you wrote:
>
> > I believe that attempting an extensive detailed formal description of
> > the Everything is the wrong approach. IMO - at least in this case - the
> > more information used to describe, the smaller the thing described.
>
>I was not able to follow this, but informal and vague descriptions of
>everything have been around for millennia. Now it is time to go beyond
>this. One cannot scientifically discuss nonformal statements or theories.

I did not say I had no formal description. I have a small one which I have
attached.

>You did refer to formal describability when you repeatedly wrote that
>if a universe is a theorem cascade in an N-bit formal axiomatic system
>"then Chaitin's incompleteness dictates that the cascade must stop,"
>and there are no more than 2^[N + c] theorems. For some reason this
>statement even made it into your "FAQ" list.
>
>Counter example: number theory is describable by finitely many bits of
>axioms yielding an infinite cascade of provable theorems.

"FAQ" is a poor name for what we can do on this list at this time. The
"FAQ" I am attempting is - as stated several times - a comparison of
various approaches. The above is one of mine.

That being said, how are you treating numbers? The finiteness of a FAS is
not just a description of its axioms but of all its components that
contribute to the complexity of the program describing its theorems which -
as I understand it - is the complexity of which Chaitin speaks. [I will
look for the reference in his books and post it.]

If numbers are just various strings of two binary bits giving a small
alphabet then I suspect Chaitin's work applies.

Hal

------------------------------------------------------------

The rest of this is at: http://www.connix.com/~hjr/style2.html

Parts of:
PATTERN BASED MODEL OF THE EVERYTHING
VERSION J
DRAFT OF 4/08/01
BY HAL RUHL
FILE FAQstyle2j.html

                                          SECTION I
                                        DEFINITIONS #1

1) Pattern: A pattern is a geometric structure that could vary in at least
one characteristic from location to location within
the pattern. Patterns must be at least a set of more than two zero
dimensional isolated discrete points.

2) Information: There are two types Relative and Absolute:

Relative information is the structure of a given pattern, bit string or
other such structure both within the structure itself which
would be just the relative position and style of its elements, and between
structures in a larger whole which would be the
relative styles, quantities, and positions of elements/patterns.

Absolute information is based on mathematical structure and selection. An
example of mathematical structure absolute
information would be the resolution of : The Everything is stable; true or
false. An example of absolute information
based on selection would be the selection of a single pattern, bit string
or other such structure out of a collection of such
structures.

As an example of total information the selection of a particular bit string
consisting of some count of all zero's would be a
maximum of selection based absolute information while the string selected
contains no internal relative information.

                                          SECTION II
                                      THE LOWEST LEVEL

In this model the lower level of existence contains an expression of no
information. Rather like 345/345 is an expression
of an identity element. There are two polar extremes at this lower level:
the Everything and the Nothing. The Everything
expresses pan-isomorphism, the Nothing expresses anisomorphism, hence
neither is fully describable. However,
selected pieces can be described.

The Nothing, since it contains no information, can not resolve the question
of its own stability which it must address. The
only option is to test the issue with the only perturbation available - it
becomes the Everything.

The interesting thing is that the Everything being a perturbation from the
Nothing does not contain the Nothing. Subtracting
the Nothing from "all information" to produce the Everything is the
smallest selection [perturbation] I can think of. The
idea being that no information and all information are identical but the
Everything is not quite all information. For this
reason I prefer the name Superverse.

The Everything also having almost no information similarly can not resolve
the question of its own stability and must also
test the issue by becoming the Nothing. Both poles - being mutually
exclusive - destroy history whenever manifest, thus
a random Everything/Nothing [E/N] alternation is established. Existence at
this level is sustained but has bipolar
expression.

                                         SECTION III
                                       THE UPPER LEVEL

Pan-isomorphism is the upper level of existence. It is manifest only when
the Everything is manifest so it is not
continuous.

A portion of the pan-isomorphism expressing Everything is describable as a
seething foamy fractal pattern of infinite
repeats of all patterns. Part of the seething is due to the differences
between successive Everything manifestations.
Since the E/N alternation destroys history, each Everything manifest has a
randomly selected pattern of patterns. Any
further seething that may be present during an Everything manifestation may
be thought of as generating historic
information, but it is relative information and not absolute
information. It is not germane to the question of the Everything's
stability. Thus it does not preclude the E/N alternation and is destroyed
by the alternation.

Individual patterns in this portion of the everything have multiple
interpretations. Each such interpretation produces a pair:
[pattern;interpretation]. These pairs are linked to isomorphisms which can
be states of universes. These isomorphic
links can be self sequenced by rules internal to the individual
isomorphism. The links of a sequence are either past,
active, or possible. Looking just at the present and successor links we
shorten this to active and possible. Speculation
as to past links may or may not be incorporated into the rules of a given
isomorphism. Thus we write these isomorphic
links as {[pattern;interpretation];[possible/actual isomorphism]}. The
sequencing is a migration of active isomorphic link
from one [pattern;interpretation] pair to another.

The rules can have a non deterministic content. Such rules define the
family of viable link successors with a procedure
that can be partially "do not care". Since the Everything is in effect a
seething pattern of patterns the first acceptable
"possible" link encountered by any search scheme is random for rules with a
non deterministic content. This link
becomes the next active one.

                                         SECTION IV
                               MATHEMATICAL DESCRIPTION PART 1

In order to focus on a particular class of these link shift rules which may
contain our universe the model makes the
following associations:

Some of these isomorphic links can be represented by strings Uj()
consisting of at most a countable infinity of binary
bits.

Every evolving universe Uj is isomorphic to a self sorting sequence Uj(i)
of these links that, upon an encounter between
an active link and an acceptable "possible" link in the fractal, they
switch states thus they self sequence according to
[written post shift]:

      (1) Pj(i) = {Rj(U'j(i - 1)) + PLj(i)} is the shortest program that
computes Uj(i).

Where:

Rj is the current rule set of Uj and Rj(U'j(i - 1)) is Rj acting as a
comparison filter based on U'j(i - 1).

U'j(i - 1) is the previous link's representing string if Rj was fully
deterministic. [See below]

PLj(i) is the program length self delimiter.

Uj(i) is the current link's representing string.

The structure of U'j(i - 1) depends on the nature of Rj. If Rj is fully
deterministic then U'j(i - 1) is the same as Uj(i - 1). This
causes the Algorithmic Information Theory [AIT] complexity [Note #1] of
Uj(i) to increase as i counts up. This can be
more clearly seen by rewriting (1) as:

      (2) Pj(i) = {Rj(Pj(i - 1)) + PLj(i)} is the shortest program that
computes Uj(i).

since Pj(i - 1) is the most compressed form of Uj(i - 1). Pj(i) has more
bits than Pj(i - 1) since it contains Pj(i - 1) as data.
If Rj is partly non deterministic but still needs all of Uj(i - 1) as data
then U'j(i - 1) is more complex than Uj(i -1) and the AIT
complexity of Uj(i) increases even faster. If Rj becomes even more random
then not much can be said of the relation
between U'j(i - 1) and Uj(i - 1)

The first link encountered while the fractal is seething that passes the Rj
mediated compare becomes the successor to
Uj(i - 1) i.e. Uj(i).

Each Uj(i) is a stand alone isomorphism that contains a finite
semi-consistent Formal Axiomatic System [fsc-FAS] that
defines Uj. The structure of the fsc-FAS is:

a) It initially has a single axiom Aj unique to a particular family of
universes which is in Pj(1) as the initial data provided to
Rj i.e. as Rj(Aj). It is Uj(0) and initiates the recursion.

b) It has a set of rules = Rj which form the comparison filter. Rj is a
particular evolving universe's laws of physics. The
rules as stated need not be fully deterministic. This is the source of the
"semi" modifer to "consistent". While Uj(i) is a
theorem of the FAS in the standard sense, when the rules Rj act on Uj(i)
to compute Uj(i + 1), Uj(i) may activate a "do not
care" operator in Rj.

c) It has an alphabet = differently sequenced strings of bits in Uj that I
call types of "regions". The axiom Aj contains the
entire initial alphabet of regions.



                                          SECTION V
                                        DEFINITIONS #2

3) Granular-discrete space-time: A discrete space in this thread a
3-space in which isolated points are confined to fixed
regions [granules] that have a fixed relative location with respect to
other regions in a space grid structure. The grid
structure currently preferred in this thread is Face Centered Cubic [with
spherical surfaced regions]. Within each region
the associated point can assume a finite number of discrete
locations. Each region with a particular point location can be
thought of as isomorphic to a particular alphabet element of a FAS such as
an "a" region or a "b" region etc. A finite
string of these alphabet elements [such as abcryopaabctgjk...abcfg]
isomorphic to state of a finite physical universe.
Different such strings are then isomorphic to different states of that
physical universe. The dimensions within a region
may be continuous but a given FAS can only contain a finite number of
alphabet elements i.e. regions. A binary bit
string can be constructed which designates a region by a string of 0's with
a single 1 buried in it some where. The "a"
region might be "00000000000000001000" and the "b" region
"00000100000000000000". This would allow a finite string to
locate each of the finite number of points in such a finite
granular-discrete space-time with infinite precision without the
need to actually display the associated infinite strings. Again time is
quantified and subjective to a given universe.

                                         SECTION VI
                               MATHEMATICAL DESCRIPTION PART 2

Each "region" type is modeled as isomorphic to an interpretative structure
that has physical meaning such that the
location of a discrete isolated space point u inside a small fixed portion
of a space grid is coded by each region type.
[In our case I believe the grid to be 3D and most likely Face Centered
Cubic.] The points can not leave their own region
but can relocate within it.

The isomorphism need not give rise to an actual physical existence of a
universe within the Everything as this would be
redundant to the existence of the pattern itself. Just the applicable
interpretive isomorphism need exist as an overlay on
the pattern. A given pattern can have many such overlays depending on
which section of the pattern is considered to
be the rules of succession by the particular isomorphism.

Uj(i) contains a theorem of this f-FAS giving a specific arrangement of
"regions" - a configuration of a particular universe.
The structure of Uj(i) using English letters to represent different
"region" types would look like the following.

     (3) Uj(i) =
aaxcvsyplmnjhkkyufpoiiimjkhlyhhhhnkmlpmneidhsu...qaeeerwetgbfvvvdcsdxazjfirjnfjgkkeirejqzq


To express this idea as an expanded binary string call each of these a type
of sub string u. In this limited example there
are 26 types of sub string u. For example a = the u:
00000010000000000000000000, and b = the u:
00000000000000100000000000. The location within the string Uj(i) of a
particular u identifies the particular grid region it
codes and the location of the 1 within each u codes the location of the
discrete space point u within that region.

The result is a granular-discrete space-time. The granules are the regions
and for starters have a spherical surface. The
point within a region is discrete but may be located by continuous
dimensions. However, the finite complexity FAS can
only contain so many alphabet elements and thus the space-time is
discrete. Nevertheless the bit string scheme above
allows the FAS to locate points with infinite precision absent a need to
display the actual dimensional coordinates of any
of the discrete points. Time in any given universe is also discrete and
runs at some ratio of the Nothing-Everything
oscillation rate. This ratio need not be constant, the Nothing-Everything
oscillation rate itself can not be constant or it
represents absolute information, and time is subjective to a particular
universe.

                                         SECTION VII
                                         TRUE NOISE

If there were no "true noise" in the system due to the nature of Rj [a
fully deterministic Rj] then (1) would be a recursive
enumeration or theorem cascade in an N-bit, fc-FAS. Chaitin's
incompleteness [The maximum AIT complexity of a
theorem of an N-bit, fc-FAS is (N + 1).] dictates that the cascade must
stop since there are no more than 2^[N + c]
theorems in the FAS. But as was shown above such cascades produce
monotonically more AIT complex theorems.
For the cascade to stop it must end on a theorem that has no consequent
under the rules of the cascade. If region n is
the neutral region then all regions of the granular-discrete space-time
would be the neutral one. If this is region "n" in (3)
then Uj(i) becomes:

     (4) Uj(i) =
nnnnnnnnnnnnnnnnnnnnnnnnnn...nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
                = m repeats of n

This is a very low AIT complexity theorem. Thus we have a
contradiction. Call this the "Halting Contradiction". A random
oracle can provide new information to the FAS [say new alphabet elements -
new types of regions] as necessary and
thus repeatedly increase N eliminating the contradiction. This is also
equivalent to "true noise" as well as to starting the
sequence over with a new axiom which is now just Uj(i).

The sequence may stop when N becomes countably infinite if this destroys
the consistency of the FAS.

Consequently Uj(i) must also grow in length as i counts up since there are
only 2^N - N-bit strings. Since Rj is a source
of "true noise" if not fully deterministic then this accumulation of
information just accelerates as the sequence progresses
since Rj is applied to ever longer Uj(i). This constitutes further use of
the random oracle at theorem complexities below
that which triggers the "Halting Contradiction".

Further one must consider that those Rj [FAS] that form Godelian incomplete
systems will be prone to the need to
resolve that type of undecidable which are seen as additional inputs from a
random oracle.

Thus there are so far three potential sources of "true noise" in the model.

I happen to believe that all SAS require some true noise influx into their
universe. I have so far argued the possible
presence of true noise from the perspective of Chaitin's and Godel's
incompleteness and an added just plain "do not
care" component in the rules of link succession of a particular
universe. But is such noise built into any SAS?

If we consider ourselves to be SAS do we allow that any SAS - to be a SAS -
must be able to run any possible
experiment including thought experiments we can? If we do then the idea
that we perhaps can construct an isomorphism
between the S/N alternation and the scanner/transporter/duplicator [STD]
thought experiment [see the everything list FAQ
and archive] may be another source of true noise. Considering that the
U'j(i - 1) to Uj(i) operation of the Rj is a
deterministic one [given the data on what just happened our current state
is predictable but the data may not have been
deterministicly arrived at] the S/N alternation looks like the STD
operating at the level of the Superverse itself. However,
any SAS in any particular universe can not identify its actual
operation. Thus the SAS is faced with a fundamental
undecidable.

How does the potential "true noise" impact the logic system during the
sequencing process? Relation (1) is really
saying that there is not necessarily enough data in Uj(i - 1). The
consequent then is that each new U'j(i - 1) would be a
new initiating axiom for the cascade whenever a true noise event takes place.

----------------------------------
Received on Wed Apr 11 2001 - 05:47:30 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST