Registered: Dec 2005
Posts: 5

Hi, I was wondering if anyone could point me in the right direction for the answer to a question I've had recently.

In a previous post I asked about the possibility of a CA's output being equivalent to some kind of set, or in general some other kind of mathematical structure. The reply answered the question by basically equating "sets, data, patterns", etc., with sequences--that is, arrays of binary digits.

I felt like this makes a lot of intuitive sense (take a long enough string of binary digits and you can probably provide enough information to differentiate any two different sets, patterns, etc.). But now I'm wondering to what extent it really is true that sequences can capture "all forms of mathematical structure, organization, etc.". I suppose words like objects, structures, patterns, data, etc. are "fuzzy" epistemic words without well-defined meanings, but in an informal and intuitive sense the meaning is clear.

I guess my question is really about the foundations of mathematics. Set theory seems to be the backbone of modern math, with other structures, like groups, rings, vector fields, etc. defined in terms of sets with binary operations satisfying certain properties etc. I noticed that in NKS there is large use of sequences (in the form of rows of black and white squares) in discussing the foundations of mathematics. I'm basically just trying to further understand what's going on here.

Here is an example in group theory which I hope will clarify what I'm after. Consider the group G = (G, *), with * the binary operation. Now suppose I want to represent G using a binary sequence. How would I do it?

Here's the idea I was playing with: The meat of the group seems to be contained in the definition of the binary operation. Suppose |G| = 3 and we call the elements of the group a1, a2, a3. Then suppose the binary map * is defined by the 3^2 = 9 relations:
a1 * a1 = a1
a1 * a2 = a2
a1 * a3 = a3
a2 * a1 = a2
a2 * a2 = a3
a2 * a3 = a1
a3 * a1 = a3
a3 * a2 = a1
a3 * a3 = a2

That is, a1 is the identity, and a2 is the inverse of a3. Now, to form a sequence that represents the group, I thought maybe we could let
a1 -> 00
a2 -> 01
a3 -> 10
And now, write each of the nine relations as a sequence, so that for instance, a1 * a2 = a2 becomes (a1)(a2)(a2) = 000101. Is this the correct way to represent a function using sequences? If not, what would be more correct?

Supposing the above is reasonable, then perhaps we could join these 9 sequences to form:
000000 000101 001010 010001 010110 011000 100010 100100 101001

(where the spaces mean nothing and are only for visual clarity)
Now here's the question: Is this a valid sequence representation of group? By which all I really mean is, does this "make sense"? When is such a process of continually appending sequences to make one giant sequence sensible and appropriate?

Consider B, the set of sequences that the set of all groups maps onto. Assuming that the translation is injective, we should be able to determine the original group given sequences in B, right?

That is, it seems that we should have an inverse function on the subset B of the codomain. Is this the criterion for our representation to "make sense"? If not, what is the criterion?

Also, I'm very curious to know: To get from the huge string of bits above back to the original group, our translating function has to know some things, like the fact that there are always N^2 relations for a group of order N, and that each relation has 3 components (two inputs and an output).

What's the nature of the knowledge that the translating function has to have? By which I mean, does the fact that the translating function has to do a lot of work mean that we haven't totally captured the entire structure of the group in our current sequence scheme? Is there a way to modify our scheme to capture the entire structure? What is the best way to know that one has captured the entire structure?

A similar curiosity arose from the way NKS classifies elementary CAs. Since there are exactly 255 CAs, one can distinguish them simply using the numbers 0-255. So it almost makes you want to say that the number 130 is a "complete representation" of CA rule 130. But really, this number says nothing about the structural nature of the algorithm performed by the CA, only of its place in the small set of elementary CAs. When we speak of "representation", do we always face this issue? Is representation in general always in some way dependant on the "scope" of different possibilities that we care about, or is there some more universal means of representation?

Thanks for any help and insight on this issue. Also, any suggestions on good papers/books that use binary sequences heavily in the discussion of axiomatic systems, fundamental math, the nature of representation, etc. besides NKS would be very helpful.

Best,
--Stedman

Last edited by Stedman on 01-09-2006 at 09:59 AM

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Binary can represent any single real number, when infinite length is allowed. Or one can think of binary as representing not one but all of the integers - or any other enumerable set, since enumerable means "put in correspondance with the integers". That is the more useful way to think of it.

