{α → β

Recently I came across an English translation of A. A. Markov's "Theory of Algorithms." In this work Markov introduces Markov algorithms that are similar to Turing machines and while at first glance might look like Markov chains, are quite different. Markov algorithms are used to study certain branches of constructivist mathematics, among other things. Due to several different factors they never found prominence in western math and computer science.

In this work I am hoping to make Markov algorithms more accessible. This is largely motivated by personal interest, but also due to the fact that I can't really find an easily accessible copy of this text. Springer sells a new translation of this text, but I haven't looked at it yet. I did locate a Russian copy online, but that is pretty much it.

I am intending to transcribe large parts of this text and include a compiler for executing evaluating the statements in the text itself. The compiler will be embedded into the browser as a WebAssembly object and will allow the reader to compile statements from the text into WebAssembly and run them in real time.

The repo for this project builds both native and wasm versions of the code. GitHub CI/CD plops the latest build of it here. As such, it may be broken from time to time. The current version generates very basic WebAssembly text format (WAT) S-Statements. Give it a try below.

Example statements 
squares = {□, ■}.
swap::squares (w) {
    □■ -> ■□;
    ■□ -.
}



WASM S-Statements 

    

    While it may not look like much right now, there is a lot going on behind the scenes to
    achieve this. The Emscripten WASM compiler emits a .wasm binary format and a .js runtime 
    framework. The runtime framework loads the binary, which takes the above text as an 
    argument and compiles it into the above text. Encouragingly this seems to work on every
    browser I have been able to test it on including mobile browsers.