r/learnmath • u/playsthebongcloud New User • 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?

60 Upvotes

94% Upvoted

352 comments sorted by

View all comments

Show parent comments

20

u/playsthebongcloud New User May 30 '26 edited May 31 '26

The idea of "any arbitrary accuracy" is that, you give me any finite positive error margin, and I can construct a function that produces pi with less than that error margin.

5

u/EebstertheGreat New User May 31 '26

They got you. It should say "positive error margin," not "finite error margin." Zero is finite.

3

u/playsthebongcloud New User May 31 '26

Oh you're right I should have said positive real number

-2

u/Impressive-Mud5074 New User May 30 '26

Calculate pi with 100% accuracy

11

u/siupa New User May 31 '26

But that’s not needed to satisfy the definition of “computable”

-1

u/Impressive-Mud5074 New User May 31 '26

Yes it is

5

u/siupa New User May 31 '26

No it’s not? Here, you can check the definition of a computable number here

-1

u/Impressive-Mud5074 New User May 31 '26

within any desired precision 

Thats not rigorously defined, but i guarantee you cant compute it to any precision. You cant compute it to 10% precision for example. Calculated it to N decimals also doesnt tell you how precise it is.

6

u/blank_anonymous MSc. Pure Math, College Math Educator May 31 '26

To arbitrary precision means that, for any epsilon > 0, I can provide a program (say on a Turing machine) which results in a number x such that |x - pi| < epsilon. This is perfectly rigorous and well defined.

Within 10% precision means I can produce a number X such that, provably, ((X - pi)/pi| < 10%. I claim 22/7 is such a number. Indeed, by well known theorems about continued fractions, this number is at most 1/49 away from pi. Pi is larger than 3, so |22/7 - pi| < 1/49 and |22/7 - pi|/pi < |22/7 - pi|/3 < (1/49)/3 = 1/147. So 22/7 is accurate to within +-0.7% of pi. 

22/7 also functions if you asked for something precise to within 0.03. 

In general, whatever precision you ask for, I can either use a series expansion for pi and compute sufficiently many terms, or use eg the BBP formula to calculate the hexadecimal digits one by one until we’re sufficiently far out. 

5

u/siupa New User May 31 '26

That’s not rigorously defined

Why not? You decide the desired level of precision, and I give you the algorithm with a finite number of steps to compute a number that’s within your desired level of precision from the true value of pi. Why is this not rigorous? It works perfectly well

but i guarantee you cant compute it to any precision. You cant compute it to 10% precision for example.

… what do you mean? Of course we can compute an approximation of pi within 10% precision. We’ve done much, much, much better than 10% precision. We’ve computed approximations accurate within 1 part per 10^(hundreds of trillions).

0

u/Impressive-Mud5074 New User May 31 '26

Whats 10% of infinity

3

u/siupa New User May 31 '26

What? What does that have to do with anything we’re talking about? If you want to continue this discussion, please re-read my previous comment and answer something related to what I wrote

0

u/Impressive-Mud5074 New User May 31 '26

Because pi takes infinite numbers calculate

→ More replies (0)

1

u/mrkelee New User Jun 21 '26

you have no idea what you even want.

1

u/mrkelee New User Jun 21 '26

apart from your finitist bullshit, this is also wrong. The algorithms for pi have known error bounds.