$S$-Expressions

Stephen Wolfram recently announced a challenge asking whether or not expressions using only $S$ combinators are capable of universal computation. A week ago, I wanted to investigate, so I wrote a visualization tool for $S$-expressions. Click on or below a node to apply the substitution rule. Click and drag to pan. The tool is pretty rudimentary. The starting expression is hard-coded. I’ve left it as $SSS(SS)SS$, the shortest non-terminating $S$-expression. It is also possible to include other letters in the expression to track variable combinators. For example, $Sxyz$ simplifies to $xz(yz)$.

I played around with it a bit, but I wasn’t able to produce or discover anything interesting.

---