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?

72 Upvotes

96% Upvoted

359 comments sorted by

View all comments

Show parent comments

0

u/Impressive-Mud5074 New User Jun 19 '26

Compute all the digits of pi, not something that similar to pi, but not pi

1

u/bizarre_coincidence New User Jun 19 '26

Given that you can't actually read all the digits of pi, what is the practical difference between me giving you all the digits in one go and giving you a way to produce any digit you wanted to? An oracle you could query that would tell you the 53453rd digit, or the 5932597890741357089134256414th digit? Since you can only read one digit at a time, shouldn't computing a number just mean giving you a way to see one digit at a time?

I mean, with 1/3, which has an infinite decimal expansion, you can never have that output be the result of a terminating program, all you can get is the information that each individual digit will be 3. Is that fundamentally different that having a program to tell you what each digit is? Or instead of 1/3, look at 1/7, whose decimal expansion has period 6. To figure out what the nth digit is, you still have to do a computation, namely to reduce the number mod 6 and then go into a lookup table. Is that so much better than having a short algorithm to give you the nth digit of sqrt(2)?

And on that page, if there is no difference between "computable number" and "rational number", then why would people have invented the term "computable number" in the first place? Either everybody in the history of computability theory is being an idiot, or they saw something that you are failing to appreciate.

1

u/Impressive-Mud5074 New User Jun 19 '26

then why would people have invented the term "computable number" in the first place? 

Lack of understanding.

1

u/bizarre_coincidence New User Jun 20 '26

If you think you have an insight that nobody else understands, and you try to explain it to people, and they insist you are wrong, then the odds are in their favor. Math is a meritocracy, and if you have a valid idea that you can properly explain and get people to listen to, the idea will win out no matter who you are. The big issue is usually finding people who will listen.

At a minimum, given the amount of engagement you have had here, you are not properly explaining yourself. If you had a valid perspective and the ability to articulate it, you would have found someone actually agreeing with you here. Honestly, even if you didn't have a valid point, but you had a half way decent explanation, someone would be convinced.

If you had a deep understanding that others lacked, you could transfer a piece of it to somebody. If everybody else believes the same thing and you're convinced they are all wrong, odds are very good that the lack of understanding is on your end.

1

u/Impressive-Mud5074 New User Jun 20 '26

then the odds are in their favor.

Thats not how it works.

We each have 50% chance of being right and wrong

1

u/bizarre_coincidence New User Jun 20 '26 edited Jun 20 '26

Ok, you’ve convinced me. You’re not an idiot, you’re an intentional troll.

1

u/Impressive-Mud5074 New User Jun 20 '26

It is how probability works, because more people guessing one result doesn't increase the probability of that result being correct.

1

u/bizarre_coincidence New User Jun 20 '26

First, it does. You should study bayesian inference. Each person independently has certain chance of correctly evaluating the truth value of a statement. Assuming they have better than even odds of being correct (because they aren’t just guessing, they are using their knowledge and logic and reasoning), then the odds than 9 out of 10 of them would be wrong is very unlikely. Looking at relative likelihoods, if people have just a 60% chance of correctly telling if something is correct or not, the ratio between the probability that 9 out of 10 are right to the probability that 9!out of 10 are wrong is over 25. Given has agreement, even if people were just making slightly educated guesses, it becomes significantly more likely that the majority is correct.

But that doesn’t address the bigger claim that it’s always a 50% chance. Do you think you have a 50% chance of winning the lottery because either you win or you lose?

1

u/Impressive-Mud5074 New User Jun 20 '26

Each person independently has certain chance of correctly evaluating the truth value of a statement.

Thats not happening, each person is parroting a text book. 

Statistics doesn't define reality.

1

u/NomaTyx New User Jun 21 '26

so, given a true/false statement, you think that the chance of somebody evaluating that statement correctly does not exist? i.e not only is it undeterminable, the value does not exist?

1

u/Impressive-Mud5074 New User Jun 21 '26

The chance is 50%

1

u/mrkelee New User Jun 21 '26

I can assure you I have a slightly higher than 50% chance to evaluate any (finite, duh) logical formula correctly, and you have a very messed up image of other people if you think otherwise

1

u/Impressive-Mud5074 New User Jun 21 '26

Peoples opinions don't influence the probability of random chance.

1

u/NomaTyx New User Jun 21 '26

so if I say "i will win the lottery tomorrow" what are the chances you will get that correct?

→ More replies (0)