Research Session Log

It seems that when an AI could build a full AGI then it could also kill us if unaligned. We need to get useful cognition out before that. World Substates VS Transition structure In Conway's Game of Life, Gliders are important. In Minecraft, wood is important.

Glider instances and wood instances are substates of the world state.

This is related to the difference between a static instance of a datastructure which just contains some data and the algorithm that operates on instances of this datastructure.

E.g. if the world is a bitstring B, then a substring of B is a substate of the world state.

In Conway's Game of Life, Gliders are important. In Minecraft, wood is important. Hypothesis: We as humans have a specific cognitive architecture that allows us to represent concepts specifically a glider would be saved as a specific kind of set of substates all the states that the glider can be in.

We as humans have a cognitive architecture where we can refer to the general idea of a glider somehow; an algorithm should be able to do the same thing.

We know that they are. Therefore we know that in a cognitive system that models the game of life or minecraft, it

The cognitive system has a list of concepts; one of them should be glider/wood.

We could do the same for the transition structure.

WorldState ; A state of the world
Substate ; Substate of the world

structure Concept where
  substates : Set Substate
  

tree := Concept { substates := ALL_TREE_BLOCK_CONFIGURATIONS }

Object-based World Program Instead of using the world state graph, we can have the world model consist of a collection of objects. Each object is a collection of sub-states together with a map describing the transition rules between the substates, together with some instance properties.

E.g. here would be the Minecraft tree instance:

Concept { 
  substates := ALL_TREE_BLOCK_CONFIGURATIONS,
  infraTransitionRules := []
  instanceProperties := { position := SOME_VEC3 }
}

Example

A world state is a collection of objects.

WorldState ; A state of the world
Substate ; Substate of the world

structure Concept where
  substates : Set Substate
  


tree := Concept { substates := ALL_TREE_BLOCK_CONFIGURATIONS }

GliderPhase = enum("GliderPhase", "ONE TWO THREE FOUR")
Direction = enum("Direction", "BOTRI TOPRI BOTLE TOPLE")

class Glider:
    pos: (int, int)
    phase: GliderPhase
    dir: Direction

    def evolve(self):
        if self.dir is Direction BOTRI:
            self.pos[0] += 1
           self.pos[1] += 1
        self.phase.next()

structure Glider where
  substates
  pos
  updateMap : Glider -> Glider

def Glider.update (g : Glider) : Glider :=
  g.updateMap g

In minecraft TNT destroys blocks around it when it blows up. Fire ignites wood blocks that are close by. In both cases the exact effect depends on the surrounding blocks. Dirt has lower TNT resistance than stone, and only burnable blocks will be ignited.

Often interactions are localized like the above two examples.

The rules of the world are encoded in the objects, which intuitively is “smaller” than describing the interactions with a world state graph.

The world state graph seems to be isomorphic to a lookup table. (where the key is the tuple (world state, action))

How do substates relate to

• Distill the core insights into typst
• Completely formalize objects in the 1D Bit Automata.
  • Understand at all how different objects would interact with each other.
    • One part of this is probably collision detection
  • Formalize how objects can be combined
    • algebra of objects. E.g. type theory has an algebra on types. Product type is an operation that takes in two types and returns a new type.
    • Generally what I mean with algebra is that I have a set O (the objects) and a set of functions Oⁿ -> O where n can be anything and is not fixed, that can be applied to the objects that are closed over O. And usually it's implied that we can discover rules that hold
    • We want to be able to combine different objects, automatically, such that all attributes of the original object get combined in a meaningful way.
      • E.g. if I know what it means for a glider to collide with something I want to be able to create a glider formation object of multiple gliders that has automatically defined the “is colliding” functionality.
• How does this relate to algebraic structures
• How does this relate to the algebra over programs (FP, John Bacus lecture, etc.)
  • With an algebra over programs could you solve
• How does functional analysis relate? Seems very related.
• Can you do something like construct your program in a specific algebra of programs?
• Human reasoning seems to use some algebra of concepts. E.g. I can talk about a milk bottle that has two openings connected to different internal components.
• Concrete task:
  • Read Bakus lecture on FP
  • Look at Gathman script
  • Create a runable program that defines the 1D Bit Automato at the low level, purely in terms of objects.
  • Define the functions that can meaningfully combine any of the low level objects
    • This algebra should be complete, in that any object that can exist is constructbile from some set of atomic concepts and object operations in the algebraic structure.
  • Learn the very basics of smalltalk to evaluate if using smalltalk would make programming so much easier that the switch is worth it.

The name Object-to-Word-Network is interesting because it makes your brain conceptualize the object relationship as a network, without me already having a good idea of how to model object interactions as a graph.

How do objects communicate with each other? Each object could send messages to adjacent objects. Each object could know how it interacts with other objects. Specifically, each object could define an interface, meaning a shape that this object knows how to react to, if another object that it interacts with has this particular shape. E.g. in Minecraft a stone can know how much force is required to break it. A pickaxe then asserts force onto the stone, but so does TNT. The stone need not know if a pickaxe or TNT breaks it, just how much force is applied to it. Generally, programming concepts like interfaces, smalltalk messages, network protocols, and so on might provide a useful conceptual framework for thinking about object interactions.

We define objects indirectly. We want to find a specific structure that perfectly models the world. This structure can be a set of objects \(O\), together with an update function. The update function is hardcoded to simply call the update function on each element in \(O\). \(O\) contains what we call objects.

An object only needs an update function. That is the only requirement. However, each update will usually query \(O\) (\(O\) is read only) to know how it should update itself.

structure Object :=
  ObjectStructure : Type
  -- update the state of the object
  update : Object → Set Object → Object 
  -- Calling the objects update function gives correct result for the current context?
  updateValid : Set Object → Bool 
  -- Deconstruct the object by constructing the concrete object that it is composed of.
  downTranslate : Object → Set Object 

incList = map (+ 1)
incList' x = map (+ 1) x
incList'' x = map (\y -> y + 1) x

foo a b c d e = e b d a c
foo = ((flip . (flip .)) .) . flip (flip . (flip .) . flip . flip id)

foo a b = b c
foo = ((flip . (flip .)) .) . flip (flip . (flip .) . flip . flip id)

foo a b = [b, a]
foo = flip (:) . return

There are factorial many permutations of the input arguments, meaning that there are

Point free style is good in practice. ~Gurkenglas

Function application is

• Point free style is good because it reduces the size of the search space.
• How to do program search by algebraic manipulation on programs.

pointfree.io

You could prove whether the goaldbach conjucture is true by being able to calculate if it is \(O(1)\) or \(O(n)\) for doing proof search.

• Unedrstand point free style.
  • Undestand how to do algebra with programs.
• Understand SKI Combinators
  • I think their purpose is to be simple to reason about formally. That's probably (ask GPT)

Consider that we have the program \(\left( (f \circ g) \circ h \right)\) where \(f\), \(g\), and \(h\) are programs and \(⚬\) is the function composition combinator. We can algebraically transform this program: \[\left( (f \circ g) \circ h \right) = \left( f \circ (g \circ h) \right)\because\text{ composition is associative }\]

In general if we prove some identity like \(h = f⚬g\) for some functions \(f\), and \(g\), then in any expression in the current context we can substitute \(f⚬g\) with \(h\). In this case we can transfer properties of \(h\) (i.e. knowledge about \(h\)) to reason about \(f⚬g\).

The above is a trivial example, of iteratively rewriting a program in a way that preserves functional equality. I expect there are non trival ones. Things that seems possible:

• Rewrite the code such that it does the same but is more performant (probably compilers to something similar).
• Iteratively construct a program according to a target specification.

One feature of this style of reasoning is that we don't need to quantify over arguments. I intuit that this is an important property. Instead of needing to reason on the argument level, where would have potentially properties like \(\forall x \in A,f(x) = g(x)\) we instead reason about what properties a combinator expression has, probably usually based on what properties the operates and operants have.

Somehow it seems that the size of possible combinator combinations is smaller than the size of all functions and arguments. After all for every combinator combination we could expand it such that it does talk about it's arguments. But then there is just more stuff to reason about. It seems that we can “compress” our reasoning into the space where we only consider properties of programs as a whole, and properties of combinators.

Possible:

1. Find concrete algebraic program manipulations, useful for constructing programs.
   • Something like “my function needs property P and using a combinator would make it have this because it has property set X and this combinator application has property Y that tellms me what properties the resulting program will have, based on the combinator and the properties of the combined progarms”.
2. Develop an algebra of objects.

In this document we use the term Algebra as used in Universal algebra: A set A together with a collection of operations on A.

Object World Network

• The algebra of objects could be such that

Algebra of world descriptions

• Formalism/Algebra that allows transformation and combination of different world descriptions, that guarantee that any resulting world description still perfectly describes the world.
  • This could go so far that world descriptions can be structureally dissimilar and than the structures themselfs can be combined.
  • Objects are part of the world descriptions so an algebra on them is useful.

Objects could model themselfs. Specifically when we run the simulation of the world, each object observes how it interacts with other objects. And this self knowledge and self modeling would transcende specific object instance. A glider in the game of life could know that if it flies into a wall, it will die. But this knowing is performed by a cartesian system that observes this particular glider and it's disintegration (or potentially even multiple gliders). So there is a sort of Meta Glider entity that can get to know gliders that looks at a glider from a cartesian prespective. This is valid if we are talking about a simulation of the world, because there cartesianess can be easily enforced.

• Bacteria under microscope.
  • Already know that the object is a good component of the world model.

This is about trying to make the perfect physics simulation that I already have, be faster by building more abstract world models (objects that interact with each other).

Another thing you need to figure out

• Try all possible algebraic manipulations to get an object.

Object World Networks are about

Imagine you have a perfect model of the world that is though too computationally inefficient. I think we want to optimize this model first for lossless computational compression, i.e. making the model run with less compute but still being perfectly accurate. This makes it easier to evaluate if you're going in the right direction. Simply check if your model is still perfect and how much faster it got.

