5 ms·

Suppose we have a human-written program that's N-bits long. It takes an input, and generates an infinite output by performing some hashing of the input. We run

Suppose we have a human-written program that's N-bits long. It takes an input, and generates an infinite output by performing some hashing of the input. We run it on an M-bit input to get some output, then stop it manually. Now suppose we have an input and the output made by this program. But we don't have the program. Suppose we want to discover by brute force what the program was. The brute-force algorithm will create every possible program up to N bits long, and run each one until either a difference in outputs is found, or it found the correct output, or too much time has passed. How do you come up with the order-notation for this brute-force algorithm?

umanwizard 13y ago
Since you're bounding (with a constant) the time each iteration can take, this is just O(2^n). EDIT: I suppose if the time bound per program is a parameter "m" that you can vary, then it's actually O(m*2^n). Without the bound, this algorithm is unlikely to work, since programs can run indefinitely. If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.
- gizmo686 13y ago
  >If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible. Nonsense, there is no reason you cannot design an algorithm that uses a halting oracle. Running that algorithm may be difficult though.
- reitzensteinm 13y ago
  I'm sure you know this, but I'd just like to clarify something: You absolutely can generate only programs that terminate; for instance, throw out any that have recursion or unbounded loops, or use a non Turing complete language that is guaranteed to terminate. That you can't solve the halting problem in general does not mean that static analysis is fruitless. The answer to "does this terminate" will be yes, no or maybe, almost always in the latter category. The correct thing to say would be: If you modify your algorithm to only generate programs without infinite loops, you've most likely thrown out the correct solution.
GuiA 13y ago
I'm confused. Why is the output infinite? Do we know when the hashing was stopped? I'm not sure this is a decidable problem with just the information you gave. Did you just make up the problem, or is that inspired from a real world situation?
- xjtian 13y ago
  The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the number of programs up to N bits long is 2^(N+1) - 1.
scardine 13y ago
O(2^n) where n is the number of bits?
cscheid 13y ago
In a tangential note, if P=NP, a sufficiently carefully crafted algorithm very much like that suffices to solve any NP complete problem in polynomial time! (Of course the constants are ridiculously, absurdly large) http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessity-of-enumerating-all-programs/ http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessit...

umanwizard 13y ago

Since you're bounding (with a constant) the time each iteration can take, this is just O(2^n). EDIT: I suppose if the time bound per program is a parameter "m" that you can vary, then it's actually O(m*2^n). Without the bound, this algorithm is unlikely to work, since programs can run indefinitely. If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.

gizmo686 13y ago
>If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible. Nonsense, there is no reason you cannot design an algorithm that uses a halting oracle. Running that algorithm may be difficult though.
reitzensteinm 13y ago
I'm sure you know this, but I'd just like to clarify something: You absolutely can generate only programs that terminate; for instance, throw out any that have recursion or unbounded loops, or use a non Turing complete language that is guaranteed to terminate. That you can't solve the halting problem in general does not mean that static analysis is fruitless. The answer to "does this terminate" will be yes, no or maybe, almost always in the latter category. The correct thing to say would be: If you modify your algorithm to only generate programs without infinite loops, you've most likely thrown out the correct solution.

GuiA 13y ago

I'm confused. Why is the output infinite? Do we know when the hashing was stopped? I'm not sure this is a decidable problem with just the information you gave. Did you just make up the problem, or is that inspired from a real world situation?

xjtian 13y ago
The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the number of programs up to N bits long is 2^(N+1) - 1.

scardine 13y ago

O(2^n) where n is the number of bits?

cscheid 13y ago

In a tangential note, if P=NP, a sufficiently carefully crafted algorithm very much like that suffices to solve any NP complete problem in polynomial time! (Of course the constants are ridiculously, absurdly large) http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessity-of-enumerating-all-programs/ http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessit...