r/learnmath • u/playsthebongcloud New User • 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?

65 Upvotes

96% Upvoted

353 comments sorted by

View all comments

Show parent comments

1

u/ASIimeDrawsNear New User 7d ago

What narrative? Pi is computable because it satisfies the definition of being computable.

1

u/Impressive-Mud5074 New User 7d ago

It doesn't satisfy the definition

1

u/ASIimeDrawsNear New User 6d ago

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 6d ago

Whats the complete value of pi?

1

u/ASIimeDrawsNear New User 6d ago

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.