Is there a non self-referencing non-computable function? I've seen in college that some functions are not computable. 
The proof for that was the case of Halt(x,y) function.
The thing is, the proof used a very artificial (IMHO) case 
which is evaluating the function in it's own program number.
In fact the whole idea of the Halt function is quite self-referencial...
I'd like to know if there is a more "normal" function which
cannot be computed.
Can someone show me a function which is non-computable but
does not refer to itself?
I hope I made myself clear... if not, just comment and I'll explain.
Thanks!
 A: I don't have a specific example, but here's a way to think about it.  Virtually all functions are not computable--there are uncountably many functions, but only countably many are computable.  Nevertheless, it may be hard to give a specific example of a non-computable function that doesn't seem a bit contrived.  You could think of this as analogous to the fact that it's very hard to actually prove that any particular number is transcendental, even though almost all are.
A: There are tons of uncomputable functions. Example: given a polynomial $p(x\_1,\ldots,x\_n)$ with integer coefficients, are there integers $a\_1,\ldots,a\_n$ such that $p(a\_1,\ldots,a\_n) = 0$? Undecidable.
Given a bunch of polygonal tiles, can you tile the plane with them without gaps or overlaps? Undecidable. 
Wikipedia has a nice list of undecidable problems: List of undecidable problems. 
A: There are many undecidable problems that come up in practice, see Darsh's answer. However, as far as I know, all of them are shown to be undecidable by showing they could be used to solve the halting problem, and vice versa. So, in that sense, they are all the same problem. 
There are undecidable problems that are weaker than halting, but I don't know of any which occur naturally.
A: Depending on the intended meaning, your question can be reformulated as whether for all non-computable function f, ability to compute f implies ability to compute Halt. This is a famous Post's problem in recursion theory. It turns out that answer is that there are uncomputable functions that are 'weaker than' Halt. In general, the relation between functions, as which can be used to computed which  other leads to a partial order, called the order of Turing degrees, which are equivalence classes of 'equally hard to compute' functions.
A: Strictly speaking, one can say that most functions are uncomputable. There are uncountably many functions and only countably many Turing machines to compute the functions.
So here's an example: Pick a random real number $\alpha \in (0, 1)$, and ask that $f(n)$ return the $n$th bit of $\alpha$. With probability $1$ this is uncomputable, but there's no obvious way that this is "self-referencing."
(By the way, I'm cheating just a little bit here, since the proof that there are uncountably many reals relies on essentially the same trick -- diagonalization -- as the self-referencing non-computable functions proofs. But it's only a little bit.)
A: Here is a good example. Call a number n random if no program of length < log(n) exists that outputs n on input 0. (This can be more formally defined using Turing machines). Random numbers are also called Kolmogorov random. The characteristic function, call it R, of all random numbers is not computable. By the way, the Halting function H(x,y), you mentioned, is, in certain precise sense, equivalent to the function R. That is H and R are in the same Turing degree. 
A: A nice example for a function that fits your description (I think), is the Busy-Beaver function. The definition is rather natural (at least for an uncomputable function) and the uncomputability proof is not using any "tricks". See the Wikipedia entry (http://en.wikipedia.org/wiki/Busy_beaver) for details.
A: Check this blog post.
A: If your question is "Are there uncomputable functions which cannot compute Halt?" then the answer is yes. If you take all functions from ℕ to ℕ, "can compute each other" is a natural equivalence relation, and the equivalence classes are called Turing degrees. The computable functions form the minimal degree, 0. The Turing degree of Halt is called 0', pronounced zero jump. (For any degree A, the degree of Halt with A as an oracle is written A'). There are lots of degrees which are strictly between 0 and 0'.
The question as phrased, suggests that logic constructions are unnatural or abnormal. This attitude is flatly wrong. Offhandedly rejecting such arguments is as quackish as claiming the real numbers are "morally countable". Computation, definability, and diagonalization are embedded deeply in a wide range of mathematical systems. (See Hilbert's 10th Problem or Gödel's Second Incompleteness Theorem) 20th century logic is a reality of mathematics.
