Author |
Topic: CS: New Problem: Longest Terminating Program (Read 2952 times) |
|
Yournamehere
Guest
|
 |
CS: New Problem: Longest Terminating Program
« on: Aug 24th, 2002, 8:06pm » |
 Quote  Modify
 Remove
|
An easy problem:
Given a computer with 8k bytes of memory (RAM), and an execution speed of 1 billion (10**9) instructions per second, what is the longest terminating program (in terms of execution time) which can run on the machine? "Terminating" means that the program is guaranteed to execute some HALT instruction.
The desired solution is simply a "back of the envelope" estimate. The exact answer, of course, depends on details such as exactly what the instruction set looks like, and so forth. Feel free to make reasonable assumptions, where necessary.
|
|
 IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: CS: New Problem: Longest Terminating Program
« Reply #1 on: Aug 26th, 2002, 1:55pm » |
Quote Modify
|
For my estimate here, I am not going to consider programs that can modify themselves, as it is just too mind-boggling. So, say that part of the memory is for instructions and the rest is for data.
I'd think of the program in terms of the discrete states of the computer's memory. If the program halts, then it must not get into an infinite loop, therefore it can never be in a state that it was in before.
So how many possible states are there for the computer's memory? 8 kilobytes is 64,000 bits, so there are 264000 distinct states. Now the program will take up some memory, so the distinct states of the data memory during the run of this program will be somewhat smaller.
I'd imagine the longest running program something like a small program that uses the rest of memory as a massive counter, and halts when it has counted through all possible values.
Just to be simple and conservative, assume we need 1 instruction to increment the counter by 1, on average. We're talking roughly 264000 instructions to execute then.
(264000 has about 64000*log10(2) zeroes, or about 19,265 zeroes.)
So, executing a billion instructions per second, it runs for about 1019256 seconds.
|
| « Last Edit: Aug 26th, 2002, 2:00pm by S. Owen » |
IP Logged |
|
|
|
Yossarian
Guest
|
|
Re: CS: New Problem: Longest Terminating Program
« Reply #2 on: Sep 11th, 2002, 5:00am » |
Quote Modify
Remove
|
This calculation is correct assuming that this computer has no means to input data. Otherwise it can run as long as needed.
Also S. Owen's calculations are also valid for self-modificating
programs. There are exactly 2^64000 different states,
and it does not matter if they are parts of program or data.
Some part of the program can change, others should remain
the same.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: CS: New Problem: Longest Terminating Program
« Reply #3 on: Sep 12th, 2002, 12:54pm » |
Quote Modify
Remove
|
on Sep 11th, 2002, 5:00am, Yossarian wrote:This calculation is correct assuming that this computer has no means to input data. Otherwise it can run as long as needed.
|
|
This is essentially covered in the definition of "teminating". That is, any program which looks to its input in order to return to some already visited state is not guaranteed to reach the halt instruction, since there is then some input which results in an infinite loop. Such a program is not "terminating".
|
|
IP Logged |
|
|
|
David Madison
Guest
|
|
Re: CS: New Problem: Longest Terminating Program
« Reply #4 on: Sep 18th, 2002, 6:34pm » |
Quote Modify
Remove
|
on Sep 11th, 2002, 5:00am, Yossarian wrote:Also S. Owen's calculations are also valid for self-modificating
programs. There are exactly 2^64000 different states,
and it does not matter if they are parts of program or data.
|
|
Not quite.
If it's self-modifying, then you need to consider the PC (program counter) as part of the state, and it can take 8k values if you allow for instructions to be byte-aligned, so multiply that times your states.
And arguably you'd need to consider all the rest of the state of the processor as well, such as register contents and whatnot..
Now even more difficult, write the program that can take all those states. 
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: CS: New Problem: Longest Terminating Program
« Reply #5 on: Sep 18th, 2002, 8:00pm » |
Quote Modify
|
Agreed - I guess I was considering the PC and any other registers as included in the 64k, but if not, absolutely, that is state also.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: CS: New Problem: Longest Terminating Program
« Reply #6 on: May 30th, 2004, 2:06pm » |
Quote Modify
|
The simplest way to make sure all states are used is to make a big counter with all the available memory.
The only valid optimization is to make the program as short as possible to leave the maximum of memory. If you can save a single byte of code, you can multiply the run time by 256!
Here is a program in some pseudo assembler.
Code:start:
inner:
load ptr, memory
outer:
inc [ptr]
if( [ptr]!=0 ) jmp inner
inc ptr
if( ptr<end ) jmp outer
halt
data:
as many zero bytes as available
end:
the first non-valid address |
|
|
| « Last Edit: May 30th, 2004, 2:11pm by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print