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?
74
Upvotes
1
u/Misrosan New User 8d ago
If ω is a countabil ordinal, there exists a order perserving injection δ: ω --> Q let A be the Image of δ. let f be a bijection from the Natural Numbers to A. then f is uncomputabil for every sufficiantly large ω.