Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all the major applications of these structures that I can think of (for example, interpreting groups as symmetries, using Galois groups to classify extensions, semigroups to classify automata, etc.), and it is also the most basic hook one can use to get intuition about these structures. Of course the reason that these structures have non-trivial actions follows from the associativity axiom which leads to Cayley's theorem/Yoneda's lemma.
As a result, associativity is a necessary and sufficient condition for a binary algebraic structure to `act' like a collection of functional relations on some set (or between many sets in the case of categories). If one believes that functions are the end-all-be-all of mathematics, then the story is over and the situation is hopeless. However, I believe (perhaps naively) that functions are just one kind of relation -- granted a very important one! -- and that there are many other useful things out there.
One alternate picture of magmas that I find quite amusing, is to think of them as forests of binary trees with labelled leaves, together with some rewriting rules that can be applied to subtrees. This type of structure shows up quite frequently in programming languages (for example when implementing an interpreter). As a result, I wonder if there is some canonical way to think of a magma as something like a Turing complete language.
As an example, it is easy to translate the lambda calculus into a magma; let $\Sigma = ${$ x_0, x_1, ... x_n $} be a collection of variables and let $\lambda \Sigma = ${$ \lambda x_0 , .... \lambda x_n $} be a second collection of distinct symbols denoting name binding. Then a lambda expression is determined by the free magma generated by $\Sigma$, $\lambda \Sigma$ subject to the relations:
$(\lambda x_i M) N = M [ x_i \mapsto N ]$
Where the $[ x_i \mapsto N ]$ denotes the capture avoiding subsitution rule.
Now this tells something about how a magma interacts with itself (specifically that it can do pretty much anything it wants), but what I am searching for is some way to interpret a magma interacting with some external set. Is there a general mechanism that would allow one to think of a magma as a relation with some extra structure in the same sense that a semigroup is like a transitive relation, a monoid like a preorder and a group like an equivalence relation?
