Ben Mickler BenjaminMickler

Solving SAT via interaction net superpositions

I've recently been amazed, if not mind-blown, by how a very simple, "one-line" SAT solver on Interaction Nets can outperform brute-force by orders of magnitude by exploiting "superposed booleans" and optimal evaluation of λ-expressions. In this brief note, I'll provide some background for you to understand how this works, and then I'll present a simple code you can run in your own computer to observe and replicate this effect. Note this is a new observation, so I know little about how this algorithm behaves asymptotically, but I find it quite

Notes on the Railway Model of Computation

From A universal cellular automaton in the hyperbolic plane.

Switches

A switch is a point from which a track splits. So it starts with one track, and ends with two.

You can go in two directions on the switch:

Type C	Call method	Go type	Bytes (byte)	Numerical range
char	C.char	byte	1	-128~127
signed char	C.schar	int8	1	-128~127
unsigned char	C.uchar	uint8	1	0~255
short int	C.short	int16	2	-32768~32767
short unsigned int	C.ushort	uint16	2	0~65535
int	C.int	int	4	-2147483648~2147483647
unsigned int	C.uint	uint32	4	0~4294967295
long int	C.long	int32 or int64	4	-2147483648~2147483647

ANSI Escape Sequences

Standard escape codes are prefixed with Escape:

Ctrl-Key: ^[
Octal: \033
Unicode: \u001b
Hexadecimal: \x1B
Decimal: 27

	#define QUEUE_SIZE 16

	int main(int argc, char** argv) {
	queue_t example = {0, 0, QUEUE_SIZE, malloc(sizeof(void) QUEUE_SIZE)};

	// Write until queue is full
	for (int i=0; i<QUEUE_SIZE; i++) {
	int res = queue_write(&example, (void*)(i+1));
	assert((i == QUEUE_SIZE - 1) ? res == -1: res == 0);
	}

	//
	// Simple listener.c program for UDP multicast
	//
	// Adapted from:
	// http://ntrg.cs.tcd.ie/undergrad/4ba2/multicast/antony/example.html
	//
	// Changes:
	// * Compiles for Windows as well as Linux
	// * Takes the port and group on the command line
	//

	struct Keycode {

	// Layout-independent Keys
	// eg.These key codes are always the same key on all layouts.
	static let returnKey : UInt16 = 0x24
	static let enter : UInt16 = 0x4C
	static let tab : UInt16 = 0x30
	static let space : UInt16 = 0x31
	static let delete : UInt16 = 0x33
	static let escape : UInt16 = 0x35

	var socket = null;

	function bootstrap() {

	// 適当な図形を描画
	var c = document.getElementById('mycanvas');
	var ctx = c.getContext('2d');
	ctx.globalalpha = 0.3;
	for(var i=0; i<1000; i++) {
	ctx.beginPath();