0
$\begingroup$

This is a rather strong claim, and therefore likely to be incorrect, but hear me out.

Firstly, when I talk of “computations”, I mean this in a broader sense than normally used, because I am including “infinite computers”, e.g. Turing machines that can perform computations not in a finite amount of steps, but infinite or even uncountable. e.g., a Turing machine that can check (using an uncountable number of computations for any subset of an uncountable $X$ whether it is open in $(X,T)$ is allowed.

This means my question is inherently a bit vague, because I don’t know a lot about infinite Turing machines, and I am not sure how “computational complexity” is defined for such infinite Turing machines (and not sure if it has been studied at all).

But it seems to me that if you squint your eyes, many theorems in math can be seen as performing the role of “simplifying computation”:

Claim. Every mathematical definition gives a (possibly incomputable in finite time) algorithm.

Example. Definition: A function $X$ to $Y$ is continuous iff every open set in $Y$ has open preimage. This gives an algorithm: Check for each open set in $Y$ whether the preimage is open in $X$. (algorithm requires infinite computational time for uncountable spaces).

Many theorems can be seen as “simplifying computations”:

  • Some theorems turn incomputable algorithms into computable algorithms. For example, the algorithm that checks whether a function $f$ is made up of a composition of a database of other continuous functions, is computationally simpler than the algorithm induced by the definition of continuity (though can only verify, and only for a subset of functions)

  • some theorems turn incomputable algorithms into still incomputable but “less complex” algorithms.

I’m gonna make a (largely unwarranted) generalization from this:

Bold and weakly substantiated claim. Every non-trivial theorem in mathematics can be seen as motivated by an attempt to reduce an algorithm (possibly requiring infinite computation) that answers questions $Q$, to a simpler algorithm that answers questions $Q$ or some subset thereof.

Do you think there is something to this? Are there a preexisting ideas about this?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ This should probably be on Mathematics or even MathOverflow as you'd want to ask mathematicians. I'd expect the answer to be a hollering "no". Unless you generalize the notion of "computation" so much it becomes useless, there's plenty of descriptive/declarative mathematics around. Also, proofs (in non-computable domains) are not computation, and mathematics is mostly about proofs. $\endgroup$ – Raphael♦ Mar 2 '19 at 12:50
  • $\begingroup$ @Raphael, the reason I'm asking it here, is because the question is based completely on the idea of infinite computers, which is a CS topic. (Also, I'm not sure you've read what I wrote about infinite computations based on your comment). $\endgroup$ – user56834 Mar 2 '19 at 12:53
  • 1
    $\begingroup$ @user56834 Actually infinite-time computation is a mathematical topic at least as much as it's a CS topic - there's a whole ton of literature under the name "generalized recursion theory" you would probably be interested in, including infinite-time Turing machines. I do think this would be more appropriate at math.stackexchange, although I don't think it's strictly inappropriate here; it may also fit at philosophy.stackexchange. $\endgroup$ – Noah Schweber Mar 2 '19 at 15:49
  • $\begingroup$ I am gonna make a (largely unwarranted) generalization from this: Bold and weakly substantiated claim. Every non-trivial fact or abstraction in human knowledge can be seen as motivated by an attempt to reduce an algorithm (possible requiring infinite computation and quantum oracle) that answers questions $Q$, to a simpler algorithm that answers question $Q$ or some subset thereof. (I could claim this is my original thoughts, even though I believe it must have been folklore, regardless how much it makes sense). $\endgroup$ – John L. Mar 2 '19 at 20:36
  • $\begingroup$ Theorems cannot "turn incomputable algorithms into computable algorithms;" they may find or help formulate a (computable) algorithm for a problem, for which formerly no (computable) algorithm was known. But this knowledge has nothing to do with the computability of the problem. You would have to use the term computable in the sense of "computable according to the current state of knowledge," which is not its common usage. $\endgroup$ – Peter Leupold Mar 8 '19 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.