Bounded computation and incompleteness
It depends on what you mean by "encode computation". There are many papers on the topic, a good starting reference is "Metamathematics of First Order Logic" by Petr Hajek and Pavel Pudlak. Pavel defined what is called sequential theory for theories where you can encode strings (I don't see if being a computation or not means much).

P vs. NP can be studied for other structures, first order logic with order is sufficient to phrase the question whether every $\Sigma^b_1$ formula is equivalent to a quantifier-free one (and you can enrich the language to contain all operations that you want to assume to be efficient). The strings case is old (I will add reference later). It is also studied over real numbers (in the context of BSS model). 

The question can be studied over structures without order, see the work on algebraic complexity like Valiant's VP vs. VNP and also GCT (for complex numbers and other fields).