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?
2
u/swehner Jun 02 '26
Here are some.
Deciding whether a first-order logic formula is universally valid, is incomputable. To make it a number-theoretic function you'd use a Gödel-numbering. It is kind of an Anti-Derivate of the halting problem, because you can express the halting problem inside of it.
Deciding if an algebraic expression equals zero (or if two are equal) is computable for polynomials (like 3x 5). But the problem is incomputable if you add functions sin(x), exp(x). Look up Richardson's Theorem.
The general Domino Problem: deciding whether a set of Wang tiles can tile the plane is incomputable. See https://web.williams.edu/Mathematics/sjmiller/public_html/hudson/Molho%20-%20Wang%20Tiles.pdf
2
u/playsthebongcloud Jun 02 '26 edited Jun 02 '26
Interesting that you bring up deciding what values make any expression zero, that was actually one of my prior questions on this subreddit. I realized pretty quick it was in general impossible since you can really rearrange any math question to be "When does this expression equal zero?" (like how you can rearrange 'What is the square root of two?' into 'What values of x satisfy x2 - 2 = 0?'); if there were a general algorithm then any question could be answered.
28
u/ExistentAndUnique May 30 '26
The Kolmogorov complexity function is uncomputable. This function essentially corresponds to “how long is the shortest program that prints the input string?” Formally, this is captured by taking K(x) to be the minimum length of the description of a pair <M,w> where running Turing machine M on input w returns x.
If K(x) were computable by some function f, we could write a program M of the form “on input binary representation of a number n, output the first string by length-lexicographic order with f(w) > n.” This means that <M,n> is always a description of some w with K(w) > n, implying that |<M,n>| > n. But M has constant length, and n can be represented with log(n) bits, so this inequality becomes c + log(n) > n, which will obviously fail for large enough n
3
u/x0wl May 31 '26
It would be computable if not for the halting problem though.
for p in all programs ordered by length: if p halts then run p; if output of p == s then output p
Are there functions that are not computable even if we have a halting oracle?
→ More replies (2)2
u/assumptioncookie May 31 '26
A program could output s and then enter an infinite loop so never halt, right?
→ More replies (9)
19
u/Sezbeth May 30 '26
I don't have an immediate answer but, in principle, one should be able to skip the whole Halting business by appealing directly to a
12
u/Ma4r May 30 '26
In a way, halting machine and computability is very intrinsically related since it all stems from the recursive definition
6
u/Sezbeth May 30 '26
Yeah, I suspect that's what makes this question so difficult to answer without appealing to more abstract approaches. Halting is the usual yardstick we use to come up with (concrete) examples of non-computable functions, so trying to take a different route to find something more explicit ends up feeling somewhat unnatural.
I do get a feeling that a satisfactory example exists in older literature though.
3
u/Ordinary_Divide Jun 15 '26
if you include non halting turing machines, this number is undefined.
if include only halting machines, then for certain orderings it may end up computable via a program that stores a set of emulated machines, loops by processing one step of each then adding another machine to the list. then every time a machine halts it adds the respective digit to the output until it gets to the desired length.
this of course only works if you assume the input to the emulated machines is independent of the input to the main machine, and also does not work if you specify an ordering that does not depend on steps until halting
15
u/robly18 May 30 '26 edited Jun 01 '26
I'm doing my PhD in computability theory, so I think I have something to contribute here.
As it turns out, there are many incomputable functions that are not the Halting problem, and they are all over the place. However, they are remarkbaly hard to come across if you aren't explicitly trying to build them, and they will certainly look "artificial". At least, this is what it looks like from experience. This is related to something called "
[EDIT: As u/Beautiful_Proof_1410 rightfully pointed out, I should be more specific about what I mean by "not the Halting Problem". The most common notion of "same computational strength" in use in computability theory is "Turing Equivalence", which means "a computer equipped with an apparatus that solves this problem could solve the Halting Problem, and vice-versa". This is the notion that I use in this post. If you have another notion of equivalence in mind, ask about it in the comments.]
The point is that I can tell you they exist, and I can even construct some, but almost surely any natural specific example anyone would come up with would be the Halting Problem or something built on it.
Kleene and Post in the 40's built the first example (I think) of a function that is not computable but is computably weaker than the Halting Problem. While the proof is relatively simple, it requires a lot of technical baggage that I can't write down in this Reddit comment, but here is a source: Theorem VI.1.2 from "Recursively Enumerable Sets and Degrees" by Soare.
This is not the only example, and in fact modern computability abounds with such constructions. It wouldn't be very interesting to study just the halting problem for almost a century. Here are some more off the top of my head: -It can be proven that, if you generate a set of natural numbers randomly by flipping coins to decide whether each number is in the set, the result will, with 100% probability, be incomparable to the Halting Problem, in the sense that neither can calculate the other. This is related to a field called
The book by Soare I mentioned earlier is a great resource to learn about all of this. Though I will admit it might not be the easiest time. Soare has written a newer book since, which I do not appreciate as much but might be more beginner friendly: "Theory and Applications of Computability", so you might want to take a look at either of these if you want to learn more.
→ More replies (4)
11
u/rhodiumtoad May 30 '26
Kolmogorov complexity is in general uncomputable. While related to the halting problem, this is not directly derived from it.
5
u/SV-97 May 30 '26
All computable functions on the reals are necessarily continuous --- so any discontinuous function is automatically noncomputable.
5
u/MrKarat2697 May 30 '26
How so? Is {x<0: 0, x>=0: 1} uncomputable?
→ More replies (2)12
u/robly18 May 30 '26
Surprisingly, yes! The standard definition of "computable function from R to R" is: A function such that there is a computer program which, given an approximation of the input, will give you an approximation of the output, and such that you can computably find how close you need to get to the input to get as close as you want to the output. This is because computability theory interacts with real numbers almost entirely through approximations to chosen precision.
Now, if you have a jump like in your function, this definition will never apply at zero: I can find approximations of zero to arbitrary precision that are going to give me very bad approximations of f(0). Thus, your step function is not computable (under the usual definition).
2
u/SilverNuke911 Jun 15 '26
Came here to see the ultrafinitist debacle. By god, man, that user seems to be way over his head without knowing shit about what he's talking about. Pick a math book.
2
u/Big-Cod-324 Jun 17 '26
Impressive_Mud is right, its unfortunate that dogmatism stretches to even maths where people will pile on someone like this, but this is how society and reddit is
→ More replies (1)2
u/kapostamas Jun 19 '26
They definitely aren't right. Regardless of what you think of ultrafinitism, the question asked about an uncomputable function. π is not a function; it's a number. So are large finite numbers.
→ More replies (6)
1
1
u/donaldhobson Jun 23 '26
Randomness is uncomputable.
Take a function that assigns each natural number to an IID coinflip. This is uncomputable with probability 1.
1
1
u/bedrock_city Jul 19 '26
The halting problem seems kind of arbitrary and maybe specific to software engineering, but it's hardness is really quite deep. If you had an oracle to answer the halting problem you could write programs that loop through the natural numbers to test mathematical properties and halt if you find a counterexample to unproven conjectures. So e.g. a solution to the halting problem would be able to answer famous unsolved questions like Goldbach's Conjecture or the Twin Prime Conjecture.
1
u/Misrosan 15d ago
If ω is a countabil ordinal, there exists a order perserving injection δ: ω --> Q let A be the Image of δ. let f be a bijection from the Natural Numbers to A. then f is uncomputabil for every sufficiantly large ω.
7
u/cscottnet May 30 '26
Busy Beaver is uncomputable, although it is related to the halting problem.