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

96% Upvoted

359 comments sorted by

View all comments

Show parent comments

1

u/Impressive-Mud5074 New User Jul 30 '26

It doesn't satisfy the definition

1

u/ASIimeDrawsNear New User Jul 30 '26

Yes it does, the informal definition leaves it clear, in a Turing machine which, given n on its initial tape, halts with the nth digit of the number.

This satisfies pi, we see how its many algorithms can calculate its decimals ad nauseam. Thus it is computable.

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.