Relationship between message entropy and complexity of the best algorithm
I believe you are looking for algorithmic information theory.  This defines the information contained in a string as proportional to the size of the smallest program that produces that string.  The metric is called Kolmogorov (Колмогоров) complexity.

The problem with normal Shannon entropy, is that it is defined relative to your assumed model of the producer of the information stream.  Shannon entropy really only deals with models that produce infinite and stationary random streams.  When you know that the producer is deterministic then the Shannon entropy of the stream is 0 (even though you don't know the algorithm of the producer.)  You can often model a deterministic stream as some kind of Markov process, but there will always be a Markov process with more states that models the deterministic stream and in which the entropy is smaller.