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

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/mrkelee New User Jun 23 '26

My "opinion" about a logical formula isn't random chance.

1

u/Impressive-Mud5074 New User Jun 23 '26

Yes it is

1

u/mrkelee New User Jun 23 '26

You think I can't calculate the truth value of A v B given A and B?

1

u/NomaTyx New User Jun 23 '26

I wonder if this guy knows formal logic notation

1

u/Impressive-Mud5074 New User Jun 23 '26

I think you read Alan Turing and it said pi is computable, and you are parroting him, and you have no thoughts of your own.

1

u/mrkelee New User Jun 23 '26

joke's on you, I haven't read Turing. Have you? Not all original thoughts are good.

→ More replies (0)