« Recovery 2.0 – A Plan | Main | Blogging Science Without a License »

May 21, 2006

The Longest Running Program – Reader Explanation

Several readers correctly specified that the algorithm for the longest running program which does, eventually, end is to use as much of available memory as possible as a gigantic counter and simply count up or down.  I tried to explain why this is the correct answer here but that didn’t end debate.  Reader Joseph Bruno commented with a much better explanation than mine which I’ll quote in its entirety below:

1. The computer is deterministic.

2. So its next state depends on its current state and on nothing else.

3. And a given current state can only ever turn into one "next" state.

[you can't disprove this with an "up and down" counter: when it is counting up the state is {n,UP} and when it is counting down the state is {n,DOWN}, which are two different states - so the total is N+1 bits of state, N in the counter and 1 in the "UP/DOWN" setting].

4. So the longest program is the one that goes through the most states, once each.

5. N bits of memory can have 2**N possible states.

6. So the longest program cannot have more than 2**N possible states.

7. A counter can have 2**N possible states.

8. So no program can take longer than the simple N-bit counter.

Each byte of program code subtracts 8 bits from the space available for the counter. So each byte of program reduces the running time by a factor of 256, which makes programmatic cleverness very unlikely to be useful.

Using the registers would be useful if you can do this in less than 4 bytes of code (less than 8 bytes, for a 64-bit computer). For instance,
XXX: INC AX
JNZ XXX
takes only 3 bytes but lengthens the effective "counter" by 4 bytes.

Good explanation, huh?  Can’t resist a clarification and a note though.

Implied but not stated by his explanation is the fact that, if the computer ever reaches a state it has previously been in, it is in a loop.  Why?  Because, as he says in #2 and #3 above, each state consistently determines one and only one successor state.  So if State A leads to State B…. leads to State A the whole sequence will repeat ad infinitum and not be a valid solution to the puzzle.  Therefore each state can only be entered once.  Counting either up or down assures that all states are entered.

Several readers did point out that different instructions execute at different speeds.  So, all else being equal, a program that counts more slowly will run longer.  But, BIG but, all else being equal definitely includes the amount of memory occupied by the program.  Each bit used by the program is a bit NOT available for the counter.  Each extra bit in the counter makes the program run twice as long because it doubles the number of possible states.

Because program size in memory is so critical, the best algorithms obviously can’t be written in a higher level language but must be in the machine language of the target computer.  Moreover, a clever program will find a way to overwrite its own initialization code with part of the counter.

| Comments (View)

Recent Posts

Facts are Stranger than Fiction

Negotiators Can’t (Appear to Be) Afraid of No Deal

“There Are No Facts About the Future”

The US Should NOT Lead the Effort to Protect the Straits of Hormuz

Stopping Climate Change Would Be an Unnatural Act

TrackBack

TrackBack URL for this entry:
https://www.typepad.com/services/trackback/6a00d83451cce569e200d8352ce2e053ef

Listed below are links to weblogs that reference The Longest Running Program – Reader Explanation:

Comments

blog comments powered by Disqus
Blog powered by TypePad
Member since 01/2005