The last claim demands a proof. Well, let me convince you with the rest of this blog post.

## LODA

LODA stands for Lexicographical Order Descent Assembly and is both a minimalistic programming language and a computational model. It consists of only four types of instructions (five if we count syntactic sugar). LODA programs operate on an unbounded sequence of memory registers $0, $1, $2, ... where each of them stores a natural number. The operands of instructions are either constants, direct memory accesses or indirect memory access. There are only two types of arithmetic operations: "add" and "sub". The latter is maybe not exactly what you would expect: since we allow only natural numbers, subtracting a larger value from a smaller value yields 0. Using these two operations, we can also define the assignment instruction "mov X,Y" which overrides the register X with the value of Y. It can be defined simply as "sub X,X" and "add X,Y".

The most interesting part is of course the model of loops in LODA. The language supports so-called "lexicographical order descent loops," which we write using the instructions "lpb X,Y" and "lpe". The interesting thing about these loops is that they are guaranteed to stop for every input and yet that they are more powerful than primitive recursion. This can be shown by implementing the Ackermann function with it.

A somewhat easier example of a LODA program for computing the Fibonacci numbers is shown below. If you are curious how this works and why the expressive power of LODA is "between" for-loops and while-loops, check out the documentation and cool C++ implementation at GitHub.