Basing a concrete definition of Kolmogorov complexity on the lambda calculus rather than Turing machines has many advantages.

See https://en.wikipedia.org/wiki/Binary_lambda_calculus for a concrete definition, and a proof that the complexity of the prime numbers is at most 167 bits.

This language can be implemented in only 25 lines of C.