Infon Theory Intro

NOTE: If you aren't developing the Proteus Language it's suggested that you not read this page. This is the red pill. You do not need this information to use the Slipstream

This page contains some relevant information about why Proteus has the structure that it does. The language comes directly from the theory of infons and significant improvements to the language will require filling in gaps in the theory.

##Introduction Suppose we have some machine, device, or system and we wish to represent all of the possible ways that it can be made to evolve over time. To represent this situation, let us begin by listing two things: the different states that the system under consideration can be in, and the different actions which can be performed on the system to make it go from state to state.

Question: If states==information, is there any thing physical or not, that does not carry information?
  
Example: we can talk about the states of a bicycle -- it's wheel positions, pedal positions 
   (and how the pedal position maps to the chain position which maps to the wheel positions). But isn't 
   it a state of the universe that the matter comprising the bike is in fact a bike and not something else? 
   Didn't the state of the universe change when we mined the steel and shaped it into a bike frame? 

Question: As we break a system into two parts how do the states divide?
* A 16 state system can divide into two four state systems, not two 8 state systems.
* Adding matter adds states/information, removing it removes states. Can we say that matter != infons?
* Thus adding info adds matter while removing info removes matter: is it possible that matter/energy != information

We have several issues to resolve regarding our two lists, so let us consider, for a bit, a very simple system, a light switch. Naively we might note that a switch has two states, ON and OFF. But for a double light switch system, the ON or OFF status of one switch depends upon the state of the other one. Therefore, we could model such a switch with UP or DOWN. If we needed to, we could also model all the intermediate positions as we slide the switch from one position to the other. Furthermore, we could include in our list of states the state of the plastic covering, the conductivity of the contacts, etc. The point of this is that the states we choose to place in our list must reflect what we intend to model. This will be important soon. For now, let us settle with the list ON, OFF.

Next, let us consider what type of actions we will be performing on the system to make it change state. Just as the list of states for a light switch could be simple or complicated depending upon the needs, the list of actions that can be performed upon a given system can be simple or complicated. For a light switch we could do any number of things to it: bop it with a hammer, heat it with a torch, tap it gently, etc. However, these actions produce state changes that are not in our model of ON/OFF. For example, bopping it with a hammer may shatter it and heating it with a torch may melt it. Both of these state changes go beyond our model of ON/OFF. If we wanted to model such states we should have added them in the first step of listing states. So let us limit ourselves to only those types of action which relate to the states in our model.

Shall we represent _over determinism_ where more than one action can cause a particular state change? 
No. This “bit” is external and can be collapsed into a single action or made internal. In other words, 
the information about which of the two actions caused the particular state change is an infon - bring 
it into the system being modeled.

Shall we represent _under-determinism_ where an action causes one of two or more transitions? 
No. Measuring the information shows that we have really just hidden a state internally which should 
be removed or made explicit in the lists.

Of course, there is another thing we can do besides flipping the switch; we can leave it alone – do nothing. If we do not count “doing nothing” as a valid action than really we are saying that we MUST flip the switch, in which case there is really only one state: constantly flipping. If we are to have a choice about the state changes then we must have a “do nothing” action.

Now suppose we have a system with 5 (or n) states. How many actions can there be? Suppose, for example, that our five states are numbered 1 through 5. And suppose that currently the system is in state 1. One action is the “do nothing” action that leaves it in state 1. There can also be actions that change it to either state 2, 3, 4 or 5. We have already ruled out the possibility of having two or more actions represent the same state change. For example, we have ruled out the idea that two different actions can move the system from state 1 to state 2. Instead, if the difference between the two actions represents an state external to our list we merely refer to them both as being the same kind of action. And if the difference between the two actions represents a state of a part of the system we are modeling (i.e., a state that is in our list), then can can’t say that both actions refer to state 1. In the same way, we cannot have an action that changes the system to more than one state. For example, flipping a switch cannot change the switch to both on and off; otherwise we should not have listed these as different states.

Since, at any given time the system is in one state, and from that state it must either stay the same or change to one of the other states, and since each of these requires a different action, we must therefore have 5 (or n) actions. Of course one of these 5 actions must be the “do nothing” action and the others change it to the other four states. Can we leave out a state? In other words, can we say that there is no action that moves the system from state 1 to state 3, for example? No, because we could either get to that state through a combination of actions (in which case just put it in), or we can never get to it (in which case why list it in the first place?)

In other words, the number of actions on each state is the same as the number of states.

##How similar are infons and Mathematical Groups? In math, a "group" is "a set together with a binary associative (a(bc)=(ab)c) operation such that there is an identity, every element has an inverse and any pair of elements can be combined without leaving the set (closure)."

What we have just discovered about infons is pretty close to groups: We have a set of states/actions, there is an identity element (the 'do-nothing' action), every action has an inverse action and the system is closed over these actions.

There are some subtle differences.

Work in progress: more of the details go where this messages is.

Please update this either by adding content here or editing the above text to make it easier to understand. The notes below are intended to help filling in details. Math folks, please correct any errors.

---

###Notes:

• A commutative (ab=ba) group is called Abelian.
• The identity (e) element is unique.
• AB=AC implies that B=C. (Cancellation)
• Every element f in the group has a unique inverse g such that fg=gf=e.
• The number of elements in a group G is called its order. It is notated |G|. Infinite groups have order 0.
• A subset S of a group G is a sub group iff one of:
• S is closed under the group operation (for finite sets)
• For every a and b in S, AB-1 is in S

####Some Common Groups:

• Zn The group {0, 1, 2, … n-1) under addition modulo n.
• U(n) Unitary Group: the group of integers less than n and relatively prime to n.
• Sn The Symmetric group of degree n. The group of all permutations of a set of n elements.
• An The Alternating Group of degree n: The even members of a symmetric group Sn
• Dn The Dihedral Groups of order 2n
• GL(n, F) The General Linear Group. All N by N matrices with nonzero determinant with coefficients from the field F.
• SL(n, F)The Special Linear Group. All N by N matrices with determinant of 1 with coefficients from the field F

####Cyclic Groups

• A Cyclic group has only one cycle.
• There is at least one generator that generates the whole group.
• Cyclic groups are Abelian.
• All of their subgroups are cyclic.
• Every infinite cyclic group is isomorphic to Z+. Every finite cyclic group of order n is isomorphic to Zn+.
• To find all the generators of a cyclic group: an integer k in Zn generates Zn if gcd(n, k)=1.
• The order of any subgroup of a cyclic group is a divisor of ||.
• For each positive divisor k of ||, the cyclic group has exactly one subgroup of order k, namely, <a||/k>.

####Subgroups

• For every member g of a group there is a subgroup notated which is {gn | n  Z}. A subgroup notated by <a, b, c…> contains all of the groups generated by a, b, c, etc..
• The intersection of two subgroups is itself a subgroup.
• The order of an element g in a group G (notated |g|) is ||, i.e., the order of the cyclic group it generates. * This can be calculated as the smallest integer n such that gn=1. If no such n exists, g has infinite order.
• The subgroups of Zn: For each positive divisor k of n, <n/k> is the unique subgroup of Zn of order k. These are the only subgroups.
• To find the number of elements of each order in a cyclic or non-cyclic finite group, see Gallian p.80.

####Cosets, Group Products, Factor Groups ####Finitely Generated Abelian Groups

####Conjugation

####Homeomorphisms

####Automorphisms, Orbits, Centers, Stabilizers, inner morphisms

####Lagrange’s Theorem

####The Class Equation

####Converses of Lagrange’s Theorem: Sylow, Hall