The standard complexity classes such as P, NP are usually defined using Turing Machines. In finite model theory those classes can be defined via the classical first-order/second-order logics.


I am curious whether there exists an equivalent definition of such classes via $\mu$-recursive functions. What about register machines? lambda calculus? etc? In computability theory it is known that $\mu$-recursive functions, counter machines, lambda calculus and Turing Machines are all equivalent. (<https://en.wikipedia.org/wiki/Computable_function>)



$\mu$-recursive definitions for the complexity classes P, NP, etc
Yes, there is. See [Cob64]. 
The idea is to replace primitive recursion 
in the definition of primitive recursive functions with bounded recursion on notion.


Another more delicate approach is taken in [BC92].


* Alan Cobham, "[The Intrinsic Computational Difficulty of Functions](http://dx.doi.org/10.1016/j.tcs.2003.10.017)", 1964
* Stephen Bellantoni and Stephen A. Cook, "[A New Recursion Theoretic Characterization of The Polytime Functions](http://www.cs.utoronto.ca/~sacook/homepage/ptime.pdf)", 1992


