If M does not halt, then R(a n ) ≤ 1 1+e 2(n+1) ≤ 1 1+e 2 < 0.12 for all n ∈ N. On the other hand, if M halts after T steps, then using Lemma 14 in the appendix.
a string with weight above 0.12 exists if and only if M halts, so the best string problem is also undecidable.