Ciro Santilli @cirosantilli 37

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

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.

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.

Term invented by Ciro Santilli to refer to problems that can only be solved once we have AGI.

It is somewhat of a flawed analogy to NP-complete.

There is no fundamental difference between them, a quantum algorithm is a quantum circuit, which can be seen as a super complicated quantum gate.

Perhaps the greats practical difference is that algorithms tend to be defined for an arbitrary number of N qubits, i.e. as a function for that each N produces a specific quantum circuit with N qubits solving the problem. Most named gates on the other hand have fixed small sizes.

Metric created by IonQ.