In order to understand what the measure μ that was constructed from d will reward, here’s the sort of machine that comes close to supMμ(M)=3:
Let M0 be an arbitrary UTM. Now consider the function r(n)=n−2⌊lgn⌋ (or, really, any function r:N+→N0 with r(n)<n that visits every nonnegative integer infinitely many times), and let L={x∈{0,1}∗:|x|>2,x|x|−1=xr(|x|−1),x|x|−2=xr(|x|−2)}. (The indices here are zero-based.) Choose x0∈L such that x0 has no proper prefix in L. Then, construct the UTM M that does:
repeat:
s := ""
while s not in L:
# if there is no next character, halt
s := s + readchar()
if s == x0:
break
M0()
This M will have μ(M)>3−2−|x0|+d(M0,M)2−|x0|−d(M0,M).
M here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to “encode” from the UTMs it efficiently encodes, using at most 2 bits (an average of 1+√52). This is somewhat interesting, but clearly doesn’t capture the kind of computational expressivity we’re primarily interested in.
In order to understand what the measure μ that was constructed from d will reward, here’s the sort of machine that comes close to supMμ(M)=3:
Let M0 be an arbitrary UTM. Now consider the function r(n)=n−2⌊lgn⌋ (or, really, any function r:N+→N0 with r(n)<n that visits every nonnegative integer infinitely many times), and let L={x∈{0,1}∗:|x|>2,x|x|−1=xr(|x|−1),x|x|−2=xr(|x|−2)}. (The indices here are zero-based.) Choose x0∈L such that x0 has no proper prefix in L. Then, construct the UTM M that does:
This M will have μ(M)>3−2−|x0|+d(M0,M)2−|x0|−d(M0,M).
M here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to “encode” from the UTMs it efficiently encodes, using at most 2 bits (an average of 1+√52). This is somewhat interesting, but clearly doesn’t capture the kind of computational expressivity we’re primarily interested in.