{α → β

I came across an English translation of A. A. Markov's "Theory of Algorithms." In this work Markov introduces Markov algorithms, a basic grammar for string rewriting rules. 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. Give it a try below

Example progam 
# define two-element sort 
# algorithm over a length-2
# abstract alphabet. 
sort::[2]{
    # name : rule : emission
    # -> for pure and ~> for impure
    # -. and ~. for terminal
    
    swap : ba ~> ab : "~p[~m]~s";
    done : ab ~. : "[~]"
}

# define a concrete alphabet
squares = {□, ■}

# define bindings between the 
# abstract and concrete alphabets 
bind1 = sort :> squares

# custom bind rules 
bind2 = sort :[a:■, b:□]> squares

# Call sort on stdin 
# with each binding
sort::bind1(~)
sort::bind2(~)

Input 

    
    
    
    


    
    
    


    Output
    

    

    

    WASM S-Statements