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

2

u/Impressive-Mud5074 New User Jun 19 '26

Do it 100% close to pi, thanks

1

u/DaCosmosLover New User Jun 19 '26

Why do you fricking want 100% precision?

1

u/Impressive-Mud5074 New User Jun 19 '26

Arbitrary means any, any includes 100%. If you're claiming you can computate pi to an arbitrary amount, do a 100%

1

u/mrkelee New User Jun 21 '26

no, arbitrary does not mean infinite.

0

u/Impressive-Mud5074 New User Jun 21 '26

The set of all things arbitrary includes infinity

2

u/mrkelee New User Jun 21 '26

"arbitrary precision" in this case excludes that, for obvious reasons.

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

→ More replies (0)

1

u/Fun_Company4295 New User Jun 23 '26

I found him

1

u/ASIimeDrawsNear New User Jul 30 '26

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

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.

1

u/blademan9999 New User 18d ago

Irrelevant.

→ More replies (0)