You seem to have go it, the suggestion seems is to search all possible programs sorted by length.

"Start with the shortest program", a null instruction, which does not meet the criteria, "and complexity it iteratively" by appending new instruction in a breadth first manner "spanning a tree of all possible program."

You're correct that the first program that this search finds will satisfy K(X, T) but may not satisfy KT or kST.