Here is a bit of mathematical logic for you - an accessible presentation of Turing's proof that the halting problem ("will a given computer program with a given input stop") is undecidable. It's just a proof by contradiction, with a recursive aspect similar to the work of Godel.
To try to simplify his already simple explanation, assume we can identify when a program would halt and consider a program P that loops forever when fed somethings that halts and exits otherwise. Then, feed P to itself - for it to stop, it would have to loop forever, and vice-versa. Contradiction, therefore we cannot identify when a program would halt.
If you want a fuller explanation, read the linked resource. As an aside, the copyright notice at the top of it is a little unsettling, but I decided to share it nonetheless as it is well written. But for reference, all works are implicitly copyrighted, and in my book if you're going to make an explicit declaration regarding intellectual property you're best off choosing some sort of "libre" license (but still retaining your copyright of course).
No comments:
Post a Comment