5

In English, the word "function" means "doing". Asking "what's its function?" is logically equivalent to asking "what does it do?". So a non-computable function is, by the definition of its constituents, logically equivalent to a non-algorithmic process.

But with the exception of stochastic processes (that is, processes like generating random numbers that just happen without cause, or whose cause is too intractable to analyze so that for all intents and purposes it's as if it happens without cause), it is not possible to conceive of a non-algorithmic process.

Then why is a non-computable function a coherent idea?

11
  • 4
    You are equivocating on the meaning of the word "function". Commented Dec 14, 2023 at 5:26
  • 5
    @Fomalhaut, welcome to English. Why do they call a structure made to help woodworking a saw horse when it's not a horse? Why do they call call throwing the ball a pitch when pitch is an angle? Why do they call the thing you control a computer with a mouse? Why do they call something you wear when it's cold a sweater? Shouldn't a sweater make you sweat? Commented Dec 14, 2023 at 6:29
  • 6
    It is a good question and is being ridiculed by ignoramuses. I suggest you close your own question (ie delete it) because the English reference is a red herring. Instead if you study the history of function from the time of Bernoulli, Euler etc you will see the notion then corresponded to your notion, nowadays called computable function and due to some various so called crises in math (or causing it!!) it got changed in the twentieth century to this modern notion: A possibly uncountable (therefore noncomputable) set of ordered pairs.
    – Rushi
    Commented Dec 14, 2023 at 8:40
  • 3
    When you can phrase it in terms of the math history rather than the English analogy you can reopen it. Florian Cajori's classic History of mathematical notations may be a good starting point available on archive.org. Also see my comment below Katz' answer below
    – Rushi
    Commented Dec 14, 2023 at 8:59
  • 5
    I agree this is a real problem and not just a terminological one. A non-computable function is related to the concept of an undecidable problem. There are many of those. Determining whether a sentence of first-order classical logic is satisfiable is undecidable. We understand what a sentence is and what satisfiable means. We can specify a function from a sentence to a truth value that returns true if the sentence is satisfiable and false if it is not. We know what this function does, but it is not computable. We distinguish between a specification and an engine that computes it.
    – Bumble
    Commented Dec 14, 2023 at 10:06

3 Answers 3

1

I want to say that I accept your premise, that there is an ontological problem with noncomputable functions. If something has no possible consequences for any practical experiment or observation we can carry out, in what sense is it meaningful?

But there are some ways that noncomputable functions can, in fact, be practically examined by some procedure.

First, there may actually exist a "method" to calculate some noncomputable functions. Some noncomputable functions may still be limit-computable. To be limit-computable means that we can write a program that gradually approximates the function, producing better and better approximations as time goes on, tending towards perfection if we let it keep running. The halting problem is limit-computable and can be "solved" in this manner. The only caveat is that we don't know how long it will take to get an accurate value for a given input.

Second, in mathematics, we often deal with specifications of functions without worrying about how the function could be calculated. We can calculate properties of the specification without needing to calculate the function itself. So it is grounded in some practical observation in the end; "what we can get a ZFC theorem checker to accept."

For many mathematical objects, it is best to think of them as imaginary hypotheticals. "What if we had a Euclidean plane - what could we say about it?" We can examine questions like this without needing to propose there is actually any Euclidean plane in this world. The same perspective may be helpful for some noncomputable functions.

2
  • 1
    Limit computable is problematic, because a limit presupposes that there's something in external reality that it's approaching. But by the definition of a non-computable function, there's nothing in external reality that it's approaching.
    – Fomalhaut
    Commented Dec 14, 2023 at 5:45
  • 1
    @Fomalhaut There is no contradiction between a function being uncomputable and it being limit computable.
    – causative
    Commented Dec 14, 2023 at 13:21
1

Your argument owes its plausibility to a conflation of the generic meaning of the term function and its technical meaning. The generic meaning, as well as possibly the etymology, do suggest an inherent aspect of computability. However, the technical meaning of the term as used in modern mathematics is broader, and includes non-computable entities, as well.

Another example of a significant difference between the generic and the technical meaning is the term asymptote. Its etymology suggests that the line will never meet the curve. However, in its technical meaning, the line can certainly meet the curve, even infinitely many times; consider for example the function (sin x)/x and its horizontal asymptote.

In fact, many historians consider it to be a major accomplishment of 19th century mathematicians when they succeeded in broadening the meaning of the term function beyond its previous connotation of "a specific rule that, given an x, produces a y."

Whether or not it is an accomplishment or a setback is of course open to debate. Constructive mathematicians will have more reservations about it than mathematicians working in classical logic.

4
  • Its good youve put modern math. It was only after Weierstrass, Dedekind, Cantor etc (Im not sure if Ive missed key names) at the end of the 19th century that function as formula or at most computational rule got morphed into the modern notion: Set of ordered pairs
    – Rushi
    Commented Dec 14, 2023 at 8:56
  • @Rushi, very true. Leibniz for example would have found the idea of "infinite set of ordered pairs" meaningless. Commented Dec 14, 2023 at 8:58
  • "However, in its technical meaning, the line can certainly meet the curve, even infinitely many times; consider for example the function (sin x)/x and its horizontal asymptote." <- Okay but this is a very technical point. In spirit, an asymptotic is a line that a curve approaches and never touches. But what a function means in computability theory has changed from "a verb" to "a set of ordered pairs with an arbitrary restriction on the abscissa", and it's now no longer obvious that this is spiritually or morally speaking the same object.
    – Fomalhaut
    Commented Dec 14, 2023 at 9:02
  • @Fomalhaut, The issue of computability concerns already the real numbers, even before we get to functions. See for example this recent comment. The issue with ideal entities in mathematics is always the same: on the one hand, they don't seem to correspond to anything in physical reality; on the other, they sometimes facilitate the mathematician's work, and yield insight into entities that are computable. 400 years ago a similar issue concerned the complex numbers. Commented Dec 14, 2023 at 10:30
1

We discovered that some functions are not computable after we started pondering the concept of a function, as part of the overall refutation of Hilbert's program.

You must log in to answer this question.

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