I thought about it a while back when it came up in my studies, and in this case I think it's easy to make the argument that it exists (some shortest program+inp

I thought about it a while back when it came up in my studies, and in this case I think it's easy to make the argument that it exists (some shortest program+input P+I that produces a given finite-length string S), but not computable. Programs + Input in the K-complexity world are sequences of symbols taken from a finite alphabet. For any finite-length S, we can definitely find a program Q that produces S: Simply write the program that literally embeds and reproduces S. Now, Q is a program+input that has finite length. So we can always find a maximal bound for the K-complexity (length of Q). Since Q is a finite-length symbol sequence from a finite alphabet, we can consider the finite-sized subset of all symbol-sequences of length <= Q. Every single one of those sequences describes a program + input. Every one of those programs is deterministic: it will either run to completion and produce some fixed output, or never-terminate. We know the finite upper bound exists. We know the finite set of Program+Input sequences exist. We can even enumerate all of them (and write a program to do it). We also know that each of them will deterministically either produce S or not produce S (we can't be guaranteed that we will run them all and find the results of each, but we know each of them have an intrinsic and deterministic behaviour). Either one or more of those will produce S or not. If there are none, then our candidate Q is the shortest. If there are one or more, then the shortest of those definitely exists, since we already have the finite set it comes from in our hand. Overall, this and other cases (Godel's work, Halting Problem) lead me down the path of accepting the mathematical truth that it's possible for there to be truths we never "reach". Truth and knowability are linked, but knowability is not a prerequisite for truth. It wasn't an easy idea to come to terms with, but I'm relatively comfortable with it these days.