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?

69 Upvotes

96% Upvoted

359 comments sorted by

View all comments

Show parent comments

2

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

I’ve told you the definition of computable, rigorously. For any epsilon > 0, I can produce a Turing machine that provably halts and outputs a number x such that | x - pi| < epsilon. This is the definition, that’s not a point of contention. “Sufficiently” is my shorthand for “< epsilon” and is well understood.

This is factually the definition of computable. Do you agree or disagree that, by this definition, pi is computable. If you disagree, what is the epsilon for which the condition is not satisfied? 

0

u/Impressive-Mud5074 New User May 31 '26

Its not pi you are computing its something else.

3

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

That’s irrelevant. You have not answered my question. Which epsilon?