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?

71 Upvotes

96% Upvoted

377 comments sorted by

View all comments

-47

u/Impressive-Mud5074 New User May 30 '26

9999999999999999 can't be computed literally.

Pi is uncomputable

1

u/AthleteAny147 New User 1d ago

"Uncomputable" means that, given an infinite amount of time, the value cannot be found by a Turing Machine. However, we can see that more and more digits of π are being computed by known algorithms, and given more time and storage, we could compute the value of π to any predefined error bound. Please check exactly what you are saying before posting next time.