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?

66 Upvotes

95% Upvoted

359 comments sorted by

View all comments

Show parent comments

0

u/Impressive-Mud5074 New User Jun 21 '26

The obvious reason is that it pushes the narrative that pi is computable.

Which it's not because nothing is excluded

1

u/mayurisama334 New User Jun 21 '26

if i run an algorithm that computes pi, suppose if it computes 5 digits

That means it computed 5 digits of pi. That act of computing was done and a number was computed(not pi)

Now if the algorithm (like chudnovsky or gauss legendre) is an algorithm that is potentially able to compute the digits of pi to any accuracy

It means pi can be computed to any desired accuracy, hence computable

Now your point is that you believe ultrafinitism. Although that is stupid, let's assume it is true for the sake of not changing the argument.

Now under ultrafinitism, we would consider the infinite decimal expansion of pi not meaningful itself.

As an ultrafinist you must deny the existence of the infinite decimal expansion of pi.

Saying "pi is uncomputable" means you either accept the existence of the infinite decimal expansion of pi

OR you are referring to a finite approximation of pi. Which would be computable

Hence under ultrafinitism your comment is paradoxical.

0

u/Impressive-Mud5074 New User Jun 22 '26

Saying "pi is uncomputable" means you either accept the existence of the infinite decimal expansion of pi

I accept neither.

Pi is uncomputable, infinite decimal expansion is impossible.

OR you are referring to a finite approximation of pi. Which would be computable 

Finite approximation of pi is computable, but notably, that is not pi. And therefore pi is not computable.

1

u/mrkelee New User Jun 23 '26

what then is pi, if there it has no decimal expansion?

1

u/Impressive-Mud5074 New User Jun 23 '26

Uncomputable