CliqueVM is an experimental framework for building computational models, both classical and quantum mechanical, and tracing their multithreaded evolution as 2D/3D graphs. New models can be coded in JavaScript directly on the app by modifying the operator function that maps a clique of states into a new generation of states.
Run online: https://met4citizen.github.io/CliqueVM/
The purpose of the project is NOT to make an app for practical simulations, but to study the underlying concepts and ideas.
The app uses @hpcc-js/wasm for compiling Graphviz DOT language into SVG, 3d Force-Directed Graph for rendering 3D graphs and CodeMirror as a JavaScript editor.
The project is based on my two earlier projects Hypergraph and BigraphQM. For a philosophical take on these ideas read the blog post The Game of Algorithms.
All physical systems evolve over time. We can represent this with
a mathematical object called an operator that maps the state of the system
at time
Often the system has so many possible states that it is very hard or impossible to describe the operator. Fortunately, all physical interactions are, as far as we know, spacelike and local. This means that instead of acting on the full state of the system we can process smaller collections of microstates independently of each other. We call these collections cliques, because they show up as maximal cliques in our graphs.
For two programs to end up spacelike and local, their computational histories must be mutually consistent and they must compute the same function. More specifically, their lowest common ancestors (LCAs) must be operations, not states, and they have to belong to the same equivalence class of programs. Both of these properties are relative. If and when these pairwise relations change, we end up with not one but multiple threads that can branch, merge and run in parallel.
A multithreaded system, real or simulated, can be classical, quantum
mechanical, or some mix of the two, depending on the operator. The thing
that makes a system quantum mechanical is the existence of superpositions.
A quantum superposition is a situation in which some computational sequence
Once we know how to calculate these maximal cliques, we can use them as inputs to our operator function, iterate the process, and trace the system's multithreaded evolution with a pre-defined set of graph-based tools. All this can be done within the app.
CliqueVM is called a framework, because it allows us to define, among others, our own initial state, operator and equivalence relation. By using JavaScript's primitive types, such as numbers, strings, arrays and objects, we can construct hyperedges, vectors, complex numbers, matrices, coordinate systems etc. Using these data structures as states, it is possible, at least in theory, to build different types of rewriting systems, physical simulations and other computational models.
Let
At each new step, the latest set of maximal cliques,
In order to calculate the new generation of maximal cliques, we start from
the latest operator-generated states
Now, let
ALGORITHM BK(R, P, X) IS
IF P and X are both empty THEN
report R as a maximal clique
choose a pivot vertex u in P ⋃ X
FOR each vertex v in P \ N(u) DO
BK(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}
Once all the maximal cliques of all the disconnected subgraphs have been calculated, a new iteration (step) can be started.
If the operator is deterministic, the system, too, will be deterministic. However, if the operator generates more that one operation, even a deterministic system can become quantum mechanical. In these cases the evolution will appear probabilistic to any internal observer due to self-locating uncertainty.
Under self-locating uncertainty, an observation becomes a process in which the observer interacts locally in a way that resolves all the second-order inconsistencies (superpositions). These interactions make new shortcuts through the ancestral structure. This in turn prevents certain future interactions, which appears to the internal observer as a wave-function collapse.
From the internal observer's point of view, the proportion of all
the possible
Hamiltonian paths
that lead to the maximal clique
Note that from the external point of view - from "the point of nowhere" - all
the possible interactions get actualised without any randomness or
probabilities. In this context, often called the Many-Worlds
interpretation,
The framework offers the following graph-based views:
The previous or the next step can be calculated by clicking the arrows.
Reset
returns the model to its initial state. Cancel
aborts current
processing and cancel the job queue.
By clicking Model
, the user can specify his own model, deploy the model,
and export/import models as JSON strings.
A model is a set of JavaScript functions:
The INITIAL STATE
returns an array of initial states. A state can be
any valid JavaScript data structure. An example:
/**
/* @return {any[]} Array of initial states.
**/
return [1];
The OPERATOR
gets a maximal clique (array of states) as its input
and returns an array of operations so that each operation is an array of
output states. An example:
/**
* @param {any[]} c Clique, array of input states
* @return {any[][]} New operations with output states.
**/
let sum = c.reduce((a,b)=>a+b,0);
let state1 = (2*sum+3) % 10;
let state2 = (3*sum+1) % 7;
let operation1 = [ state1, state2 ];
return [ operation1 ];
The COORDINATE / EQUIVALENCE
gets a state as its input and returns its
coordinate label as a string. The coordinate label is used to test whether
two states are equivalent (local). This state equivalence could also be seen
as an observer-theoretic coarse-graining and/or encoding function. An example:
/**
* @param {any} s State
* @return {string} Spatial coordinate.
**/
return s.toString();
The DETECTORS
returns an array of coordinates to be monitored. Whenever some
detector state is visited at some step, its counter is increased. An example:
/**
* @return {string[]} Array of detector coordinates.
**/
return ['0','1','2','3','4'];
All functions get executed with the "use strict" directive.
NOTE: The JavaScript source code in the JSON string is used to
create a new Function
object inside a Web Worker. This means
that the code will have no DOM access and critical issues such as
infinite loops can be easily solved by terminating the worker (reset).
However, for security reasons, always check the model before importing!
In order to keep the functions short, the framework offers a simple API
(ModelAPI
class) with a set of commonly used utility functions and
generators. In the app these methods can be called with this
, for
example: this.id()
.
FUNCTION | DESCRIPTION |
---|---|
id() |
Returns a new unique number from [0,1,2,3...]. Reseting the model also resets the id counter. |
set(key,value) |
Set option. Currently supports the following keys: observer (1=quantum, 2=classic), maxcliquesperloc (number) and maxstatesperclique (number). |
get(key) |
Get option value. |
clone(x) |
Makes a deep copy of the given data structure. |
shuffle(arr) |
Shuffles an array in place using the Fisher-Yates shuffle. |
*comb(arr,[size]) |
Generates all combinations of a set. size is the length of the combination. An example:comb([a,b,c],2) -> [a,b] [a,c] [b,c] |
*perm(arr,[size]) |
Generates all permutations of a set. size is the length of the permutation. An example:perm([a,b,c],2) -> [a,b] [a,c] [b,a] [b,c] [c,a] [c,b] |
*cart(...sets) |
Generates the cartesian product of the given sets. An example:cart([a,b],[c,d,e]) -> [a,c] [a,d] [a,e] [b,c] [b,d] [b,e] |
BronKerbosch(V,N) |
Finds maximal cliques of the set V using the Bron-Kerbosch algorithm. N is a WeakMap of neighbours for each vertex. |
rewriteStr(s,rules) |
Rewrite string s with rules . Return all overlapping maximal results. For example:rewriteStr('BAA',[['BA','AB'],['A','C']]) -> ['BCC', 'ABC'] . |
TODO: Add utility functions for typical use cases such as graph and string rewriting.
Copy the JSON string below and import it to the app:
{
"init":"return [\"ABBABAA\"];",
"oper":"let a=/BA/gi,b=\"AB\",r,o=[];\nwhile( r=a.exec(c[0]) ) {\n let s = c[0].split(\"\");\n s.splice(r.index,b.length,b);\n o.push( [s.join(\"\")] );\n};\nreturn o;",
"coord":"return s;",
"detectors":"return [];"
}
Copy the JSON string below and import it to the app:
{
"init":"let v = this.id();\nreturn [[v,v],[v,v]];",
"oper":"let s = this.clone(c);\nthis.shuffle(s);\nif(s.length>=2){\n let v1=s[0][0],v2=s[0][1],v3=s[1][1],v4=this.id();\n s.splice(0,2,[v1,v2],[v1,v4],[v2,v4],[v3,v4]);\n}\nreturn [s];",
"coord":"return s[0].toString();",
"detectors":"return [];"
}
Copy the JSON string below and import it to the app:
{
"init":"return [{x:0,y:0,z:0},{x:0,y:0,z:0}];",
"oper":"let s=[],t=[];\nfor( let p of c ) {\n let [a,b]=this.clone([p,p]);\n let i=this.shuffle(['x','y','z'])[0];\n if (a[i]<3) a[i]++;\n if (b[i]>-3) b[i]--;\n s.push(a);\n t.push(b);\n}\nreturn [s,t];",
"coord":"return s.x+','+s.y+','+s.z;",
"detectors":"return Array.from({length:7},(_,i)=>i-3+',0,0');"
}
Jacob Yatsko explains Fibonacci modulus sequences in the following video
A New Way to Look at Fibonacci Numbers
The following is the same view turned into a 3-dimensional view. You can easily change the modulus in the editor and redeploy the updated code.
Copy the JSON string below and import it to the app:
{
"init":"return [[0,1]];",
"oper":"let s=[];\nfor( let p of c ) {\n let [a]=this.clone([p]);\n a[0] = a[1]\n a[1] = (p[0]+p[1]) % 10\n s.push(a);\n}\n\nreturn [s];",
"coord":"return s[1]+\"\"",
"detectors":"return ['0','1','2','3','4','5','6','7','8','9'];"
}
Experimental sequence where fibonacci modulus is converted to a complex with 1/2 0.5 real part and sequence as imaginary. Graph shows a recurring structures emerging.
Copy the JSON string below and import it to the app:
{
"init":"return [[0,1]];",
"oper":"let s=[];\nfor( let p of c ) {\n let [a]=this.clone([p]);\n a[0] = a[1]\n a[1] = (p[0]+p[1])%1050\n // console.log(a)\n s.push(a);\n}\n\nreturn [s];",
"coord":"function convert2Rectangle(polarReal, polarAngle){\n var real = Math.cos(polarAngle*Math.PI/180)*polarReal\n var imag = Math.sin(polarAngle*Math.PI/180)*polarReal\n var RectNumber = {'real':real,'imag':imag}\n return RectNumber\n}\n\nlet dis = convert2Rectangle(0.5,s[1])\n//return Math.round(dis.real)+\"x\"+Math.round(dis.imag)+\"\"\nreturn dis.real+\"x\"+dis.imag+\"\"",
"detectors":"return ['0','1','2','3','4','5','6','7','8','9'];"
}
Experimental combination of repeating fibonacci sequence with modulus 50 and the fibonacci sequence is inputed as mandelbrot pixel positions with height and width of 1000 pixels mandelbrot.
The fractality should emerge between the nodes of the mandelbrot pixel node 80 and the outside pixels nodes 1,2,3.
Copy the JSON string below and import it to the app:
{"init":"this.MAX_ITERATION = 80\nthis.REAL_SET = { start: -2, end: 1 }\nthis.IMAGINARY_SET = { start: -1, end: 1 }\n\nthis.mandelbrot = function mandelbrot(c) {\n let z = { x: 0, y: 0 }, n = 0, p, d;\n do {\n p = {\n x: Math.pow(z.x, 2) - Math.pow(z.y, 2),\n y: 2 * z.x * z.y\n }\n z = {\n x: p.x + c.x,\n y: p.y + c.y\n }\n d = Math.sqrt(Math.pow(z.x, 2) + Math.pow(z.y, 2))\n n += 1\n } while (d <= 2 && n < this.MAX_ITERATION)\n return [n, d <= 2]\n}\n\nreturn [[0,1]];","oper":"let s=[];\nfor( let p of c ) {\n let [a]=this.clone([p]);\n a[0] = a[1]\n a[1] = (p[0]+p[1]) % 500\n s.push(a);\n}\n\nreturn [s];","coord":"const WIDTH = 1000\nconst HEIGHT = 1000\nlet complex = {\n x: this.REAL_SET.start + (s[0]/WIDTH) * (this.REAL_SET.end - this.REAL_SET.start),\n y: this.IMAGINARY_SET.start + (s[1]/HEIGHT) * (this.IMAGINARY_SET.end - this.IMAGINARY_SET.start)\n }\nconsole.log(\"Mandel \", s,\" - \", complex, \" -> \", this.mandelbrot(complex))\nlet [mandel, isMandelbrotSet] = this.mandelbrot(complex)\n\nreturn mandel+\"\"","detectors":"return ['80','1','2','3','4','5','6','7','8','9'];"}