3 ms·
It is plausible that there could be an initially 256-byte program that is self-expanding, as in, it generates more code as it runs, gradually increasing the com
by grishka 6y ago
It is plausible that there could be an initially 256-byte program that is self-expanding, as in, it generates more code as it runs, gradually increasing the complexity of whatever it's doing.
- wussboy 6y ago... you mean like our DNA?
- alcover 6y ago> increasing the complexity of whatever it's doing. I wonder if this is possible at all without external input. I'm an ignorant in Complexity Theory though.
- codeulike 6y agoYou could have something generating a sequence, say PI to infinite digits, and then 'executing' instructions based on those digits. You'd have to design the 'language' very carefully so that any errors or nonsensical series of instructions were ignored or recovered from. Some way of avoiding infinite loops. Hmmmm. It's probably not possible to guarantee that it wouldn't get stuck in a loop eventually (which would mean complexity would no longer increase). My bet is on this being impossible to continue indefinitely due to the halting problem implying that it would fall into a loop eventually.