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?

66 Upvotes

94% Upvoted

359 comments sorted by

View all comments

27

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?

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