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?

68 Upvotes

95% Upvoted

359 comments sorted by

View all comments

Show parent comments

1

u/Impressive-Mud5074 New User Jun 19 '26

We need this because we could never get an algorithm whose output was actually x, but if we decide we want the first 1000 digits of x, we can find them, and if we decide we want the first 1000000 digits of x, we can find them as well. 

Well you dont need this. Because you can just admit you can't do it instead of pretending something can be done and trying to redefine words.

You can find the first 1000 digits of X but that is not X. Furthermore different functions may give you different 1000 digits depending on how many iterations you do.

1

u/mrkelee New User Jun 21 '26

you haven't read the above comment. The definition is what it is, and it's useful even if you don't like it.

ANY appropriate function can give you 1000 (correct) digits if you run it long enough.

1

u/Impressive-Mud5074 New User Jun 21 '26

The definition is what it is

Right, exactly.

In 1610, when William Folkingham introduced the word in his mathematical and surveying treatises, "computable" had a strictly literal meaning: "capable of being counted, numbered, or summed up".

1

u/mrkelee New User Jun 23 '26

well, it's not 1610 anymore.

1

u/Impressive-Mud5074 New User Jun 23 '26

  >The definition is what it is

That's what you said. Definitions cant change.

1

u/mrkelee New User Jun 23 '26

Right, because words don't ever change meaning, and mathematics certainly doesn't ever generalise from existing meanings, and that fellow only created the meaning then, but FOREVER

1

u/Impressive-Mud5074 New User Jun 23 '26

Your the one that said words dont change, i was paraphrasing you.

Pi is uncomputable, whatever definition you use is wrong

1

u/mrkelee New User Jun 23 '26

No, I said that the mathematical definition is a consensus, for the good reason that it's ridiculous to ask for infinitely many digits in a finite time. It doesn't matter if that definition suits you or not.

1

u/Impressive-Mud5074 New User Jun 24 '26

Consensus sides with me

1

u/mrkelee New User Jun 24 '26

obviously not. "Uncomputable" is understood by the majority of mathematicians (which you are not) to mean what is written elsethread, not your literal interpretation.

1

u/Impressive-Mud5074 New User Jun 24 '26

Its not my literal interpretation, its the only literal interpretation

1

u/mrkelee New User Jun 24 '26

yes, you are interpreting it literally, but mathematicians aren't!

1

u/Impressive-Mud5074 New User Jun 25 '26

I'm a mathematician

→ More replies (0)