[Unlambda](http://en.wikipedia.org/wiki/Unlambda) is an example of a Turing-complete programming language that implements your requirements.

- Its expressive power only requires three *base* terms, `s`, `k` and `i`. 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](http://en.wikipedia.org/wiki/SKI_combinator_calculus), which itself finds its source in [Combinatory Logic](http://en.wikipedia.org/wiki/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!