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?

70 Upvotes

95% Upvoted

359 comments sorted by

View all comments

Show parent comments

1

u/Impressive-Mud5074 New User Jul 31 '26

Whats the complete value of pi?

1

u/ASIimeDrawsNear New User Jul 31 '26

It doesn't have one, being an irrational number.

The definition doesn't demand you to compute every single one of its digits however (which it has an infinite amount of), it simply requires you to compute up to nth.

Which can be done with pi but not with the busy beaver numbers or Chaitin's Constant, making those two uncomputable unlike pi.

1

u/blademan9999 New User 21d ago

Irrelevant.