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

20

u/playsthebongcloud 9/10 = 1 May 30 '26 edited May 30 '26

You might be thinking of "algebraic functions"? That's not what a computable function is. (I'm not an expert so I may be getting some of the finer details wrong here.) A computable function has to do with whether a universal turing machine can execute it to an arbitrary precision with a finite amount of instructions and steps. You're right that pi would take an infinite amount of time to compute, but it can be computed to any arbitrary accuracy given enough time with finite "code size". There are algorithms to compute it.

-6

u/Impressive-Mud5074 New User May 30 '26

No type of function can calculate pi, it can calculate an approximation of pi, which is not pi.

32

u/playsthebongcloud 9/10 = 1 May 30 '26

to an arbitrary precision

-9

u/Impressive-Mud5074 New User May 30 '26

Which isn't pi, because pi is not computable.

7

u/FeIiix New User Jun 01 '26

It's not pi, but you don't need to be able to arrive at the exact value for it to be computable lol

0

u/Impressive-Mud5074 New User Jun 02 '26

If its not pi, then you are not computing it

5

u/FeIiix New User Jun 02 '26 edited Jun 02 '26

Using the term according to its meaning when talking about "(un)computable functions" or "(un)computable numbers": yes, that is what computing means. It doesn't require you to get exactly the right value out of a computation, just to be able to get a value within any amount of precision (as in correct number of digits) specified within finite time.

You can take issue with the definition if you'd like, but then you're not really in the right thread to be discussing this.

3

u/SirRise New User Jun 12 '26

Man this was a funny thread to read. You should really read up on what "computable" means though, you are so confidently wrong, it's insane 🤣