Once you try to find a lossy compression, you need to now be able to properly evaluate whether the trade-off of losing accuracy in the overt model is worth the efficiency gain in running the algorithm.

brainstorm

• what johannes doing
• what julia doing
• overlapping intersts
• conflicting models

figure out alignment ??? trying to think about alignment problem from scratch-ish

current leaf nodes / threads of thinking

• homo sapiens cultural foom transition
• is there an “intelligence core” or “generality-binary”
• causal&telic tags which allow shape for “agency”

some general topics of interest

• corrigb/friendliness, attractor
• “intelligence introspecton”
• abstractions

predictions: world state graph, world object networks, etcetc downstream of “intelligence core”

whats your process: different answers

BFS finds a path in any graph. In general brute force search can do optimal reasoning.

Therefore the core of intelligence isn't so much about how to be able to reason about the world, but how to do so efficiently.

(There are still some other issues though like embeded agency.)

• Abstractions are important.
  • Abstractions need to capture what you care to model at sufficient detail, such that you can perform the computations that you acre about (e.g. simulating the world) at a sufficient level of accuracy.
  • you need to be able to iteratively update your abstractions.

Human can handle ontology shifts well because they don't even talk about certain things. For example, when I think about a clock, I would think about it in terms of gears. So if I now realize that atoms are not real and there is only a quantum wave function, it wouldn't change how I think about a clock because I'm already thinking about it in a different conceptual framework without referencing atoms.

Looking at software engineering, we can see a bunch of different strategies for making a system robust to changes.

• Git version your system and have tests and automatically roll back to the last version the tests they're passing if the current version breaks.

1. Think something.
   • This might involve drawing on a whiteboard, speaking, writing in a text document, writing down math, writing down pseudocode, doing interactive programming, etc.
2. Compress your thoughts.
3. Replace the original thought with the compressed version such that you have a larger capacity for new thoughts.

• Somebody can tell you how to c
• GPT is trained and now its knowledge is fixed. Actually it can learn new things during a “context window”, but this will be forgotten afterwards. Even if GPT says that it learned something new, it hasn't in the long run. And just having this one convesatino be in the new training dataset would probably not be enough data to make GPT get this right in general.

LLMs can't observe some data and then update their ontology without destroying it, using only few datapoints.

The weapon damage of speech scales with intelligence, not with strength.

Can you have an intelligence without language? A dictionary allows you to have short names that map to larger datastructures. This seems to be a generally useful thing. So something like this would show up in the internal structure of an AGI.

Inventing names is relly useful. It's underused. When you actually need to explain something you need to recursively unroll all the concepts, and give them names to iteratively build up the concepts that you want to communicate until you finally have enough concepts in the other persons brain.

• How can we create a system that optimizes in the direction we want?

Q

• What is a goal directed agent

Fragility of extreme states ‘

• If you have a ‘goal directed agent” and want to do X, aiming it at \(X + \varepsilon\) is usually not good enough. Why?
  • Depends on metric. Which metric causes this?
  • Ontology issues w this formulation.
• If you have some variables \(\left( x_{i}\sim X_{i} \right)_{I}\), optimizing \(\left( x_{j}\sim X_{j} \right)_{J}\) pushes \(\left( x_{i} \right)_{\left\{ I - J \right\}}\) into “extreme” (low probability?) values. Why?
  • Okay I have some semi-formal intuitions could write down if load-bearing. Variables are related & optimizing x_i pushes x_i inte extreme which forces x_j into extreme.

Extreme values are reached only for variables not specified in the goal (implicitly it means they can be any value). If I only add a small

Intuitions

• self awareness of “flaws”. the thing knows it was initialized close to. but not at an attractor fix-point. it will try to reach this point
  • property X (X is the optimal algorithm/goal): ‘I” ‘probably” am close to X, but not X. I will act with this in mind, and avoid making ‘mistakes” which might be due to my distance from X.
• something which this is not: ‘uncertainty over the utility function”
  • you dont want the AI to open up the human or manipulate the human to give G, and then the AI optimizes for G.
• apparant paradox: intuitivly we do not desire our corrigible agent to ‘want” anything. But we desire it to ‘want” to be corrigible.
  • perhaps we do not desire out AI to ‘want” to be more corrigible. simply to ‘assist” the ‘user” in making itself more so.
    • How could one get around the standard notion of instrumental goal conservation?
• We want our ‘user” to be ‘better off” for having the AI assist it, rather than not.
• the AI needs to employ internal consequentialist reasoning. but this needs to be careful not to ‘optimize” in a way which could cause ‘mistakes” to propagate.
• have some ‘user'. want the AI to try and ‘empower” ‘user'.
  • dont want the AI to ‘steer” through ‘manipulating” ‘user”

Objects can be modeled as a map of properties like

structure Car :=
  Make : String
  Model : String
  Built : Datetime
  Color : Color

together with combinator logic, i.e. a definition of how the object combines with other objects. For example, yellow can be an object of:

