Unlambda is an example of a Turing-complete programming language that implements your requirements.
- Its expressive power only requires three base terms,
s,kandi. They would be your base $B$. - It has an additional construct,
`, which represents function application. It would be your binary operator $(\cdot)$. - Unlambda has a few more built-ins but they are just here to make the programmer's life easier (although mentioning easy anywhere in the context of this language is probably an overstatement).
Natural numbers can be represented using Church's method, e.g. $3$ can be written as ``s``s`ksk``s``s`kski. Pretty simple, no? Recursion can be defined with the Y combinator, and from there the usual techniques can be applied to define more and more complex functions until an universal Turing machine has been simulated.
This language is based on SKI combinator calculus, which itself finds its source in Combinatory Logic. There is a simple mapping between the Lambda and SKI calculi, which luckily makes proving Turing completeness much easier than actually doing the work!