Can every decision algorithm be expressed as a first order predicate? Suppose we have a decision algorithm over, let's say, the set of natural numbers. Can this algorithm always be expressed as a first order predicate A(x) over the natural numbers, using only the language of natural numbers? in a way such that the algorithm will return true with input x if and only if A(x) is true?
Here i'm assuming that my decision algorithm is indeed computable (it never goes on forever)
For example: The algorithm which checks whether a number is even could be expressed as $A(x) \equiv (\exists y)(y+y = x)$ 
 A: There are at least two ways to give a positive answer to the question. The first uses the concept of a universal Turing machine to make a single formula that can handle every computable function. The second makes a different formula for each computable function, based on how the function is built from simpler functions.
First method: universal Turing machines
Recall that every computable algorithm can be implemented on a universal Turing machine, by specifying the correct program to the machine as an additional input.
Therefore, it would be sufficient to create a formula in the language of arithmetic that encodes a universal Turing machine. This was first done by Kleene in the mid-20th century, and a formula of this kind is now usually called the T predicate.
Using Kleene's T predicate, we can represent any computable function as a formula in the language of the natural numbers, and ask about whether the function halts and about the value of the function.
Actually, there are two predicates, $T$ and $U$. For simplicity, we will deal with one-variable computable functions. Then $T(e,n,s)$ holds if and only if $s$ is a code for the complete execution history of program $e$ running on input $n$, such that the program halts at the last step in $s$. Here $s$ encodes the complete sequence of computational steps that program $e$ takes when run with input $n$, so checking that $s$ is correct just requires checking that each step is correctly obtained from the previous one according to the program $e$. The $T$ predicate is represented as a first-order formula of the natural numbers. 
The $U$ predicate is used to decode the output of the function. If $T(e,n,s)$ is true, then $U(s,n)$ holds if and only if $n$ is the value that was returned by the algorithm when it halted.  This value can be found, intuitively, by simply decoding $s$. The $U$ predicate is also expressed as a formula in the language of arithmetic.
So, let $f$ be a computable function with program $e$. It we want a formula $A(n,x)$ that is true if and only if $f(n) = x$, as in the question, we can take
$$
A(n,x) \equiv (\forall s)[ T(e,n,s) \to U(s,n)]
$$
or (equivalently)
$$
A(n,x) \equiv (\exists s)[T(e,n,s) \land U(s,n)].
$$
Second method: representing one function at a time
There is another way to represent computable functions in the language of arithmetic, which is more commonly used in settings like the incompleteness theorems. This method uses a different characterization of computable functions: they are exactly the $\mu$ recursive functions. This is the smallest class of functions which contains a few basic functions and is closed under composition, primitive recursion, and the $\mu$ operator.
We can show easily that all the basic functions are definable by formulas of arithmetic. It is also not hard to show that the class of functions definable in arithmetic is closed under composition and $\mu$ recursion. To show that the class of functions definable in arithmetic is closed under primitive recursion, we use the fact that this language is able to quantify over and handle finite sequences, and then use course-of-values recursion. In the end, we find that the class of functions that are definable in arithmetic contains the basic functions and is closed under composition, primitive recursion, and the $\mu$ operator. So this class contains all the computable functions (it actually contains many more functions, as well). 
The difference between this approach and the $T$ predicate approach is that this second approach makes very different formulas for different computable functions. The $T$ predicate uses a single formula with a parameter $e$ for the program; the formula itself is set once and for all. The second method has no such parameter, and the defining formula itself is changed to reflect each new computable function. 
