Which calculus is based on first-order functions and is Turing complete?
There are many, but I think the most famous one µ-recursive functions. It describes functions from $\mathbb{N}^{(\mathbb{N})}$ to $\mathbb{N}$, i.e. from tuples of naturals to naturals. This can be transformed into a theory of functions from $\mathbb{N}$ to $\mathbb{N}$ by composing with an encoding of tuples; I think the reason it isn't commonly presented that way is that it doesn't look neat.

µ-recursive functions are defined as follows:


All constant functions are µ-recursive.
The successor function ($S(n) = n+1$) is µ-recursive.
Projections ($\pi_i(n_1,\ldots,n_k) = n_i$) are µ-recursive.
Composition: if the $f_i$ and $g$ are µ-recursive then $(n_1,\ldots,n_{k_1+\ldots+k_m}) \mapsto g(f_1(n_1,\ldots,n_{k_1}), \ldots, f_m(n_{k_1+\ldots+k_{m-1}+1},\ldots,n_{k_1+\ldots+k_m}))$ is µ-recursive.
Primitive recursion: if $f$ and $g$ are µ-recursive then the function $h$ defined by $h(0,n_1,\ldots,n_k) = g(n_1,\ldots,n_k)$ and $h(n+1,n_1,\ldots,n_k) = f(n,n_1,\ldots,n_k,h(n,n_1,\ldots,n_k))$ is µ-recursive.
Minimisation: if $f$ is µ-recursive then so is the function that maps $n_1,\ldots,n_k$ to the smallest $x$ such that $f(n_1,\ldots,n_k,x) = 0$.


Note that in the definition of the minimisation operator, it is possible for $x$ not to exist. In this case the resulting function is partial. This calculus thus defines partial recursive functions.

If you restrict the calculus to total functions, you get the recursive functions, with the same computing power as Turing machines.

The minimisation operator is usually written $\mu$ and gives the calculus its name. If you omit it, the resulting set of functions are exactly the primitive recursive functions (indeed that's a convenient way to define them).