2 ms·

There's also a simple algorithm to compute K(s) for any particular s (and thus for any finite set of such inputs). Enumerate every possible Turing machine by in

There's also a simple algorithm to compute K(s) for any particular s (and thus for any finite set of such inputs). Enumerate every possible Turing machine by increasing length until one that outputs s is found. Since you've tried all shorter machines, and they didn't output s, you've found the shortest machine that outputs s and thus its length is K(s). Other machines of the same or greater length may exist which output s, but since K(s) is just about the minimal length this doesn't change anything. For all strings with length <n, you just repeat the brute-force for every one of the 2^n strings. It's a finite process!

hyeoniuwu 2y ago
This is incorrect. The problem is that you won't be able to tell if certain small Turing machines halt to give s, or loop forever. (So, if you are dovetailing through every possible Turing machine, the first one to output s may not be the minimal one. If you are not dovetailing, your search procedure will not halt, as you'll become stuck enumerating a Turing machine which does not halt.) (Besides, that there is an "algorithm to compute K(s) for any particular s" directly contradicts the non-computability of K(s).)