<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, May 20, 2014 at 6:19 PM, Bruce Hoult <span dir="ltr"><<a href="mailto:bruce@hoult.org" target="_blank">bruce@hoult.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="">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><div class="gmail_extra"><div class="gmail_quote"><div class="">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">
<div><div><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><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></div></div>
</blockquote><div><br></div><div>Yup. Tiny ones like that are usually mask-programmed or one-time programmable, so unfortunately there's no use desoldering them from broken items and keeping them around to reuse in projects. Just have to throw them away :(</div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">
<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>
</blockquote></div><br></div><div class="gmail_extra">Yes, that's what I said in the next paragraph. The importance of this observation is not the practicality: it's that the nature of the difficulty changes radically, from "provably impossible to do, AT ALL" to "we know at least that there is an obvious extremely slow and naive algorithm for the general case, but the door is open for improvements".</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Just to play devil's advocate against your claim "would be completely impractical even for such a microcontroller", I'll give you another situation where you theoretically have to deal with 2^N configurations (states), but on many kinds of typical practical inputs the result is quite manageable: the power set construction, where an NFA with N states is turned into a DFA with (worst case) 2^N states.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">-- Sean Silva</div></div>