Ciro Santilli @cirosantilli  40

The for loop is a subcase of the while loop.

One theoretical motivation for its existence is that it has the fundamental property that we are immediately certain it will terminate, unlike while loops with arbitrary conditions.

Primitive recursive functions are the complexity class that divides those two.

In intuitive terms it consists of all integer functions, possibly with multiple input arguments, that can be written only with a sequence of:and such that n does not change inside the loop body, i.e. no while loops with arbitrary conditions.

n does not have to be a constant, it may come from previous calculations. But it must not change inside the loop body.

Primitive recursive functions basically include every integer function that comes up in practice. Primitive recursive functions can have huge complexity, and it strictly contains EXPTIME. As such, they mostly only come up in foundation of mathematics contexts.

The cool thing about primitive recursive functions is that the number of iterations is always bound, so we are certain that they terminate and are therefore computable.

This also means that there are necessarily functions which are not primitive recursive, as we know that there must exist uncomputable functions, e.g. the busy beaver function.

Adding unbounded while loops of course enables us to simulate arbitrary Turing machines, and therefore increases the complexity class.

More finely, there are non-primitive total recursive functions, e.g. most famously the Ackermann function.

AGI-complete in general? Obviously. But still, a lot can be done. See e.g.:

Short for Doctor of Philosophy, it's how some weird places like the University of Oxford say PhD. In Oxford they also analogously say MPHil.

Described at: arxiv.org/pdf/2107.12475.pdf where a relation to the Busy beaver scale is proven, and the intuitive relation to the Collatz conjecture described. Perhaps more directly: demonstrations.wolfram.com/CollatzSequenceComputedByATuringMachine/

One of the most beautiful things is how they paywall even public domain works. E.g. here: www.nature.com/articles/119558a0 was published in 1927, and is therefore in the public domain as of 2023. But it is of course just paywalled as usual throughout 2023. There is zero incentive for them to open anything up.