Given a machine U, a c-short program for x is a string p such that U(p)=x and the length of p is bounded by c + (the length of a shortest program for x). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>