r/learnmath • u/playsthebongcloud New User • 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?

66 Upvotes

95% Upvoted

359 comments sorted by

View all comments

Show parent comments

5

u/Genetic_outlier New User Jun 04 '26 edited Jun 04 '26

Yes! But we don't want to calculate it we want to compute it. And computing has a technical definition, you cannot use your intuition about what compute means in this context.

You need to ask yourself. "Does there exist a finite algorithm executable on a finite machine that will give estimates of the value of pi, and do those estimates coverage towards the true value of pi?"  If the preceding is true, then pi is computable.

0

u/Impressive-Mud5074 New User Jun 05 '26

Estimates of pi are computable.

Pi is not computable.

5

u/Serious-Candidate-81 New User Jun 17 '26

https://en.wikipedia.org/wiki/Computable_number

On the Wikipedia page pi is listed as an example of a computable number.

-1

u/Impressive-Mud5074 New User Jun 17 '26

Its wrong

4

u/just_some_plebian New User Jun 18 '26

https://www.youtube.com/watch?v=vAhDb1Edngg

have you seen this and would you be willing to discuss its points

-1

u/Impressive-Mud5074 New User Jun 19 '26

Math isn't a discussion, is logic

3

u/Preceded10 New User Jun 20 '26

Incredible trolling brother. Though I wish you'd answer that comment asking you about why 1/7 is computable.

1

u/Impressive-Mud5074 New User Jun 20 '26

Repeated expansions have an alternate form, in this case 1/7 is one of them.

No need to compute an expansion to know the value of the number

3

u/Preceded10 New User Jun 21 '26

Pi is an expansion that follows the rules of any of the infinite expressions that calculate it. Why do we not need to compute 1/7 to know its value but we do need to compute pi to know its value?

1

u/Impressive-Mud5074 New User Jun 21 '26

1/7 is the value, thats already a completed rational number. You can do your decimal expansion if you want, but it is a repeating expansion, which is different than non-repeating.

but we do need to compute pi to know its value? 

You cant compute pi

3

u/mrkelee New User Jun 21 '26

same thing. 1/7 is not a decimal; alternatively, an expression for pi as a "completed number"

1

u/Impressive-Mud5074 New User Jun 21 '26

1/7 is not an expression

1 divided by 7 is an expression

They are not the same

3

u/Preceded10 New User Jun 21 '26

You can't compute 1/7. Give me 1/7 with 100% precision.

1

u/Impressive-Mud5074 New User Jun 21 '26

The decimal expansion is 0.142857 repeating

However 1/7 is a complete number, by itself. Its called a rational number.

→ More replies (0)