
<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">John Tromp via e-mail has kindly called my attention to the following:<div class=""><br class=""></div><div class=""><blockquote type="cite" class="">in your recent post to the Cryptography List, you asked<br class="">"how many bits are needed to define the smallest UTM?"<br class=""><br class="">My page <a href="http://tromp.github.io/cl/cl.html" class="">http://tromp.github.io/cl/cl.html</a><br class="">argues that it is upper bounded by 29 bytes.<br class="">Also see <a href="http://www.ioccc.org/2012/tromp/hint.html" class="">http://www.ioccc.org/2012/tromp/hint.html</a></blockquote>...</div><div class=""><blockquote type="cite" class="">this is the smallest encoding I know of, of a universal machine<br class="">that does all the work of parsing a description of some machine/term and<br class="">then simulating the behaviour of that machine/term on the remainder of<br class="">the input.</blockquote><br class=""></div><div class="">29 bytes is 232 bits, more than the key size of AES-128 and a little less than for AES-256. Of course this is not a lower bound, but it does support the notion that block ciphers with keys in that range are unlikely to contain a hidden Turing machine.</div><div class=""><br class=""></div><div class="">Also in my most recent post where I tried to show that a search for the most efficient algorithm to break a given block cipher is finite, I neglected to mention that the running time for each candidate algorithm can be limited to the maximum time for a brute force search, since we don’t care about algorithms which take longer.</div><div class=""><br class=""></div><div class="">Arnold Reinhold</div></body></html>