From numbers to programs is basically the same generalization as functions in mathematics. Functions of integers, sets of integers (equivalence classes corresponding to outputs of functions), sequences of integers, all can be used as equivalent to one another. For someone with mathematical background, thinking of states as integers and programs as functions defined over integers is natural.

If you think in practical computer terms, the state of memory at any one time on the global clock is a single large number in binary (an integer or terminating decimel, which are equivalent). Transitions to another internal memory state are integer to integer transitions. So memory updates are maps from integers to integers, aka functions of integers. That's what a program is and does.

Back in the 1930s when the idea of computation was being worked out mathematically, the correspondances among the various representations were noticed. People worked on diverse approaches and then proved theorems that they reached the same space. Integer arithmetic is universal - any constructable computation can be translated into a corresponding problem in arithmetic. Functions on integers are universal - the lamba calculus was based on this idea (though it starts lower still and builds up its own representation of integers).

Universality does not apply to a simple system of naming or representation. Binary is such a system of naming or representation but it is not universal. It does not possess a specified set of transformation rules. If you add the transformation rules of arithmetic, you get a universal system - arithmetic - which would be universal in unary or base ten. (You can add lots of other systems of transformation rules instead - some are more convenient than others). There is nothing special about binary in this, it is just convenient for branching, IFs, and the like. It is the set of transformation rules which may or may not be universal, not the naming system.

Universality applied to a rule system means, any possible function in some other rule system over the integers (or any other enumerable set) can be translated into an instance in the universal system. By an instance I mean a rule and initial condition pair. By translated I mean the translated function with its eventual output retranslated, gives the same output as the original, and fails to halt if and only if the original fails to halt. We say the second emulates the first.

Since these are correspondances between (enumerable) infinite sets, though, there is plenty of wiggle room. Universal system X might require ten times as many operations or a much more complicated initial condition or both, to emulate system Y. Universal means the transformation rules can map computations "onto" or get them all, somewhere in their own (countable) infinite enumeration.

A set of transformation rules might not be universal. If it is simple enough there will be possible functions of integers it cannot emulate. For example, ordinary first order predicate logic is not universal. Every expression has a definite truth value, there are no non-terminating computations or "infinite loops". We say, first order logic "always halts" or "has no WHILE loops".

There are sequences that are not computable in the above sense, meaning no function of integers arrives at that output. This can be shown with diagonal arguments - there are as many sequences of integers as there are reals, which are not enumerable, and only as many computations as there are integers, which are. It is in general undecidedable whether any given sequence of integers is computable, or in other words is the outcome (after however long) of a deterministic computation from a single integer initial (however large).

The basic papers on all of this stuff occur in the 1930s in the work of Alan Turing (TMs and the idea of computation), Alonzo Church (lamba calculus, a function-based form of logic effectively), and Kurt Godel (universality in arithmetic). John von Neumann contributed then and later, in particular to the development of practical computers and the idea of representing program and data in the exact same way, the program simply occupying the first portion of memory. Together they founded computer science before there were electronic computers, when the term "computer" was the job description of a human being who did arithmetic with pencil and paper.

A standard modern text covering the basics - and a fair ways beyond the basics - is "Introduction to the Theory of Computation" by Michael Sipser. Here is an Amazon link -

http://www.amazon.com/gp/product/05...1171080-6531131

There is extensive material on these subjects in the NKS book, both in the universality discussion in chapter 11 and in the foundations of math sections of chapter 12. And more in the accompanying notes.

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

The other way to answer this question is to point out the connections to language and philosophy.

Even an English sentence has no meaning without context. This is the problem of semantics.

The question of whether binary sequences can describe everything implies the question of what you mean by everything.

NKS, the book, says that the natural world can be well-described by simple programs, implying that those things can be described by binary sequences, or their equivalents.

That leaves open metaphysics.

If one takes a minimalist point of view, then one could stop here.

(Feel free to correct me. Though maybe I should have posted this in the section, NKS Way of Thinking).

While it is usually a risky venture to say that one representation is more correct than another, it is possible to say which is simpler. In your example of a group, one could ask for its smallest unambiguous description. This would probably mean data and a means to decode it.

The NKS aesthetic prefers the smaller, simpler explanations, which could be thought of as its vehicle for delivering meaning.

Report this post to a moderator | IP: Logged