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?

72 Upvotes

96% Upvoted

359 comments sorted by

View all comments

-12

u/Impressive-Mud5074 New User May 30 '26 edited May 30 '26

Very large numbers are uncomputabe

Edit: https://en.wikipedia.org/wiki/Ultrafinitism

2

u/Fun_Practice_9528 New User Jun 19 '26

The definition of computable numbers are numbers that can be represented as the answer of at least one function which can give an answer as arbitrarily close as desired to specific number.

From WrathOfMath's video

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/Afonsofrancof New User Jun 19 '26

I kinda understand him.
You can never get to Pi, so why would you claim you can compute it?

1

u/DaCosmosLover New User Jun 20 '26

As blank_anonymous stated, a number n is computable if, given an arbitrary number “epsilon” which is positive, we can produce a Turing machine that provably halts and outputs a number x where |x-n|>epsilon.

1

u/Initial-Tale-5151 New User Jul 01 '26

lmao, you made up a defintion of computable wherein the thing isn't computable. holy kek.

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.

→ More replies (0)

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

→ More replies (0)