<div dir="ltr">On Wed, May 21, 2014 at 7:28 AM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div class="h5"><span style="color:rgb(34,34,34)">This upper bound can be established for real computers, or any model of computation where there is a (computable) limit on the amount of storage space. A real computer has a finite amount of state (say N bits) in RAM, registers, etc.; furthermore, each "clock cycle" it deterministically transitions from one particular configuration of those N bits to another configuration (ignoring I/O, "random seed" instructions, etc.); there are only 2^N such configurations. So if it runs for 2^N + 1 cycles, at least one configuration must have been entered twice. Because the computer is deterministic, the same path that took it from the repeating configuration back to itself will now take it back to that configuration again, and again, and again, so the program is stuck in an infinite loop.</span></div>
</div></div></div></div></blockquote><div><br></div><div>There exist microcontrollers with 16 or 32 bytes of registers, and no RAM. It's enough to run your washing machine, or microwave oven.</div><div><br></div><div>
This method would be completely impractical even for such a microcontroller. Let alone anything with RAM. Or I/O.</div><div><br></div></div></div></div>