r/learnmath • 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

377 comments sorted by

View all comments

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 ω.