3
$\begingroup$

I apologize if this question sounds too philosophical. I am reading about Turing's paper on computability and it got me thinking:

Why do we bother defining the mysterious "undefined things" in-between on the real number line? How important are they?

I agree that it is ok to define anything and work with any structures. But undoubtedly, some structures are more interesting than others.

Does distinguishing between computable and uncomputable real numbers generate any important results in mathematics?

(Edit: Thank you for the answers so far, I understand that we do not have to distinguish computability in the set of real numbers. I am curious what happens if we do (in any way). Has anyone investigated?)

$\endgroup$
2
  • 3
    $\begingroup$ We defined real numbers before computers or the theory of computability even existed. We didn't "make up" uncomputable numbers, we already had the reals, and we made a new interesting set of computable numbers, and noticed that the two are not the same. So the numbers missing from the second set get called uncomputable. $\endgroup$
    – 5xum
    Sep 28, 2018 at 13:35
  • $\begingroup$ Seems related: math.stackexchange.com/questions/948171/… $\endgroup$
    – Asaf Karagila ♦
    Sep 28, 2018 at 13:35

2 Answers 2

Reset to default
4
$\begingroup$

Uncomputability as a phenomenon occurs throughout mathematics. Although theoretical computability may seem a very abstract subject, it does have concrete applications.

For example, the negative solution to Hilbert's 10th problem shows that there is no algorithm to determine if a multivariate polynomial equation over the integers has integer roots. This means that nobody is spending time trying to find such an algorithm, because we know that there is none. In this way, theoretical computability provides a "backstop" for other areas of algorithmic mathematics.

There is also a research field of "computable analysis" which studies the analysis that can be done with computable real numbers. Of course there are restrictions, but by adding additional hypotheses we can get similar versions of many theorems. For example, the intermediate value theorem continues to hold if we look at computable continuous functions and computable real numbers. There are also theorems about derivatives and integrals of computable continuous functions, such as this question on MathOverflow and this paper by Ning Zhong.

$\endgroup$
1
$\begingroup$

The "uncomputable" comes in computability theory often in the form of undecidability. A subset $A$ of ${\Bbb N}_0^k$ is decidable iff its characteristic function is recursive (computable and total). One prominent example is the halting problem. As far as I known it has no real impact on programming these days. But in terms of the theory of computation the situation gets even more frustrating since by the theorem of Rice, we can say that each nontrivial program property is undecidable.

$\endgroup$
1
  • $\begingroup$ When I learned programming, I noticed compiler warnings of this type: "The return value of function xyz() could be undefined". This happens for instance if you return a variable which gets assigned inside if-clauses. I knew that actually the return variable gets always at some point assigned, in every case, but the compiler doesn't know this. I asked whether it is possible to make a compiler which analyses your code to determine whether the return value is always defined. Years later when I was in university I learned about the halting problem. On my way home this day I noticed its the same. $\endgroup$
    – S. M. Roch
    Sep 28, 2018 at 16:12

You must log in to answer this question.

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