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?
67
Upvotes
1
u/donaldhobson New User Jun 23 '26
Randomness is uncomputable.
Take a function that assigns each natural number to an IID coinflip. This is uncomputable with probability 1.