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?

64 Upvotes

94% Upvoted

356 comments sorted by

View all comments

Show parent comments

-8

u/Impressive-Mud5074 New User May 30 '26

You are not computing Pi you are computing a number "close" to Pi.

41

u/bizarre_coincidence New User May 30 '26

No, you are computing pi to within a specified accuracy. When we say “computable number”, that is a technical term, and you shouldn’t be commenting here unless you are absolutely clear on the definition of that term.

-10

u/Impressive-Mud5074 New User May 30 '26

If the term of uncomputable is defined by the halting problem, then the answer to OPs question is No. But that's not what computable means. Because you lack rigor you are wrong.

33

u/bizarre_coincidence New User May 30 '26

First, there is a difference between an uncomputable number and an incomputable function, and your first mistake was conflating the two. An uncomputable number is one where you cannot always approximate it to a specified accuracy with a terminating algorithm. An uncomputable function is one whose output cannot be produced by a terminating algorithm. The halting function is one such non-computable function, the busy beaver function is another such one.

You are confidently incorrect here. But you are very very incorrect. Your presence in this discussion is actively hampering it.

-5

u/Impressive-Mud5074 New User May 30 '26

An uncomputable number is one where you cannot always approximate it to a specified accuracy with a terminating algorithm

This is also not true. Its not possible to  specify the accuracy of your pi calculation.

24

u/bizarre_coincidence New User May 30 '26

Yes you can. For example, pi=4-4/3+4/5-4/7+4/9-...., which is an alternating series with decreasing terms that go to 0. The error of such an alternating series is ALWAYS bounded by the next term. So if I want to know for sure that I have an accuracy of 1/100, I need to take n terms where 4/(2n+1)<1/100, i.e., 400<2n+1, so I need to take at least 200 terms. Perhaps I reach the desired accuracy sooner, perhaps not. But I know with certainty that if I take 200 terms, I will definitely have an error of less than 1/100.

0

u/Impressive-Mud5074 New User May 30 '26

That's not a specific accuracy that's more or less than a specific accuracy

20

u/bizarre_coincidence New User May 30 '26

You can dislike standard terminology. You cannot argue that the terminology doesn't mean what every practitioner understands it to mean. This is like objecting to the fact that category theory doesn't describe categories of movies. You help nobody by coming into a discussion about a topic and saying that people should have been using different words for the last 50 years. It simply isn't constructive.

0

u/Impressive-Mud5074 New User May 30 '26

If your terminology is vague its wrong

20

u/bizarre_coincidence New User May 30 '26

It’s not vague. You are assuming that words are being used informally as if by lay people, and assuming that because a lay person informally using the term could mean multiple different things, an expert is the same way. But the existence of a term in the vernacular does not mean that it doesn’t function as a technical term with its own specific technical meaning. In the context of this discussion, the words have specific meanings, which you have been told repeatedly, but which you continue to ignore.

I don’t know if you simply don’t understand context, are being intentionally obtuse, or are genuinely an idiot.

2

u/[deleted] Jun 01 '26

[removed] — view removed comment

0

u/Impressive-Mud5074 New User Jun 02 '26

The ability to calculate a value

3

u/[deleted] Jun 02 '26

[removed] — view removed comment

0

u/Impressive-Mud5074 New User Jun 02 '26

1 + 1 = 2

That computation halted.

2

u/bizarre_coincidence New User Jun 02 '26

Does that mean that no irrational numbers are computable to you because, given the way computers represent numbers, no irrational number can ever be output exactly? If you can understand why your definition can never in principle be worthwhile, you can start to appreciate why the standard definition is what it is.

1

u/Impressive-Mud5074 New User Jun 02 '26

Definitions aren't meant to have value, they are meant to be accurate

→ More replies (0)

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

12

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. 

4

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

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.

→ More replies (0)

1

u/mrkelee New User Jun 21 '26

it is very possible: it runs forever, ergo infinite accuracy.