Basing a concrete definition of Kolmogorov complexity on the lambda calculus rather than Turing machines has many advantages. See https://en.wikipedia.org/wiki

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 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.