14
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I have no idea what you mean by "artificial" here, but I'll attempt to answer this anyway...(below) $\endgroup$
    – Darsh Ranjan
    Commented Nov 8, 2009 at 4:23
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Nov 8, 2009 at 9:09
  • 1
    $\begingroup$ 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... $\endgroup$
    – Manuel Araoz
    Commented Nov 9, 2009 at 3:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Manuel Araoz
    Commented Nov 9, 2009 at 3:29
  • 2
    $\begingroup$ 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. $\endgroup$
    – Reid Barton
    Commented Nov 9, 2009 at 5:40

9 Answers 9

Reset to default
13
$\begingroup$

Check this blog post.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ This guy understood my question $\endgroup$
    – Manuel Araoz
    Commented Nov 10, 2009 at 13:59
  • 5
    $\begingroup$ Correct me if I'm wrong, but that function is still proved uncomputable by (eventual) reduction to the halting problem. $\endgroup$
    – Darsh Ranjan
    Commented Nov 13, 2009 at 2:12
  • $\begingroup$ 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. $\endgroup$
    – sdcvvc
    Commented Nov 14, 2009 at 1:09
  • $\begingroup$ 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.) $\endgroup$
    – Darsh Ranjan
    Commented Nov 15, 2009 at 22:46
20
$\begingroup$

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.

Improve this answer
$\endgroup$
1
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ why are there only countably many computable functions? $\endgroup$
    – Lucas Mumbo
    Commented Jun 2, 2022 at 5:14
  • $\begingroup$ There are only countably many Turing machines, since a Turing machine can be described using a finite list of data. $\endgroup$
    – Eric Wofsey
    Commented Jun 2, 2022 at 12:53
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Nov 8, 2009 at 4:35
  • 1
    $\begingroup$ I like this example but if the comment above is true, it doesn't answer my question. :D Thanks for the info, though. $\endgroup$
    – Manuel Araoz
    Commented Nov 9, 2009 at 3:21
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Manuel Araoz
    Commented Nov 9, 2009 at 3:18
  • $\begingroup$ See the link in Boris Bukh's comment $\endgroup$
    – Reid Barton
    Commented Nov 9, 2009 at 5:37
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ I would definitely call the BB function self referencing. It is equivalent to the halting problem in the sense mentioned by Boris. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Nov 8, 2009 at 23:16
  • 1
    $\begingroup$ 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! $\endgroup$
    – Manuel Araoz
    Commented Nov 9, 2009 at 3:19
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ I think the original poster wants a describable function. Talking about arbitrary functions is cheating in this sense. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Nov 8, 2009 at 5:38
  • 3
    $\begingroup$ 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 ;-) $\endgroup$
    – Kevin Buzzard
    Commented Nov 8, 2009 at 8:17
  • $\begingroup$ @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? $\endgroup$
    – Manuel Araoz
    Commented Nov 9, 2009 at 3:20
  • $\begingroup$ 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. $\endgroup$
    – Kevin Buzzard
    Commented Nov 9, 2009 at 14:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Darsh Ranjan
    Commented Nov 17, 2009 at 3:34
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – Boris Bukh
    Commented Nov 16, 2009 at 9:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kim Morrison
    Commented Nov 16, 2009 at 17:04
  • 2
    $\begingroup$ 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. $\endgroup$
    – Richard Dore
    Commented Nov 17, 2009 at 2:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .