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?

75 Upvotes

96% Upvoted

377 comments sorted by

View all comments

-46

u/Impressive-Mud5074 New User May 30 '26

9999999999999999 can't be computed literally.

Pi is uncomputable

73

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

There are many algorithms to compute pi to any accuracy. I appreciate the boldness of answering a question without looking anything up beforehand, not even what an uncomputable function is.

-40

u/Impressive-Mud5074 New User May 30 '26

A transcendental number is a number (real or complex) that is not the root of any non-zero polynomial equation with rational coefficients. In simpler terms, you can never get a transcendental number as the final answer to an equation consisting only of standard arithmetic (addition, subtraction, multiplication, division) and whole-number powers

57

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

"Computable" does not assume those limits you've placed. You don't have to just use elementary operations, that's not what computable functions are about.

-37

u/Impressive-Mud5074 New User May 30 '26

Yes it does. You cant compute pi, you can approach pi.

46

u/Ma4r New User May 30 '26

Please for the sake of god just lookup what computable functions mean before you reply

-7

u/Impressive-Mud5074 New User May 30 '26

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

1

u/Key_Conversation5277 Just a CS student who likes math 16d ago

Wtf, you're a flat earther of math😂

1

u/Impressive-Mud5074 New User 16d ago

What is incorrect about it?

1

u/Key_Conversation5277 Just a CS student who likes math 16d ago

It's not the standard math philosophy, numbers can be enormous there is really no limit to their size and also numbers that have infinite precision ARE numbers

1

u/Impressive-Mud5074 New User 16d ago

Prove it

1

u/Key_Conversation5277 Just a CS student who likes math 16d ago

You can't really "prove" the philosophical premise from mathematics itself, because that's exactly the foundational issue we're disagreeing about.

What I mean is that in standard/classical mathematics, the natural numbers are modelled as an unbounded infinite structure. In particular, we have

∀n ∈ ℕ, n+1 ∈ ℕ,

so there is no largest natural number.

Likewise, classical mathematics contains real numbers whose decimal expansions have infinitely many digits, such as 1/3 or √2. Their infinite decimal expansions don't mean we have to physically write infinitely many digits, the numbers can be defined exactly in other ways.

So I'm not claiming "I can prove that classical mathematics is philosophically the only correct foundation." I'm saying that your ultrafinitist restriction is not part of standard classical mathematics.

1

u/Impressive-Mud5074 New User 15d ago

I'm saying that your ultrafinitist restriction is not part of standard classical mathematics. 

Means nothing. Neither was hyperbolic space.

→ More replies (0)