Saturday, August 18, 2007

All Programs are Perfect: The Proof

Lets assume that there is an imperfect program. This leaves us with 2 cases:

A) The program has a reparable flaw
  1. If this is the case then there must be some way to repair the flaw.
  2. The only way to repair any flaw in the program is to modify the code.
  3. Having modified the code, you have effectively created a new program.
  4. Therefore it is impossible to have a correctable flaw in a program, because the program effectively ceases to be once corrected.
B) The program has an irreparable flaw
  1. If this is the case, then no correction will make the program perfect.
  2. Thus you can make an infinite number of changes to the program and it still will not be perfect.
  3. The set of all programs resulting from changing any given program an infinite number of times must be the set of all possible programs.
  4. This would imply that all possible programs exhibit flaws.
  5. There exists a turing machine for which there is a zero-byte program that does nothing.
  6. This is inherently a perfect implementation of a program which does nothing and uses no resources.
  7. Therefore statement 4 must be false
I'll talk about what this means later

0 comments: