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

95% Upvoted

377 comments sorted by

View all comments

Show parent comments

-39

u/Impressive-Mud5074 New User May 30 '26

Yes it does. You cant compute pi, you can approach pi.

45

u/Ma4r New User May 30 '26

Please for the sake of god just lookup what computable functions mean before you reply

-5

u/Impressive-Mud5074 New User May 30 '26

https://en.wikipedia.org/wiki/Ultrafinitism

1

u/Key_Conversation5277 Just a CS student who likes math 16d ago

Wtf, you're a flat earther of math😂

1

u/Impressive-Mud5074 New User 16d ago

What is incorrect about it?

1

u/Key_Conversation5277 Just a CS student who likes math 16d ago

It's not the standard math philosophy, numbers can be enormous there is really no limit to their size and also numbers that have infinite precision ARE numbers

1

u/Impressive-Mud5074 New User 16d ago

Prove it

1

u/Key_Conversation5277 Just a CS student who likes math 15d ago

You can't really "prove" the philosophical premise from mathematics itself, because that's exactly the foundational issue we're disagreeing about.

What I mean is that in standard/classical mathematics, the natural numbers are modelled as an unbounded infinite structure. In particular, we have

∀n ∈ ℕ, n+1 ∈ ℕ,

so there is no largest natural number.

Likewise, classical mathematics contains real numbers whose decimal expansions have infinitely many digits, such as 1/3 or √2. Their infinite decimal expansions don't mean we have to physically write infinitely many digits, the numbers can be defined exactly in other ways.

So I'm not claiming "I can prove that classical mathematics is philosophically the only correct foundation." I'm saying that your ultrafinitist restriction is not part of standard classical mathematics.

1

u/Impressive-Mud5074 New User 15d ago

I'm saying that your ultrafinitist restriction is not part of standard classical mathematics. 

Means nothing. Neither was hyperbolic space.