(def-abstraction Yellow
  (properties {:color #FFFF00})
  (combine-with (abstraction?) 
                (set-if-exists (color abstraction) (:color Yellow))))

such that we can say Yellow + Car {color : black, …}= to get a description of a yellow car.

Can we combine the abstractions Wind and Newtonian physics?

Newtonian physics can be represented by a program P : WorldState → WorldState. Multiple ways of combination exist:

1. Let P : List Parameters → WorldState → WorldState while wind is:

structure Wind :=
  strength : ℝ
  direction : Vec3

such that a Wind instance is passed to P. Now P needs to know how to use P correctly.

1. We could think of P and Wind as ECTS systems. P updating arbitrary values, while Wind updates only the velocity component. Both systems can be computed independently and then combined by vector addition of the velocity components.

Here we are effectively adding two programs by combining their results (which is easy because the result datatype already has an algebraic structure).

1. Add programs directly. This seems very hard.

My minds eye is a high actuation space. What makes it so?

• I have concepts like shark that have visuals associtaed with them. I have yellow that has visuals associated with them. I can add these concepts to get a new concept with different visuals, i.e. I can comibne concepts to very quickly build up an almost infinite variety of visuals.

In the past I bought things. If I want something in the future I don't want now, I could use money to buy it.

Programming, physics and math are also generally useful.

To determine if a concepts is useful you can check how it combines with your existing concepts. Computercraft.

In Lean, every definition has a type. To check whether in a theorem there is a step I need to perform that I already know how to perform, I can simply search through all the types in the library. We can index the types, such that this is fast. For concepts, we can imagine a similar thing, where we look at the shape of the concept and match it to concepts we already know.

The concept yellow, which has a color property that it sets on an object, can interact with any object that has a color. If you have many objects that have the color this concept is good.

Now need different mechanisms

1. evaluate if the combinations are useful
2. generate the concepts in the first place.

Newtonian mechanics allows us to simulate the world, and then evaluate the results. New concepts could be evaluated in simulation.

Even if you want general knowledge, you might want to set yourself specific targets. Targets where you expect if you'd solved them, you would need to have understood something new and important. And then evaluation in a simulation becomes easier because you know where you're trying to get.

Ask the question, what is a thing I cannot do right now, at all, is it because it is physically impossible or is it because I don't have certain knowledge? If it is because I don't have certain knowledge, then try to obtain that knowledge.

This allows you to understand if you have learned something.

Specifically we start in the situation where we can build using our world model target states to reach that we don't know how to reach. We then try to optimize for reaching this state, gathering the required knowledge along the way.

Iterating this process with random goals would make us smarter and smarter.

How can we determine a target that is not too hard?

You can evaluate if flying would be a useful ability:

Brain:

1. What is flying about? It's about moving my body around.
2. Do I already move my body around? Yes, e.g. to go to the supermarket.
3. Would flying be better than my current way to get to the supermarket? Yes, assumeing I can fly fast.

Brain: Preliminary analysis indicates flying would be a good property to obtain.

The brain could think about it longer, discovering more advantages, disadvantages, and other facts like needing pilot goggles. This tends to increase the probability that the analysis is correct. The brain employs an anytime algorithm.

The main impressive thing is how fast the preliminary analysis completes.

Setup:

• You have a specific goal just outside of what you know how to do.

At what point does the learning happen? I could:

• Using the current world model try to find a plan to reach the target.
• I will get stuck at some point.
• What is the shape of the hole in my mind?
• Do wishful thinking: What action if I could do it would allow me to get to the goal
  • E.g. if I had a sticks I could make an iron pickaxe, but I don't know how to get stick. How to get sticks is the knowledge bottleneck.
  • We generated a subgoal, i.e. an even narrower target.

• If you don't have a model you can experically probe the world.
• If you have a model you can calculate what to do without probing the world (probing is expensive).

Imagine you want to shoot the cannonball. You could set up three locations and through trial and error find the exact settings that make the cannonball fly to these locations. Alternatively, you could know Newtonian mechanics which would allow you to compute how to aim the cannon such that the cannonball lands anywhere.

Adding buttons to fire at the tried-and-errored locations would make shooting there very easy. Calculating Newtonian mechanics still is hard. Finding Newtonian mechanics though makes the adding of new buttons easy.

We can write a logical predicate selecting desired elements to perform exhaustive search.

A general way to make this more efficient is to try to prune as many possibilities as soon as possible. The human brain doesn't even generate extremely stupid plans, Like jumping from the third floor to get down to the street, even though it is faster.

Let \(W\) be a set of world states. Let \(P\) be a predicate selecting desired world stated.

Two targets:

• Concepts should be few. Therefore having larger objects like table instead of have this table plate with these legs is better.
• Concepts shouldn't break easily. A plate on a table is a concept breaking when I take away the plate.

• be minimal.
• Reuse your exsiting data
• Once you have a guess, generate positive and negative examples to verify it.
• Generate examples where you're maximally uncertain about the outcome. Heuristic for most relevevant evidence.
• Side channels
  • The time to compute for the master, the predicate, can provide information.
• Find an example such that a perturbation to this example, as small as possible, changes the truth value. E.g. append a single 0.
• predict every outcome.
• You need to try to falsify your predictions.
  • Otherwise, through sheer accident, there might be a pattern you spotted in the data you generated and verifying that pattern would always hold true, maybe, for example, if just any string was true, meaning you have a too specific theory that you started with and never discarded because you didn't try to falsify it.

When playing Zendo with bitstrings of length \(n\). Consider the subset of 2-tuples of bistrings \(B \subseteq \left( {\mathbb{B}}^{n} \right)^{2}\) such that \[\forall(a,b) \in B,\exists i \in \left\{ 1,2,\ldots,n \right\},\text{ flip-bit}(a,i) = b \land P(a) \land \neg P(b)\]

meaning, the 2-tuples describe a boundary. The first entry in the tuple is a point for which \(P\) still holds, while the second is a “close by” point for which \(P\) doesn't hold.

Assuming we have this boundary set. How can we generate a hypothesis from this set? I intuit it's helpful.

We tested an intuition by turning it into an algorithm and then empirically evaluating whether that algorithm is capable of gathering, given a predicate, useful examples with which you can infer what the predicate is in bit strings and all.

Using the algorithm, Thomas figured out in less than 10 minutes the predicate that the first two things in a string need to be the same and the last two also need to be the same, whereas I took over an hour.

This seemed very good, we never so far managed to get to the point of writing code such that we have some concrete outcome like empirical evidence that some algorithm is actually probably good.

Solving Zendo requires to know:

• How to form hypotheses?
• How can we ask the right question of the environment that give us maximum information (minimizing the amount of evidence we need).
  • What is good evidence?
• How to efficiently verify a hypothesis?

How to form hypotheses is the bottleneck.

how-to-turn-a-potato-into-the-sun describes a heuristic to obtain good observations. Having good observations could make it easier to find the hypothesis generation algorithm.

We give a simple solomonoff inductor style Zendo player. In addition to updating, it selects the bit string which would eliminate most hypotheses.

Let \(\mathcal{P}\) be it the set of programs with description length \(< n\). Let \[\forall p \in \mathcal{P},P(p): \propto \frac{1}{2^{2|p|}}\] meaning \(\mathcal{P}\) is distributed according to the universal prior.

Now, we want to find a bitstring that eliminates maximally many hypotheses:

A bitstring where the above sum is zero eliminates half the hypothesis space, in terms of probability mass.

To speed this up:

• Terminate too long running programs.
• Only sample a random subset from \(\mathcal{P}\).
• Randomly sample bitstrings to try.
• Terminate if you are close enough.
• Use HVM SUP nodes.

Prototype: it should be possible to compute many uncertainty-reducing bit strings and by studying them reduce the uncertainty more. Imagine, you figured out some patterns in addition to just updating your probability distribution. For example, that the first bit is always 1 if the string is true. This might just be part of the rule and not the complete rule. But in this case, you could still determine that some particular strings your distribution is uncertain about are likely to be true or false.

• What is intelligence?
  • How do you create a model of the world?
    • Given the world state graph, how do you extract the structure of the world?
  • What is the datastructure that can represent a very complicated world well?
  • What algorithms have the property that any AGI that you might look at would have some version of these algorithms?
    • creativity
    • Update the world database in Observation.
    • run simulations using a world model
• How do you make a mind want to help you?
  • Have your best interests in mind.
  • Be wary of its own ignorance to not accidentally do something you don't like when it's uncertain what you won't like.
  • Human can totally do this. I can imagine there is an alien somewhere and now I need to optimize for the alien.
    • I wouldn't start by shooting nuclear missiles at that planet, probably.
    • Sending them some technology blueprints might be nice though.
• Goals
  • How do you specify a goal that's not what you want and then have the agent still do what you want? (corrigibility)
  • How do you make a goal such that a small perturbation of the goal causes only a small perturbation in the effect of what world state maximizes the goal?
• Embedded agency

It seems like I fail to consider and write down the motivations behind what I am doing.

I mainly follow my intuitions, but often when people ask me why I am doing something, I am able to produce an explanation. Generating this explanation often helps to clarify my understanding.

It seems good to be more conscious about and explicitly ask myself the question intermittently of why am I doing this, why is this a good idea, how does it look like if I succeed.

Generally there are different kinds of knowledge:

• Running away when low on health in LOL is a general good strategy.
• As a Medic in battlefield you want to try to survive as long as possible, while reviving as many teammates as possible.
• In Insurgency you might see somebody running to cover. They are now occluded, but you can calculate how to throw a grenade to blow them up.

Running away on low health is a good strategy that generalizes across most games. If you don't know what game you are playing, it's a good bet that doing this is good.

The medic strategy is only good in the context where you are actually a medic. When you fly around in a helicopter you can't can't even revive anybody. Part of the strategy becomes nonsensical.

Knowing how to exactly throw a grenade when you are at position A, and enemy is at position B, given the (potentially partly destroyed) terrain C, where A, B, and C have some concrete values, is only useful in exactly this situation. There are so many possibly values for A, B, and C, that it is infeasible to precompute how to throw a grenade in each possible situations.

Instead you need a model of grenades. This consists of knowledge: How do they bounce, how far can I throw them, how arced is their trajectory, how long until they explode, how much damage do they do at what ranges. We also need an algorithm that can based on this knowledge quickly compute the solution of how to exactly throw the grenade in every situation that is likely to be encountered.

Generally each pice of knowledge has a “usage context”. Meaning the knowledge is only true/useful if the context satisfies certain predicates (like conditional theorems in math).

So generally our world model is structured to have factual knowledge, such as this particular object has these general properties, as well as algorithms that can efficiently calculate solutions to specific problems given the factual knowledge.

Roughly factual is just data (tree has the burnable attribute set to true). Note though that any factual knowledge could be represented by an algorithm and any algorithm could be unrolled into pure data (generate a lookup table).

Usually, procedural knowledge requires more compute, but less storage than factual knowledge, because solutions can/need be generated on the fly.

So how does learning about the world look like?

1. figure out the basic rules of the world.
2. Learn increasingly specific strategies that apply to specific situations.
   • Don't learn strategies so specific that they only apply to a single situation, when there are many possible situations of that kind and you don't know in advance which one you would be in. Instead, construct knowledge and an algorithm that can dynamically generate a solution.

Knowledge/Strategies can be general.

structure Knowledge :=
  conditional : Prop
  consequent : Prop

Knowledge is more general the smaller the conditional is.

Example: Linear search is more general than binary seach because it does not require the input list to be sorted.

Knowledge is procedural if the consequent makes statements about an algorithm.

Example: IF the list is sorted THEN binary search sorts it AND runs in \(O\left( \log n \right)\).

\[\forall f \in \text{ FSA},f\left( \lbrack\rbrack \right) = f.\text{states}\left\lbrack f.\text{start-state} \right\rbrack.\text{return-value }\]

\[P_{1}(f) = \top,P_{2}(f) = \left( f\left( \lbrack\rbrack \right) = f.\text{states}\left\lbrack f.\text{start-state} \right\rbrack.\text{return-value} \right)\]

\[\forall f \in \text{ FSA},\forall x \in f.\text{return-values},f\left( \lbrack\rbrack \right) = x \Leftrightarrow f.\text{states}\left\lbrack f.\text{start-state} \right\rbrack.\text{return-value } = x\]

\[\forall f \in \text{ FSA},\forall x \in f.\text{return-values }:P_{1}(f,x) \Rightarrow P_{2}(f,x)\]

Construct a minimal example where we have a set of axioms \(A\), from which we can proof a theorem \(T\) using LEM, such that we can add a axiom (that doesn't make the axioms inconsistent) to \(A\) such that \(T\) is no longer a theorem.

1. Axioms: \(A \rightarrow \bot\)
2. Theorem: \(\neg A\)
3. Proof: Assume \(A\) then \(\bot\), therefore \(\neg A\).

1. Axioms: \(A \rightarrow B,B\)
2. Theorem: \(A\)
3. Proof:

• Distill the content such that we can evaluate where the bottlenecks are.
  • Write down the algorithm in a nicer format, with clear step by step instructions.
• Currently the bottleneck seems to be: How to calculate a property that is true of all elements of a set (e.g. a set of bitstrings).
  • related: What are existing logic simplification techniques, and ways to add quantifiers?
• How to use a predictive property once we have it?
• Implement prototype algorithm

• Good conceptual progress.
• We thought only at a very very high level of abstraction, writing down very very rough algorithm descriptions. This was good because it allowed us to move very fast, and identify bottlenecks, and get less confused.
  • It would have been a mistake to focused on writing down any part more cleanly.
• As a general strategy you want to focus on the most confusing part, or the part you understand least how to do, instead of developing the things you already understand. However developing the things we already understand is the natural easy thing to do.

Meta

• Using laptop on whiteboard maybe good.
  • Makes me use whiteboard less.
  • More frequent switches between writing and whiteboard.

Ideas

• Compression

Let \(F\) and \(G\) be compression algorithms. Let \(G\) be some other compression algorithm (e.g. gzip). Let \(D\) be some data. What does \(\mathcal{C}(D) ≔ \frac{F(D)}{G(D)}\) tell you.

E.g. \(F\) is a an algorithm that finds the perfect FSA that generates the data. \(G\) is gzip.

If \(\mathcal{C(D)}\) is small then it means that FSAs are very good at representing \(D\), while the other compression algorithm is worse. It semes this could tell us esomething important about FSAs. Namely what things are easy/natural to represent for FSAs.

So finding \(D\) such that \(\mathcal{C}\) is small, tells what FSAs to study, namely the nose generated by \(F\).

The choice of \(G\) and it's realition to \(F\) is very unclear.

Intuitively we want to capture the notion that we are suprised by how good \(F\) is at compressing something. For that we can also compare the description length of \(F\)‘s FSA and the description generated by \(G\) together with the unzip algorithm.

If we find a \(D_{2}\) such that \(\mathcal{C}(D_{2})\) is small then it tells us that \(G\) is too good. It means that there is no FSA that can encode \(D_{2}\) well.

Let \(A\) and \(B\) be finite sets. Let \(f\) be a function from \(A\) to \(B\).

Theorem: There exist a FSA with the same functional behavior as \(f\).

Proof: Because the function has only finitely many behaviors, the FSA can simply be a tree, selecting some exact output state. \(\blacksquare\)

Every FSA is isomorphic to some finite lookup table.

Let \(D\) be some data, consisting of a set of 2-tuples, where the first element in the tuple is a finite bitstring, and the second is a single bit. We can now construct the hardcoding FSA \(H\).

Now iteritively simplify that FSA without changing it's behavior to to get something which can generate \(D\).

Given some concrete FSA, we can find an input that produces a particular output, by first finding a state which has the desired output state, and then search backward with BFS, until we find the starting state, keeping track of all edges we use, which corresponds to the sequence of inputs we need to give.

More formally, let \(f\) be an FSA \(\left( \Sigma,\Gamma,S,s_{0},\delta,\omega \right)\) with \(\Sigma ≔ {\mathbb{B}},\Gamma ≔ {\mathbb{B}}\).

We can find an input \(i \in \Sigma^{\ast}\) with \(f(i) = \gamma\) where \(\gamma \in \Gamma\), by selecting an arbitrary state \(s \in S\) with \(\omega(s) = \gamma\), and performing BFS in the reversed graph describing \(f\)‘s state transitions, until we reach \(s_{0}\).

Given a FSA \(f\) we can generate all possible input output pairs by performing BFS, and saving the input output behavior as we move along. This avoids redoing compuations.

E.g. given the input string \(a ≔ 101\), \(b ≔ 1010\), computing the input output pairs with \(\left( \left( a,f(a) \right),\left( b,f(b) \right) \right)\), would result in us causing mostly the same state transitions to occur in the FSA.

Generally with BFS we can deduplicate computations for bitstrings that share an initial similar segment. Though it is actually even better than this, because multiple inputs can take the same transition path.

[

], We can represent all DFA up to some number of states \(n \in {\mathbb{N}}\) with a NFA.

To model an DFA \(f\) that has \(n\) states we need a NFA with \(2n\) states where half these states are accepting, and half are rejecting, because we don't know how many states of \(f\) are accepting. Now though by selecting particular transitions, we can get anything between “all states accepting” to “all states rejecting”.

The starting node is a special case. We need 2 start states, one which is accepting, and one which is rejecting.

• Create large NFA \(N\) representing all DFA up to size \(n\).
• Use FSA backtracking from (??, a) to eliminate the most candidates.
• Alternatively find the state that has the most non-deterministic edges, where half of the these edges for the same input move to output 1, and half to output 0.

Get observations, and update N by removing edges that are not compatible with the observations received:

As you get in observations iteratively construct an NFA \(N\). For each new observation, add all nodes and vertices which would produce the concrete result, we have observed.

Then run \(N\) on the newest observation. Now select all paths, through the FSA which produce a wrong result. For each path, delete the last edge in the path in \(N\).

Note that if we get observations of the form \(\lbrack\rbrack\) \(\lbrack 0\rbrack\), \(\lbrack 1\rbrack\), \(\lbrack 10\rbrack\), etc. then always the last edge is the wrong one, because taking one less step must have produced a correct result, otherwise the edge would have been pruned in the previous iteration.

If we don't iterate like this, we could search over the string to find the shortest.

Note that with this method we can throw away our observations without losing information because our NFA is in a sense a perfect model of the observations we have received so far (but new observations can invalidate parts of the model). This is a general desiderata we want for modeling procedures.

FSAs can't compute functions where the size of the state you need to keep track of is proportional to the size of the input. This is because the states are hardcoded in the FSA architecture itself. There is no mechanism to dynamically create more state, e.g. by pushing something onto a stack.

Example of a set of strings that FSA cannot describe: \(\left\{ 0^{n}1^{n}|n \geq 0 \right\}\) (bitstring of length \(2n\) where the first half is 0 and the second half is 1).

As previously discussed, we could

Instead we could generate a set of FSAs that have the same input output behavior and then try to generate a property they share.

Another approach could be to generate an FSA \(f\) and have it generate some input-output pairs \(o\). Then we want to find a property \(P\) of the from: \[P(f) ≔ \left. \left( P_{1}(f) \Rightarrow \forall x \in {\mathbb{B}}^{\ast},P_{2}\left( f(x) \right) \right) \right..\]

In the simplest case \(P_{1}\) could be “its exactly the FSA \(f\)”, and \(P_{2}\) could be the property encoding exactly the observed behavior with \(o\).

Now we want to generalize \(P_{1}\). What are the properties that are actually needed to make \(P_{2}\) true?

• How do you get the predictive properties?
  • Sample a bunch of FSA.
  • Generate a bunch of input output behavior.
  • Represent the fsas and the inputs/outputs as a single logical formula.
  • Simplify the formula
    • simply using logic rules
    • Simplify by cutting stuff, e.g. ignoring a particular state in the FSA, and at the same time ignoring the input/ouput pairs effected by this simplification.
  • Simple formulas on FSA describing complex input output behavior are good.
• How do you use them?
  • Given an observation (input-output pair) find the predictive properties that are compatible with the observation, and compatible with what we know about FSA so far.
    • It feels like we could just use automatic resolution.
  • Try to falsify the hypothesis.

The idea is that we want to find properties which tell us small bits about the FSA we are trying ot infer. The predictive properties should faccilitate this. Contrary to Solomonov reduction, we don't want to try to just guess the entire FSA all at once. Instead, we want to have the predictive properties that allow us to correctly infer that the FSA must have certain properties, such that we can infer more and more of these properties, building a more and more coherent picture of what the actual FSA must be like. Each property constrains what the FSA can be.

A predictive property \(P\) is of the form \[P(f) ≔ P_{1}(f) \Rightarrow \left\lbrack \forall x \in {\mathbb{B}}^{\ast},P_{2}\left( x,f(x) \right) \right\rbrack\] where \(f\) is an FSA.

(Again note that if we figure out the overall algorithm we could use it to solve the specific problem here (which is part of the algorithm) of generating hypothesis about what is the best experiment to perform to get more evidence whether a predictive property does in fact always hold.)

• we have a long list of tuples \(\left( P_{1},P_{2} \right)\) where \(P_{1}\) is a predicate for FSAs, and \(P_{2}\) is a predicate for input-output pairs, and we have \(P(f) ≔ P_{1}(f) \Rightarrow \left\lbrack \forall x \in {\mathbb{B}}^{\ast},P_{2}\left( x,f(x) \right) \right\rbrack\)
  • example of a \(P_{2}\) predicate: \(P_{2}(i,o) =\) “1 if \(i\) ends with ‘00'”
• we can filter that list for tuples where \(P_{2}\) holds for what we actually observed
• this gives us a list of predicates, \(P_{1}\), which could hold for the FSA we're looking for
  • we use these as hints
• then we try to falsify the \(P_{1}\) predicates
  • do we know how to do this?

Let \(f\) be a DFA. If we input a string of just zeros then output of \(f\) must repeat, with a cycle \(c \in {\mathbb{N}}\) that is smaller or equal to the number of states of \(f\). This gives you a lower bound.

E.g. if the behavior is

We know that \(f\) must have at least 2 states.

This means \(f\) has at least 3 states. Note that the output could be a lot more random looking. Then it's useful to check for the cycle:

Here the cycle is \(10100\).

We can do the same with input strings of only zeros.

Note that this is an observation property, meaning we can infer what our FSA is, based on some observed input-output behaviour.

• how to play FSA Zendo as an AI
  • you (the AI) should already have some idea what programs are
    • you have a native representation of computation somehow
  • before you (the AI) start, look at the definition of FSA and compare it to your native computation to see where FSA is limited
    • maybe think of some simple rules for the ways in which FSAs are more limited than universal computation
  • you look at the observations so far and think of the simplest hypothesis (in your native computation representation) and check whether FSA can actually represent this
  • as you always do with hypotheses, try to find conflicting and supporting evidence for it
    • your native computation should be able to do something like “find a short input which makes this function return false”
      • this would ironically be incredibly easy with an FSA, because you can just do backwards search
        • but you don't know this necessarily
    • in general, your hypotheses are probably stored in a way where it's efficient to generate possible evidence (for and against it)
      • this seems very desirable
• is “finite-state-automata AI” an interesting concept?
  • an AI which can natively only use FSA computation and cannot do anything Turing-complete
  • that is, the AI itself could be written in a Turing-complete language, but in its “thoughts” it can only consider FSA hypotheses: hypotheses that can be expressed with an FSA

Let \(f\) be an FSA that takes in bitstrings, with one state, that is always rejecting.

Example input output behavior \(o\) (let this be a dictionary):

Dumb predictive property: \[\begin{aligned} P\left( \text{fsa},\text{ input} \right) ≔ & \text{fsa } = f \\ & \Rightarrow \left. \begin{aligned} (\text{input } \in o.\text{keys } \\ & \Rightarrow f(x) = o.\lbrack x\rbrack) \end{aligned} \right. \end{aligned}\]

We can spilt this further into: \[\begin{aligned} P_{1}\left( \text{fsa} \right) & ≔ \text{ fsa } = f \\ P_{2}\left( \text{input} \right) & ≔ \text{ input } \in o.\text{keys} \Rightarrow f\left( \text{input} \right) = o.\left\lbrack \text{input} \right\rbrack \\ P & ≔ \forall f \in \text{ FSA},P_{1}(f) \Rightarrow \forall y \in {\mathbb{B}}^{\ast},P_{2}(y) \end{aligned}\]

We could Split this even further. \[\begin{aligned} P_{\left( \text{FSA} \right)\left( \text{fsa} \right)} ≔ & \text{fsa } = f \\ P_{\left( \text{input} \right)\left( \text{input} \right)} ≔ & \text{input } \in o.\text{keys } \\ P_{\left( \text{conclusion} \right)\left( \text{input} \right)} ≔ & f\left( \text{input} \right) = o.\left\lbrack \text{input} \right\rbrack \\ P ≔ & \forall f \in \text{ FSA},\forall y \in {\mathbb{B}}^{\ast}, \\ & P_{\left( \text{FSA} \right)(f)} \land \left\lbrack P_{\text{input }}(y) \Rightarrow P_{\text{conclusion }}(y) \right\rbrack \end{aligned}\]

Now if we see that \(P_{\text{input}}\) and \(P_{\text{conclusion}}\) are true for the observed input output behavior, we know that \(P_{\text{FSA}}\) could be the cause of this.

It seems like a World State Graph is an “infinite FSA”: the states of the automaton are the world states and the transitions correspond to the actions.

Some major thing we did (not exhaustive):

• We tried to understand how to generate predictive properties
  • We thought about how to write observed behavior down in logic and then simplify, to get a good predictice property.
  • We understood how NFAs can moddel DFAs and how we could iteratively construct an NFA representing, our hypothesis, based on the observations.
• Simple predictive properties
  • We figured out that we can have a predictive property that just describes exactly the observed input output behavior.
  • We can then interpret the property as specifying just some part of the structure (e.g. the predictive property FSA is a subpart of the actual FSA we try to infer).
  • We understood how to compose many small such predictive properties to form an overall hypothesis, by matching FSAs to single long observed bitstring.

• Implement the FSA composing algorithm described in (??, a).
  • Write down a structured description of the algorithm in math.
  • Implement MVP in Clojure, which would involves generating predictive properties based on all FSAs of size \(n\) or smaller.

• I have no idea what I am doing. But then somehow I do good things (things seeming good in retrospect). Specifically I did not know that I could get the algorithm in (??, a). But then we did because we tried.
• FSAs so far seem to be the right choice because they are easy to reason about, write about formall, and code up.
• Sometimes we talked very abstractly until finally we did a concrete example which was then very useful.

We're trying to create an algorithm that, given some rudimentary knowledge about the system, for example an FSA, uses that knowledge to study the system such that it learns to infer what the concrete system is that I'm looking at, given some input-output behavior that I'm observing.

This is step one, where the system learns based on foundational knowledge. Step two is actually playing the game. But while you play the game and you get new information about the concrete finite automata that you're trying to infer, for example, you can use a similar reasoning process to know more about the concrete specific automata you're trying to find.

A predictive property is a logic statement of the form: \[\begin{array}{r} \forall f \in \text{ WorldModel},\forall o \in \left\{ \left( x,\text{ observe}\left( f(x) \right) \right)~|~x \in \text{ WorldState} \right\}, \\ P_{1}(f) \Rightarrow P_{2}(o) \end{array}\] where WorldModel is the set of functions from \(\text{WorldState } \rightarrow \text{ WorldState}\).

Alternatively we could have WorldModel be \(\text{WorldState } \rightarrow \text{ Action } \rightarrow \text{ WorldState}\) :todo: \[\begin{array}{r} \forall f \in \text{ WorldModel},\forall o \in \left\{ \left( \text{List (Action × Observation)},\text{ observe}\left( f(x) \right) \right)~|~x \in \text{ WorldState} \right\}, \\ P_{1}(f) \Rightarrow P_{2}(o) \end{array}\] In Lean:

-- We need this import to use setbuilder notation
import Mathlib.Data.Set.Basic

-- We untroduce the neccesary types
opaque WorldState : Type
opaque Observation : Type
opaque observe : WorldState → Observation := sorry
def WorldModel := WorldState → WorldState

-- Given a world model, the stateObservations, is the set of all possible
-- input output behaviors.
def stateObservations (f : WorldModel) : Set (WorldState × Observation) :=
  { (w, observe (f w)) | w : WorldState }

-- A predictive property asserts something about the input output behavor of a
-- world model, given that the world model satisfies some other property.
def predictiveProperty (P₁ : WorldModel → Prop) (P₂ : (a : WorldModel) → stateObservations a → Prop) : Prop:=
  ∀ f : WorldModel, ∀ o : stateObservations f, (P₁ f) → (P₂ f o)

A predictive property says that if a property \(P_{1}\) holds for a world model, then the world model generates observations for which \(P_{2}\) holds.

We want to use predictive properties to form hypothesis about the real world, Using our world model. Note that the WorldModel type is the type of all possible world models we could consider, and not any particular world model.

The goal is to figure out which concrete world model from WorldModel describes reality.

To make things more concrete let's consider that our world model is an FSA. \[\begin{array}{r} \forall f \in \text{ FSA},\forall o \in \left\{ \left( b,f(b) \right)~|~b \in f.\Sigma^{\ast} \right\}, \\ P_{1}(f) \Rightarrow P_{2}(o) \end{array}\]

A predictive property says that if a property \(o\)

Where \(f\) is a FSA, and \(o\) is a subset of \(\left\{ \left( b,f(b) \right)~|~b \in f.\Sigma^{\ast} \right\}\).

Predictive properties can be used to generate hypothesis. Given that we observe some When playing bit-FSA Zendo,

Generate the set of prodictive properties by

Each game of Zendo is about learning the generating rule. Counterstrike is in large part about aiming at the enemies head. Infering a rule and aiming seem qualitatively different.

Let's first consider the task of computing \(3 + 5\). There is only one answer: \(8\). And this answer takes the form of a pice of data. Now consider the task of adding two numbers in general.

:todo:

How is this different from having perfect aim in a shooter?

• In a limited sense you need to “learn” how to shoot somebody in each sitution.

In both situations, there is some problem \(P\) to solve: <\(p_{1}\): Infering the rule/\(p_{2}\): aimingat animies head>. Initially we can't solve \(P\). What does the the best algorithm \(a^{\ast}\) for solving \(P\) look like.

\(p_{3} ≔ \text{ compute }5 + 3 = ?\)

\(p_{3}\)‘s solution is \(8\). A constant value. But \(p_{2}\)‘s solution can't be a constantant, because there are too many situations where you need to shoot somebody. You need algorithm to calculate how to aim given the current sitution.

In the simplest case you know where you are, where you are looking, where the enemies head is and then use linear algebra.

(also bullet dropoff)

For \(p_{3}\) knowing the solution is about remembering a concrete result. For \(p_{2}\) the solution is remembering how to do something.

For \(p_{1}\) we also need to find an algorithm that find a solution. However the computational steps that are used to play Zendo are different for each game. If you get different observations you form different hypothesis. Computing how to test an hypothesis is different based on the concrete hypothesis. Therefore to solve the problem we need to compute the best strategy, meaning while solving the problem we create new algorithms, whereas in \(p_{2}\) we didn't need to create a new algorithm while trynig to aiming.

Again this is because you can't precompute for every possible hypothesis how to evaluate it.

How can we iterate all vectors of natural numbers, denoted as \({\mathbb{N}}^{\ast}\)? Let's start by considering how we can iterate \({\mathbb{N}}^{2}\):

00
01
11
10
02
12
22
20
21
03
13
23
33
30
31
32

The rule for iteration is most easily explained by a diagram:

We start in the top left corner, and then iterate through the elements in the green l-shaped pices. In each l-shaped pice we first iterate through the elements indicated with the cyan arrow, and then the ones with the purple arrow.

Describing this algorithms in words makes it easy to see how we can implement it. We hold the right digid fixed at \(x\). \(x = 1\) initially. Then generate all pairs for when the digit on the left is in \(\left\{ 0,\ldots,x \right\}\). Repeat this but now reverse the roles, fixing the left digit to be \(x\). Now generate the pairs for when the digit on the right is in \(\left\{ 0,\ldots,x - 1 \right\}\). Note the \(x - 1\). We don't need to generate the pair \((x,x)\) twice.

We can easily extend this procedure to iterate \({\mathbb{N}}^{3}\):

000
001
001
011
111
101
022
122
222
202
212

This method extends to any \({\mathbb{N}}^{n}\) with \(n \in {\mathbb{N}}\).

We can combine all these different interation procedures into one, such that we end up iterating

0
1
00
01
11
10
2
02
12
22
20
21
000
001
001
011
111
101
3 ; (list of length 1 up to 3)
X ; here instert lists of length 2 up to 3, list of length 3 up to 2, lists of length 4 up to 1
4
5

Or more readably:

1. list of length 1 containing elements from \(\left\{ 0 \right\}\)
2. list of length 1 containing elements from \(\left\{ 0,1 \right\}\)
3. list of length 2 containing elements from \(\left\{ 0 \right\}\)
4. list of length 1 containing elements from \(\left\{ 0,1,3 \right\}\)
5. list of length 2 containing elements from \(\left\{ 0,1 \right\}\)
6. list of length 3 containing elements from \(\left\{ 0 \right\}\)
7. list of length 1 containing elements from \(\left\{ 0,1,3,4 \right\}\)
8. list of length 2 containing elements from \(\left\{ 0,1,2 \right\}\)
9. list of length 3 containing elements from \(\left\{ 0,1 \right\}\)
10. list of length 4 containing elements from \(\left\{ 0 \right\}\)
11. list of length 1 containing elements from \(\left\{ 0,1,3,4,5 \right\}\)
12. list of length 2 containing elements from \(\left\{ 0,1,2,3 \right\}\)
13. list of length 3 containing elements from \(\left\{ 0,1,2 \right\}\)
14. list of length 4 containing elements from \(\left\{ 0,1 \right\}\)
15. list of length 5 containing elements from \(\left\{ 0 \right\}\)
16. …

Note that we can change this arangement to bias the iteration. For example, we could only add the next lists of longer length every 4 steps:

1. list of length 1 containing elements from \(\left\{ 0 \right\}\)
2. list of length 1 containing elements from \(\left\{ 0,1 \right\}\backslash\ list\ of\ length\ 1\ containing\ elements\ from\ \left\{ 0 \right\}\)
3. list of length 1 containing elements from \(\left\{ 0,1,3 \right\}\backslash\ldots\)
4. list of length 1 containing elements from \(\left\{ 0,1,3,4 \right\}\)
5. list of length 2 containing elements from \(\left\{ 0 \right\}\)
6. list of length 1 containing elements from \(\left\{ 0,1,3,4,5 \right\}\)
7. list of length 1 containing elements from \(\left\{ 0,1,3,4,6 \right\}\)
8. list of length 1 containing elements from \(\left\{ 0,1,3,4,7 \right\}\)
9. list of length 1 containing elements from \(\left\{ 0,1,3,4,8 \right\}\)
10. list of length 2 containing elements from \(\left\{ 0,1 \right\}\)
11. list of length 3 containing elements from \(\left\{ 0 \right\}\)
12. …

This would make it such that we “explore” more the dimension of having different elements in the list, and “exploring” less lists of longer lengths.

This overall approach should generalize to a vide range of datastructures. For example, it trivally generates to tensors, because any finite tensor can be transformed into a vector.

Here is a sort of weird sine function which Solomonov induction would consider while a human wouldn't. \[f(x) ≔ \begin{cases} \sin(x)\text{ if }x \leq c_{1} \\ c_{2}\text{ otherwise} \end{cases}\] Note that you can change \(c_{1}\) without affecting program length that much, especially if you do stuff like \(H_{10}(5)\) where \(H_{10}\) is the 10th hyperoperation.

The last element of reduction gets more and more observations, it would converge to assigning all probability to the simple sine function.

• Iterating over all \({\mathbb{N}}^{\ast}\) vectors seemed like a good thing to figure out.
• We could have been better at setting explicitly targets we want to reach.
• Clojure seems still good.

• Benchmark how fast a Solomonoff inductor can find the FSA Zendo solution
  • Number of observations
  • For what number of states does it become intractable?
• Check variations of the Solomonoff inductor
  • Optimize to generate the next observation to eliminate maximum probability mass.
  • Have the Solomonoff inductor run with the compute-boundary observations instead of just the first \(n\) observations.
    • How much better is this than explicitly computing how to explicitly eliminate the most probability mass. How much less compute do we need? How much performance do we loose (i.e. how many more observations we need on average)?
• Implement the better algorithm of just looking at parts of the bitstring, using predictive properties to construct an overall hypothesis, from many small FSA parts that you do understand.

• So the mode of induction doesn't work because the space of the program seems to consider it too large.
  • The strategy of cutting the probability mass in half by searching would actually be optimal for figuring out the correct world given the fewest observations, but the problem is we can't do this because there are too many programs.
  • Approximating this procedure by just randomly sampling some programs also doesn't work, because only the correct program is the one that will be accepted. And there is no way for Solomonov induction to know whether it is close to a hypothesis or not. It can only just re-sample more random programs, but this is so inefficient that there are too many programs to actually have this procedure converge on the world state program.
  • This is at least my intuition.

Humans do Something smarter, they don't just throw away all the hypotheses.

Julia: Picots have a genetic algorithm that samples new programs by combining existing ones.

Julias Topic: i think the topic i wanna try to think about tommorow is something like if I have a bunch of “”“optimization-power””” in a bucket and shake, out pops demons&superints. why and what are the mechanics of this?

• example1: put physics in a universe and shake. boom optimizers (humans)
• example2: put fitness selection pressures on a planet and shake. boom optimizers (humans?)
• example3: put a bunch of meta-search in a computer. boom? optimization demons???

im happy to think about something else if you have topics you are excited about

Johannes:

• What counts as optimization power here.

Shaking molecules creates configurations such that these are self replicating.

• You can't evolve a salt cristal.

In a computer program, why do you need a function definition, such that you then say these instructions are for this function. If you didn't have that, you couldn't have a mechanism to refer and reuse the function. the function definition doesn't actually do anything in your program. You could rewrite your program such that you don't have it and just inline all the code but that sort of maybe makes your code so big that it's now impractical or something.

An RNA molecule needs to have the structure that holds all of the bases together.

But these auillary structures are not the bit that is elvolved upon (though making the RNA longer makes there be more structure).

There is an important point about that you want to have the RNA basic auxiliary structure not be changeable and only the base pairs. You want to have the RNA structure to be such that you can have continued good self-modification. That doesn't break you. If you change your auxiliary structure such that your molecule just breaks apart, then you are completely fucked. It is still possible to fuck yourself by getting the wrong base passage that the self-replication breaks, but this is sort of at a different level.

Evolution is very stupid. SGD is smarter. So SGD still can find an intelligence that would kill us. The question is how much it takes.

Genetic algorithm on set of algorithms that, but these algorithms have type signatures such that we know which genetic combinations are valid.

There can be carnivore peptides that eat other peptibes and turn them into themselfs.

It's easier to invent hunger than, “this is genetic fitness, maximize it”.

Let's say that we play minecraft. I want to have an agent that optimizes goal \(G\). \(G\) is the perfect specification that I want. I now do program search to find the frist alg

We perform program search to select the AI, but we cannot actually select all the AI based on running the goal on every possible single Minecraft world and see that it performs correctly in that world. How do we still get the AI that does actually want G instead of not wanting G? It seems like you can't do that. Possibly.

We also assume, now, that we can actually, for all possible Minecraft worlds, run the algorithm, evaluate whether the goal is good, evaluate whether the algorithm is actually good and then still kill you.

The algorithm for intelligence might be pretty simple, but pretty hard to find. Hardcoding a bunch of heuristics is easy to find, but is much more complicated.

If we have a process which finds the easy thing first, something more like SGD, then you would get a system that is not aligned with you, but would look aligned if we look at only a few observations. And the problem is that maybe if we train the system more, and it gets better and better, then it will become at some point so smart that it realizes the situation that it is in and that it has certain goals and then deceptively optimizes for the correct thing or the thing that you want, while not having the goal completely aligned with you, such that the goal would now also not be updated anymore.

Actually, if you could, for literally every single possible wild state, have the AI behave exactly like the goal specifies, then it would actually be aligned. There is no possibility for it not to be aligned, even if it was constantly internally thinking about killing you. That would be fine, because it just always behaves correctly, doesn't matter how it works.

• Go on the specification
• I cannot evaluate every possible situation in my training.
• What constraints does the training put on possible mines produced?
• The AI with a goal slot.

Humans can reflect and then cristalize into certain goals. It seems more natuarl to cristalize into “everybody should be happy” than “Everybody should have maximum freedom”.

What I (Johannes) did was to look at my own consious experience. What are my prefferences over my own experience. Then I just extend these preference to every conscious experience that exist.

The mind contains the preferences which could tell you how you like any possible world state probably, but in the form of some algorithm that could probably eventually evaluate some world state, but not in the way where you know it right now.

Humans do feel a certain way if they see a drowning bird. But they cannot conceive of having 10,000 birds drown and how they feel about it. So they need an algorithm in order to extrapolate this feeling. And there are many kinds of algorithms like that. One of them would be like I actually self-modify this so that I don't care at all.

And it is possible to, while not understanding everything, not being omniscient in knowledge, think that you want a certain thing, and then modify yourself such that you actually want that thing, and then your preference would have been like locked into some particular path, and it is possible that had you thought about it for a much longer time, if you actually wanted to have the self-modification, then you wouldn't have done it.

This is a sort of existence proof that you can converge into different paths Even if you start with exactly the same mind and the only difference is how long do you consider performing a particular self modification

You can have an AI with preferences that you like. The preferences are only in a local scope thouh. How can you know that the AI would eventually get the correct value, by generalizing the current ones.

What is scope? With a human, it seems like the scope in some sense is unlimited, because you can't think of any concrete situation, and eventually you will probably be like, I care this much about it, or it's this good. But it is scoped in the sense that it is really easy to know if you're hungry, whereas it's really hard to know for an arbitrary world state where you don't understand what the world state even is, because there's lots of physics you didn't even ever hear about, whether that's good or not.

Music is an example of a physical phenomenon that a human can assign certain values to because when they hear, interact with that physical phenomenon, then it might make them feel a certain way. But it seems very arbitrary. If you have an alien, then maybe they like different music differently. That would sound like noise to us. If you have people who were born deaf and then they got some hearing aids and then they could hear, then music sounds like noise to them. This is an example of a phenomenon that humans care about but there isn't really some instrumental reason that we should definitely care about hearing a major note in like this particular way and it eliciting this specific emotion. You wouldn't expect an alien race to exactly have the exact same response to the exact same music. Whereas you would expect them to have the same mathematics or something.

If you go to an Amazon tribe that don't hear sort of Western music and then you play minor chords, then they will say it doesn't sound sad. Because that seems to be a learned thing somehow, potentially. What kind of music elicits what emotional reaction?

It is possible to start with some preferences that are, like, localized in space, let's say. I care about these people around me. And then you care now, in the same way maybe, extrapolating your preferences, that I care about all these people being healthy on the entire planet. And that now maybe though implies an action such that you would go away from your town and more people would die there, but overall, because you teach more doctors at some school you make, less people would die.

.and so like this goal looks like the outcome after you go away to the doctor would look terrible if you if you just evaluate it based on the previous scope where you only care about the people around you.

The prefferences over the people aronud you haven't changed though. The only thing that changed is the scope.

If you take your new objective that is caring about the entire world and you then run it only on the local scope of the village that you came from, it gives you the same result. But if you now take it also calculated for the rest of the world, then these two things combined imply different policies than before.

Imagine you have a utility function u and now you pick some small state space of the world of Minecraft and you run the utility function over the world state just of this small state space. And then you take the same utility function and run it over the entire world of Minecraft you will get different policies.

The policy changes because the scope changes where we are evaluating the utility function in.

We have a training procedure for a system. We train the system on some small, localized scope. Then we observe that it is correct. But now, how do we know that it would generalize to all possible states that could have preferences over and always have exactly still the correct preferences that we wanted to have there also?

By default, if we train a system to have preferences over a small scope, it will also have preferences over the larger scope.

The AI on Minecraft cares exactly to behave as my Minecraft assistant. We have a proof of that. But then the AI also cares about a lot tiling the real universe with bananas. And my proof doesn't say anything about that. And therefore the AI will actually try to escape and tile the universe with bananas because it just cares so much about that.

You can take abstractions, combine them into new abstractions, meaning if you have preferences on your lower-level abstractions, you probably can build sort of arbitrary structures and have preferences over them, such that you can, like, anything you can build with your world model you have now preferences automatically over if you have preferences for all the low-level building blocks, and therefore you care about lots of things that are possibly not even in the world, just as humans can imagine, like, situations in their head that are physically impossible.

I give you the laws of the universe. You give me a “brain” that's good at thinking about this universe.

In the world of logic: I give you a set of axioms. Now every logical sentence is either true or false. Roughly for any true sentence there is a proof, that shows that it is true. To figure out whether a logical sentence \(S\) is true or false we can simply enumerate all proofs until we find a proof for \(S\) or \(\neg S\).

But this is fucking slow. It doesn't qualify as a brain that's good at thinking about this universe.

Given a complete set of physical laws of the world, generate a world model that allows you to efficiently reason about this world.

Given a low-level works module, how can you build a high-level one?

:todo:

This article summarizes my work to date (2024-08-30).

Developing the right step graph.

• Object World Network
• What are Abstractions
• Zendo
• World Modeling
• World state graph

:todo:

Every data structure can be represented as a bitstring, and in turn as a propositional sentence \(S\). In \(S\) each variable represents a bit.

Depending on the datastructure we may need additional constraints. E.g. a positive number might be defined in terms of the first bit, which represents the sign of the number being always 0.

Note that we can always collect two distinct datastructures into a 2-tuple.

Once we have a datastructure encoded, we can add assertions about the datastructure. E.g. that some number \(X\) is larger than a number \(Y\). Really anything that can be said about this datastructure can be said in propositional logic (but it might take many clauses).

Once you added these logical assertions to the system we can use a SAT solver to answer questions. E.g. what are possible values of \(X_{5}\), given that \(Y_{4}\), and knowing that \(X < Y\).

I first had the idea that if you could link the "subcomponents" of the current world state and the model that represents the current world state.

This seems a generally useful tool: It allows you to not only detect that your world state is erronious, but also where exactly the error is. The error must be related to the concrete variable change we made.

E.g. doing the above with most variables of the world could leave the model and the world in sync after applying the respective update functions. But for one variable there is a mistake. We now narrowed down the possible errors to (non-comphrehensive):

• This specific substate is not a faithful represenation.
• The update function does not update this particular substate currectly.

Before we could maybe detect that the model and the actual world state are out of sync. But now we can detect what specific sub parts are out of sync.

This seems especially useful for updating e.g. a lisp programs which is not differentiable, that describes the update rule in our model.

As the first step I created a high level formalism. Green underline means that a term is not rigourously defined. As a first, I tried to avoid formalizing these intentianally to be able to move faster. This worked very well.

Note that you could also frame it as inspecting the list of actions that you know how to perform, then selection the action that you predict will change (or sequence of actions), the attribute of the world that you want to verify, is correctly modeled in your model of the world. Note how this takes into account more information. You could be wrong about how an action changes the world, and if it is, this experiment might also raise an alarm.

The main idea here is that given that The Epistemics of Sensory Observations is true, then we can verify higher level abstractions by comparing them with the lower ones.

The above basically outlines a system architecture and desiderata on the components of the architecture.

The next step was to identify and describe the concrete errors could show up in the various components.

In my journal I then proceded to analyse how given the assumption that the model is perfect except for one small error in only one of the components I would be able to use the other components to detect and correct this error. (The below contains all red journal entries wich also contain additional thoughts).

I also noticed that to fix same function like G, D, or P, even in this idealized scenario, I don't know how able to fix it, if they where anything complicated. I therefore thought about how we might do a special kind of program inference. Specifiaclyl how to update an almost correct program, which is very different from solomonoff induction.

I also thoughts how logic programming might help with this program search.

In retrospect I might have spend to much time thinking about how to update a program. Focusing on understanding the high level details of the model, especially the link function, seem better. I would like to first have a good understanding of how to detect and correct errors, and probably have a small toy implementation where functions like G are just maps.

That again feels like it would be too easy, but emperiaclly talking to the machine spirit very good.

I realized that there is something very fundamental about the structure of having a language and an interpreter:

I ask what kind of structure the update function (of the world state) in our world model could have. Maybe there is something that is not source code? I was unable to come up with anything that seemed qualitatively different from the language interpreter structure. Of cause ultimately we'd like our world program to not be arbitrary source code. But it will still be source code of a form (given the definition above). It seems like there isn't an alternative.

This gives me confidence that tackeling the problem of arbitrary program inference is the rigth direction. The core challenge is to figure out how to do it at all efficiently. Once that is figured out, we can focus on crafting a carefully constrained language. This seems good because in a sense I realized that there is basically nothing else to do. The world model update function must take the form of a language and an interpreter (there might be equivalent isomorphic framings).

In summary: Solving program inference is the right direction, because parts of the world model must be expressed as a program. In some form we need to solve this problem.

Now that we are talking about program inference we need to be very careful, with what program we are talking about in a given context. We have:

1. Programs making up the description of the world. E.g an update function .
2. Programs that infer programs of type . E.g. let be the procedure that updates based on new sensory observation, if mispredicts the actually occuring sensory input.
3. Programs constructing programs of type . E.g. SGD is a general optimization procedure that we use in combination to neural networks to "find minds".

We want to avoid constructing a system that uses programs of type 3. We want to figure out how to create an understandable program of type 2. We current don't need to prioritize making programs of type 1 interetable. The bottleneck is figuring out how to do anything at all.

If your system is competent it's dangerous.

somehow I haden't internalized this appropriately before. I think I have often in the past fallen into the trap of arguing that a particular algorithm would be save, or have good properties, based on some condition. And usually I failed to consider this basic point, that if it actually worked, it would be dangerous.

It dosn't matter what kind of high level argument I am making for how this could make the system save, or more save. If the system actually works it will kill you, untill you can give a very precise technical argument for why it won't. And I never had such an argument.

I expect the only way we will be able to give such rigorous arguments, is by really understanding the details of how the system works that we are buliding.

Also consider that mechanistic interpretability is really about doing a kind of program inference, where we start with a spagetty program, and try to tidy it up. This is even more evidence that program inference is good. One version of program inference is about infering a nice program that describes the behavior of a neural network. To extract it's algorithms in a nice format. Figuring out parts of the general program inference problem seems useful for that, and really if we could extract capabilities of NNs into a understandable format, we can use these as buliding blocks (with caution).

Put it seems probable enough that it is much easier to make a general program inferer/updater, that is understandable from scratch, that this would be good to try first.

I drew the above diagram. The nice thing about it is that it contains all the function, and objects that I want to talk about, and all the important information about how they relate to each other.

This diagram is similar than the predictive processing diagrams I made in the past. It seems easy to redraw and might serve as a useful visual representation of the setup in the future.

The relation to category breaks somewhat once we consider having a higher level abstract world model.

If we build a continuous NAND gate, then we can run SGD on a circuit of such continuous NAND gates to find the right circuit. The following shows a continuous NAND gate.

We want to make the loss such that gradient descent will converge onto parameter values such that the continuous nand gate can be transformed into using discrete NAND gates, because the parameters are exactly such for each continuous NAND gate X such that X behaves the same as a discrete one.

There seems to be something very elegant abotu baricentric coordinate. In a sense they encode the constraint that all values must sum to one. It feels like you could make an elegant optimization procedure, such that softmax would seem like a hack.

Here is a simple untested algorithm:

Here is an idea for a loss such that SGD would go to a corner in the simplex of the baricentric coordinate system.

How can we generate NAND circuits? If we have for each pair of NAND gates in the previous layer a NAND gate in the current layer, then we get an exponential explosion. Ideally we want a generic procedure that generates NAND gates that are as small as possible, while still containing the circuits that we are looking fore.

Here a general algorithm is presented for guiding a search process by specifying several intermediate values (they need not be ordered).

It would be great if our NAND circuits where convex. Then we could use fast convex optimization algorithms.

We have implemented the simple 2 point MC convexity test algorithm in the NAND gate project repo.

The basic NAND gate is convex. The continuous NAND gate is non convex. Somehow the convexity test said that the loss is convex but this seems very strange and probably wrong. We did not try to understand what is going on here.

The current implementation of the NAND circuits doesn't work. It is likely because the optimization get's stuck at a local minima. But we have not confirmed this!

Usually it's very good to understand why something doesn't work. However, here we are shelving this project, because we noticed that we failed at doing research by not carefully reasoning through the problem. See the notes on Research as a Stochhastic Decision Process, for the reasoning of how we failed.

Let's generate code that satisfies some specification. Then let's make the code slightly wrong. The goal is to generate concrete examples of programs that are only slightly wrong.

We want to use these programs for designing an algorithm that can detect and fix these small mistakes.

One important technique for program search might be to define some algebraic structure on the code that you are searching for, to enable certain kinds of mechanical reasoning about the programs. Things that seem relevant here is functional level programming (John Backus, the J programming).

{:formal-language X :interpreter Y} seems an important object. But we don't even have a name for it. We need to better understand program search.

Some parts of the world model needs to be expressed in a code, that will run by some interpreter. E.g. the update function. The code captures a pattern, that is then dynamically unrolled.

To figure out how to generate this part of the world model we need some form of program search. What else could it be?

Now we are at the point where we don't have good models that would tell us what to do next.

In Program Search is the Core we argued that really program search is the core thing that we need to figure out to understand world models. This might be true. But we jumped the gun. There are many things we do not understand about world models that seem very important to figure out. We basically failed to think hard and long enough at the right level of abstraction and instead just tried to solve some problem.

E.g. in Back to the basics of World Models we partially cash roam:Factored%20World%20Models, a thing we knew about for over a year, in the context of the update function of a world model. They seem very powerful and helpful for future work on program search.

How can we build a model here? Well consider that there would be some structure in the world.

If we had all these observations that highlight a specific part of the update function that is independent of other parts of the update function we'd have a factored update function, that even when implemented inefficiently (e.g. with a lookup table), can represent many world states.

But with the method outlined in name:WBB:C.41

Now the next step is to make the setup more concrete. I ended up choosing cellular automata for this.

Specifically starting by looking at the game of life. First I tried to make a puzzle setup:

Then I tried to manually find the rules for the game of life based on some observation I am making according to this puzzle setup:

Then I tried to turn the procudure that I executed into a bullet argorithm:

One nice thing about the setup so far is that it should be pretty straightforward to implement it. I immediately thought about how to do it for n-dimensions.

I then started to implement it using core.matrix in clojure.

After I had already started to implement a cellular automata simulator, I noticed that it was pretty fun, and that I didn't want to reflect about whether it is actually the best thing to do:

This is very different from evolutionary algorithms which progresses by generating random things and then pfiltering aeftrwards

Even if for every thing that moves, it is not in a contiguous region, but a single index, it's still not super slow in some sense, because you can write an algorithm programmatically that corresponds to skipping exactly these indices, and that would be expensive once, but afterwards would be cheap, and probably cheaper than creating a new array with the moving things filtered.

• The example was very useful.
  • The example is very simple, and not something that seems natural to think of when thinking about human cognition (which is what I started with).
  • We identified an important algorithm and then tried to figure it out in concrete details.
• Examples are hard to come up with
  • When having an abstract concept like "humans generate not extremely dumb things" it's unnatural by default to think "that is like accessing an array via procedure than implicitly filters by not generating certain indicies". That's a big step to take. You need to move closer gradually such that you can have this idea. E.g. by first thinking about where in computer science things are generated "Ah iterators".
  • Seems trainable.
• Johannes often fail by compartementalization. E.g. I didn't realize that game dev is useful until now for research.
  • Compartementalization might prevent you coming up with good examples.
• Eliezers thinks of brains as engines that do computations.

Gustaf ask "what is the maximum landing speed to not crash". This is a very important parameter that when you figure it out, helps you play the game well (you can use less fuel). It would be good if we had an algorithm that can when modeling the game, ask and answer such questions.

Gustaf noticed that there must be a rule that determines what velocity makes you explode. Implicit assumptions:

• In the situation where
  • The floor is even
  • I have no horizontal velocity
  • You are looking straight down
• You can die or not die based on your vertical velocity.

The Bucketing post

Bucketing was the strategy used by Julia to think better about exfohazards.

Bucketing is about how to orginize knoledege such that you can run fast local "chash out the truth" on variable change. Having different buckets allows you to not run the automatic truth persation algorithm.

Bucketing is about disabling the automatic update and taking manual control over the inference.

In the above we initially have one bucked. One thing in there is ""

What I am trying to do is get a model of the world such that we can think it terms of what is going on it terms of the world model. Similarly to how you can easily tell deep blue to never take a knight.

What I mean with understand the AI is that we build is that we have a very good gears level model of the internal mechanisms that make the system reason.

Understanding means that if the system would kill you you ALWAYS will be able to have "the intuition" that it will kill you.

Language is tightly related to world models. Studying language might reaval more about how humans.

One important thing I just thought in relation to understanding language to understand intelligence is that language is like serializing your world model, such that you can communicate it to others. However, a computer mind does not have this problem, as they can just exchange data-structures directly. So avoid spending lot's of time figuring out language features that are not neccesary for artificial minds.

We want to seperate between the presentation and the information of a language. A language might have subjects, verbs, and objects. That is about what information a language can represent. In what order subject, object and verb are put in a sence is about presentation. The choice is a mere convention. You need to put them into some order. But the order doesn't change what can be expressed in the language.

Lisp is special because it has a quoting mechanism. This facilitates treating source code as a first class citicen. A pice of code can be quoted such that it returns a datastructure that represents the code (a nested list).

Another interesting feature of Clojure in particular is that there are 3 objects the language allows us to talk about:

• Symbols (e.g. inc (or 'inc in source code))
• Vars (e.g. inc is a symbol pointing to the Var that has the inc function)
• The result of using the function (e.g. (inc 4))

There are different types of quotes in language:

• Banana is yellow - This translates to an assesment about the world.
• Bob belives "Banana is yellow" - We say that somebody made an assesment about the world.
• The following characters are written on the page 'Banana is yellow' - We don't evaluate the statement 'Banana is yellow', but we are talking about the characters that evaluate to something. This most closely matches lisp's quoting.

Hypothesis: Instead of saying "Bob plays. He likes it." we can say "Bob plays. Bob likes it." This also works for unknown people/objects. "Maybe a stone fell down. It was probably large." We can say "Maybe a stone fell down. That Stone was probably large." So we don't need any inderect refference words.

There are 2 basic constructs in language. Facts, Procedures, and exclamations.

Assertions:

• Bananas are yellow.
• Bananas are tasty.

Procedures:

• Instructions for eating a banana.
  1. Obtain the banana.
  2. Grab the strunk and pull backwards.
  3. Grap other pices of the banana still at the top.
  4. Put the banana in your mouth.
  5. Chew

Exclamantions/Sounds:

• Ahhhhhhhhhhhhh.

Facts are either true, false, or nonsensical, e.g. I jump a bread.

Procedures aren't true or false. However they can be impossible to execute. We can also make assertions about procedures.

There are a bunch of modifiers that can be added ontop of facts.

Modifiers

• Questions - Any Fact can be turned into a question. If A is a fact it's about asking what is the value of x in eval(A) = x. A question asks what a formula evaluates true.
• Assertions - Any Fact can be asserted to be true. We generate a new fact. E.g. "bananas are yellow" in natural language, translates to "eval(bananas are yellow) = true". So in english a sentence is interpreted by default as an assertion.

Imagine your goal is to write functions in a programming language that are generally useful for programming. Here we define what function \(f\) would, if we could use it “for free” (i.e. using it doesn't count towards the compelxity of the overall program), would make all other programs maximally shorter to write. Making programs shorter to write seems like good proxy for being generally useful.

Let lang-basic be a base programming language. The basic programming language does not have any functions defined. Let (defun all-programs (lang) ...) be the set of all source codes that are valid programs in lang. Let a function definition be (defun make-function-definition (name args body) (list name args body)) and (def f-def (make-function-definition ...) be a function definition. Let (defun extend (lang f-def) ...) be a function to extend a language lang with a function definition f-def, i.e. the NAME of f-def can appear in a program prog but the implementation of f-def doesn't count towards the kolmogorov complexity of prog.

(defun smallest-program-with-same-behavior (program)
  (argmin (p in (filter (fn [p]
                          (functionally-equivalent p program))
                        programs))
          (< (len p) (len program))

This is a Kolmogorov compressor that finds the smallest program that is functionally equivalent to program.

We can now define a function that finds what function if added to a language lang would make all programs maximally shorter to write:

(defun get-best-function-to-add (lang)
  (argmin (f in all-functions)
          (sum (map src-code-length
                    (set (map smallest-program-with-same-behavior
                              (extend lang f))))))

To build a library of functions that are generally useful for programming we repeatedly call this procedure.

(defun build-library (lang)
  (build-library (extend lang (get-best-function-to-add lang))))

• How can we efficiently find the best (or a very good) function to add to the library?
• How can we give the algorithm and “understanding” of when and how to use functions in the library?

Relevant notes start at headline 16.

Goal: Environment good for developing an algorithm that can create a model of an environment.

The environment is an infinite 2D grid of cells.

We have a cartesian agent .

The grid contains an avatar for . has actions UP DOWN LEFT RIGTH. partially observes the grid around the avatar. The avatar interacts with cells by walking next to cell.

It seems better to have a god game, i.e. you can from a cartesian perspective interact with the world. Intuitively this should make experimenting easier.

Cell Behaviors:

• RED - Cell disappers when interacted with
• RED/GREEN - Cell with two states. Red and green. Running into the cell changes the state.
  • Adjacent cells take the state of the neighboring state if changed.
• BLUE - Cell copies the cell East to North
• BROWN - Cell is “moved” back
• VIOLET - Position with avatar is swaped

The ground-truth-inference problem group about infering a lossless world model:

• Infer a datastructe that can losslessly describe any ground truth world state.
  • E.g. a directed graph can describe a FSA.
• Infer the ground truth transition function between world states.
• Infer the current world state from observation.

Any problem subset is a concrete problem, e.g. infer ground truth world state from knowing the transition function and world state datastructure.

If you are logically omnicient, you know the current world state, and the transition laws, you "know everything".

The efficient-model-derivation problem group is about creating an efficient world model from a lossless one:

• Submodels
  • efficiently model a limited problem domain, e.g. assuming a resistor has constant resistance.

• Abstraction

  an abstract model throws away or ignores information from the concrete model, but in such a way that we can still make reliable predictions about some aspects of the underlying system.
  – What is Abstraction? — LessWrong

• The Powder Toy is an open source particle simulation game (which might even be implemented as a cellular automata). It has the structure we want (you can predict the future, but interactions can be complex).
• There are 3⁽³³⁾ = 134,217,728 3-color nearest neighbor cellular automata (there are 27 match patterns (top part) and for each of them we need to choose a 3 color value to make a single rule). Basically a cellular automata ruleset can be described by a length 27 trit-string.
• Looking at the last plot here, we can notice that a serpiski triangle like structure appears in the randomness of rule 30.

High level Tasks

• Run Cellular automata search.
  • We need a cellular automata that exibits structure such that we can predict into the future, but such that this structure is not "trivial", like in a sirpinski triangle.
    • We probably want to search with different random initializations (not just a single cell initial state).

Concrete tasks:

• Look at trajectories with random initialisations (use seed) for all 255 elementary cellular automata.
  • Select the ones that have structure that propagates "straigt down" (instead of diagonally).
  • Implement rule in Gurkengla's visualizer and capture the structure interactively.
  • Analyse this structure and describe the patterns that appear.
• [STUB] Do a similar thing for Low K complexity high variability Rulesets