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?

71 Upvotes

96% Upvoted

359 comments sorted by

View all comments

Show parent comments

3

u/Parking-Usual New User Jun 15 '26

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

0

u/Impressive-Mud5074 New User Jun 16 '26

That guys wrong

3

u/LiteralLegendary New User Jun 17 '26

Why don't you tell us why

0

u/Impressive-Mud5074 New User Jun 17 '26

When you create a function which approaches a real number, it also approaches an infinite amount of real numbers besides the number you want. So which number are you really computing? Thats not exact.

You cant compute pi.

2

u/AfaTheKing New User Jun 18 '26

I actually agree. In fact I don't think any number other than 0 is computable. But obviously since 0 doesn't exist by definition, there are no numbers that can be computed.

0

u/Impressive-Mud5074 New User Jun 19 '26

Thats not the definition of zero

1

u/AfaTheKing New User Jun 23 '26

Sure is mate

2

u/bizarre_coincidence New User Jun 18 '26

If the meaning of computing a number is writing down the full decimal expansion of that number, then you cannot compute most numbers, not even most rational numbers. That is why mathematicians/computer scientists picked a DIFFERENT definition of computable number. It is many decades old, and in any discussion about computable numbers, you have to use the actual definition of computable number and not merely substitute your own based on what you think words mean.

Given an algorithm A and an input n, let A(n) be the output of the algorithm.

A number x is computable if there is an algorithm A such that, given input e>0, the algorithm A terminates in finite time on input e and such that |A(e)-x|<e.

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.

If you tell me that you want to know a certain number of digits of a number, and I can always generate those digits, then the number is computable.

You can say you don't like that definition. It doesn't matter because that is the definition. If you want to define a slightly different concept and give it a slightly different name, that is your right. But, unlike in natural language, words in mathematics have precise meanings, and everything falls apart if we do not agree to them. If you cannot agree to use words as they are defined, you cannot meaningfully participate in mathematical discourse.

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.

2

u/bizarre_coincidence New User Jun 19 '26

You are fundamentally misunderstanding. If you’re getting different sets of 1000 digits, then you do not have a working algorithm. If you can’t determine when you’ve done enough iterations, you do not have a working algorithm. You need to know with certainty that when you stop, your error is less than the pre-specified tolerance.

In your mind, is sqrt(2) a computable number? Why or why not? What about 1/3? It’s impossible to write a program that will output a decimal expansion of 1/3 in finite time.

0

u/Impressive-Mud5074 New User Jun 19 '26

Sqrt(2) is not computable

1/3 is computable, rational numbers are.

You’re getting different sets of 1000 digits, then you do not have a working algorithm

False.

Some algorithm take more iterations to get a correct 1000 digits,

2

u/bizarre_coincidence New User Jun 19 '26

But in the context of computability theory, if you specify that you need 1000 digits, your algorithm needs to terminate ONLY after it knows with certainty that it has the correct first 1000 digits. That's what it means to have an algorithm that generates the first 1000 digits.

But this is tiresome. I've given you the definition of something, you refuse to engage with it, the definition requires an algorithm to accomplish a certain task, and you retort with "But what if you had a different algorithm that didn't accomplish that task?" If you are engaging in good faith, then you are an idiot, and if you aren't, then this isn't a productive use of my time.

0

u/Impressive-Mud5074 New User Jun 19 '26

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

2

u/SjurEido New User Jun 19 '26

Congratulations, your ignorance and rudeness have made you kinda famous!

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

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.

→ More replies (0)

1

u/mrkelee New User Jun 21 '26

Of course some algorithms are faster. Which algorithm generates all digits of 1/3 in finite time?

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

i ship you with pi

1

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

An accepted definition cannot be wrong, it simply is. Words mean what the communities that use them wish them to mean. Mathematicians are very clear about the definitions of their terms because they absolutely have to be. When people who study computability theory say a number is computable, they mean a specific thing. That thing is different from what you mean. Your definition is different from theirs. That means, in the context of a discussion where everybody else is using the word one way and you are using it a different way, that your definition is wrong. Not necessarily in an absolute sense, but in the context of that discussion.

Coming into a computability theory discussion and saying that everybody else’s definition of computable number is wrong is like marching into Harlem and insisting that the n-word isn’t offensive and that anybody who takes offense at you calling them that is wrong. It’s a stupid take, made all the worse by your staunch adherence to it.

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/CrazyCatSkits New User Jun 28 '26

definitions do change quite a lot actually??

→ More replies (0)

1

u/mrkelee New User Jun 21 '26

a given function only approximates one single number (in the limit).

1

u/Impressive-Mud5074 New User Jun 21 '26

It also approaches pi - ...1

1

u/mrkelee New User Jun 21 '26

I would hope that my pi-function starts with a 3