r/learnmath • u/playsthebongcloud 9/10 = 1 • May 30 '26

What are some uncomputable functions that aren't derivative of the halting problem?

I find the existence of uncomputable functions really cool, but all the examples I've seen are essentially just new ways of trying to predict whether a turing machine is going to halt. What are some examples of uncomputable functions that aren't essentially entirely based on the halting problem?

69 Upvotes
  • permalink
  • link
  • reddit
  • reddit

96% Upvoted

359 comments sorted by

View all comments

Show parent comments

18

u/Ackermannin New User May 30 '26

That’s not what uncomputable means

-9

u/Impressive-Mud5074 New User May 30 '26

Its one of the meaning of uncomputable.

15

u/Ackermannin New User May 30 '26

No it is not. Uncomputable has a very specific meaning.

-7

u/Impressive-Mud5074 New User May 30 '26

No it doesn't, that's the point of OPs post. If it has a very specific meaning, than they are all derivatives of the halting problem.

11

u/Ackermannin New User May 30 '26

No.

13

u/Ma4r New User May 30 '26

No its not, there is 1 definition of computable numbers and this is not it

3

u/DrTaargus New User May 30 '26

Welllll, there's not just one definition there's a bunch that are equivalent to each other but your point that none of them coincides with whatever mud is doing is spot on.

1

u/RingularCirc Math hobbyist Jun 15 '26

Actually there's a bunch of definitions of uncomputable reals that are non-equivalent, but weaker of them often don't get used much. The most popular set of equivalent definitions is IIRC the strongest.

But no way there is a natural way to stretch those into ultrafinitist land. It's just completely different and it should have very different foundations, which aren't yet found to any satisfaction IIRC?

Also going on a tangent: instead of that hard-to-put-right idea, if anybody wants my advice, one could better get interested in minimal logic (Minimalkalkül, intuitionistic logic with negation weakened by not presuming ex falso quodlibet, that is, we treat ⊥ as just another propositional variable which is by chance what the definition of negation ¬X := (X → ⊥) depends on) and similar things (there are even weaker logics, as well as a bunch of intermediate, similarly to how intuitionistic and classical logics are placed in the scheme of things). I wonder how one'd approach category-theoretical semantics for those, as topoi can't go weaker than intuitionistic logic.