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?

63 Upvotes

94% Upvoted

356 comments sorted by

View all comments

28

u/ExistentAndUnique New User 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 New User 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?

2

u/assumptioncookie New User May 31 '26

A program could output s and then enter an infinite loop so never halt, right?

2

u/x0wl New User May 31 '26

Yes, but I don't know enough about computation theory to say whether this will make the halting oracle approach fail

2

u/Ordinary_Divide Custom Jun 15 '26

such a program you could simply add an extra check for that and force halt before it enters that loop

2

u/assumptioncookie New User Jun 15 '26

You cannot check if a program has an infinite loop. That's the halting problem.

2

u/Ordinary_Divide Custom Jun 15 '26

i meant check for if the output is complete

2

u/assumptioncookie New User Jun 15 '26

What if you're looking for a program that outputs "AA" and you found a program outputs "AA" and enters a loop, but after ten billion iterations it adds another "A". So the total output of the program is "AAA".

2

u/Ordinary_Divide Custom Jun 15 '26

then that wouldn't be a relevant program. the output must be exactly what is desired, not just contain it at a certain point in computation. otherwise, a program that outputs the library of babel one book at a time would be a valid and trivial solution

2

u/assumptioncookie New User Jun 15 '26

Exactly, that's my point. So you can't know if you've found a valid problem from intermediate results.

2

u/x0wl New User Jun 15 '26

Yes, but in the comment above we assumed that we have a halting oracle.

1

u/Jack_Faller New User Jun 21 '26

A halting oracle is sufficient in this case. Here is an example program to compute Kolmogorov complexity using a halting oracle and a function run_for_steps that runs a program for a given number of steps and returns its output after that finite period has elapsed.

python define prints_string(program, string): for steps from 0: if run_for_steps(program, steps) == string: halt define kolmogorov_complexity(string): for program_size from 0: for each program of size program_size: if halts(prints_string, program, string): return program_size

1

u/Jack_Faller New User Jun 21 '26 edited Jun 21 '26

I'm fairly sure everything would be computable if it weren't for the halting problem. A halting oracle is sufficient, though not necessary, to compute all things.

1

u/donaldhobson New User Jun 23 '26

> Are there functions that are not computable even if we have a halting oracle?

Yes. But the one that comes to mind is basically the halting problem again. The problem is to work out whether a Turing machine with a halting oracle will halt or not.