Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
I have no idea what you mean by "artificial" here, but I'll attempt to answer this anyway...(below) –  Darsh Ranjan Nov 8 '09 at 4:23
    
I also don't see what you mean by artificial. It is very reasonable to ask how to detect infinite loops in programs, just as some systems detect other kinds of bugs such as uninitialized variables, array out of bounds, etc. –  David Eppstein Nov 8 '09 at 9:09
    
I'm sorry for my lack of appropriate language. With "artificial", I intended meaning that OK, it's true that Halt is not computable because if a program existed that computed it, and you evaluated it on its own program number, a contradiction would occur, but this seems a very special and self-referencing case. I mean, it's not a case were one would usually use Halt if it were computable. In fact (I may be wrong here, please correct me), Halt(x,y) function should be computable for many values of x and y... –  Manuel Nov 9 '09 at 3:28
    
I tend to see this self-referencing problem in every non-computable function I know, and wondered if a more "mundane" function existed that satisfied this awesome property of being beyond computers' reach. –  Manuel Nov 9 '09 at 3:29
2  
It seems that your issue is not with properties of the functions themselves, but properties of the proofs of uncomputability, is that right? You keep wording your comments as referring to (e.g.) "mundane functions", but I cannot imagine a function more mundane than determining whether a polynomial has integer solutions. –  Reid Barton Nov 9 '09 at 5:40
add comment

9 Answers

up vote 13 down vote accepted

Check this blog post.

share|improve this answer
3  
This guy understood my question –  Manuel Nov 10 '09 at 13:59
5  
Correct me if I'm wrong, but that function is still proved uncomputable by (eventual) reduction to the halting problem. –  Darsh Ranjan Nov 13 '09 at 2:12
    
Most probably you are right. No points for me. (but, to nitpick, the reduction is from the halting problem, not to it) It's obvious that in any possible proof one has to use computability theory and show that the function is not equal to any of the computable ones. Diagonalization is the most natural way to do it. When this constitutes a "self-reference", it's hard to specify. –  sdcvvc Nov 14 '09 at 1:09
    
I wasn't implying that your answer isn't a good one; I think it's pretty great, actually! I just don't understand the criteria by which the OP is judging our responses. (And thanks for catching the error in my comment.) –  Darsh Ranjan Nov 15 '09 at 22:46
add comment

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.

share|improve this answer
    
For a bit more about Post's Problem (via the priority method) and its connections with Cohen forcing, see this MO post: mathoverflow.net/questions/124011/… –  Benjamin Dickman Jul 10 '13 at 11:16
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
2  
Yes, but as far as I can tell, the proof of undecidability for each of those still has the "this statement is false" core (sometimes hidden rather deeply). The question really was whether there are any other ways to prove undecidability than the liar's paradox. I'm not aware of any. –  fedja Nov 8 '09 at 4:35
1  
I like this example but if the comment above is true, it doesn't answer my question. :D Thanks for the info, though. –  Manuel Nov 9 '09 at 3:21
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
This has the same problem (IMO) that Halt(x,y) has... It is a function which refers to programs or Turing Machines to be described. In this sense, it is auto-referencial. btw: what do you mean by "H and R are in the same Turing degree." Please give a link if you don't want to explain in detail –  Manuel Nov 9 '09 at 3:18
    
See the link in Boris Bukh's comment –  Reid Barton Nov 9 '09 at 5:37
add comment

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.

share|improve this answer
3  
I would definitely call the BB function self referencing. It is equivalent to the halting problem in the sense mentioned by Boris. –  Ori Gurel-Gurevich Nov 8 '09 at 23:16
1  
I was going to answer the same thing. But, in fact, BB is an interesting function. The fastest growth, and all that... Thanks for the info! –  Manuel Nov 9 '09 at 3:19
add comment

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.)

share|improve this answer
    
I think the original poster wants a describable function. Talking about arbitrary functions is cheating in this sense. –  Ori Gurel-Gurevich Nov 8 '09 at 5:38
3  
If this question is about a function that is "describable" but not "computable" then I'm not going to be on the edge of my seat waiting for an answer ;-) –  Kevin Buzzard Nov 8 '09 at 8:17
    
@buzzard that was not the original question, but is it known to be impossible for a function to be describable and not-computable at the same time? –  Manuel Nov 9 '09 at 3:20
    
If you dare to give a formal definition of "describable" (like the formal definition of computable that already exists) then perhaps this question would have some formal meaning. But without it I'm tempted just to say "Church's thesis" and then run away. –  Kevin Buzzard Nov 9 '09 at 14:30
1  
Defining definablility rigorously is pretty hazardous, but there are plenty of functions that are obviously definable and not computable (just see the other replies). Definability is not the subject of Church's thesis; Church's thesis relates the familiar but somewhat vague concept of computability to the abstract notion of a recursive function. –  Darsh Ranjan Nov 17 '09 at 3:34
add comment

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.

share|improve this answer
3  
Dear Richard, though I agree that the theory of Turing degrees is best answer one can provide for this question, I do not think that justifies personal attacks. –  Boris Bukh Nov 16 '09 at 9:33
1  
Yeah, I agree: any accusation of "sounding like a crank" should be accompanied by a reference to one or more items from John Baez's crackpot index. That usually covers the egregious cases. –  Scott Morrison Nov 16 '09 at 17:04
2  
That's fair. I edited my answer. I was mostly upset at the way that question casually dismissed a lot of substantial mathematics. I should have been more careful to direct my ire at the question and not the questioner. –  Richard Dore Nov 17 '09 at 2:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.