just another too easy story

now posting regularly at blog.wtf.tw. see wtf.tw for marginally more coherent text.
November 2

Halting Problem

tristn:

Or rather a variation of it called “the acceptance problem”. Suppose we have a program P and we want to know that P accepts or correctly computes some input i. Let H(P,i) be a program that tells us whether a program P accepts input i. Thus:

  • H(P,i) returns true when when P accepts i.
  • H(P,i) returns false when when P does not accept i.

Let be [P] be an encoding of program P (that is, the “code” of P). Running H(P,[P]) tells us whether P accepts itself as input.

Next, let D([P]) be a program that runs H(P,[P]) as a subroutine but returns the opposite of H. Thus, D returns false when P accepts its encoding [P] as input and returns true when P does not accept itself as input.

Now, Run D([D])—that is, run D with its encoding as input:

  • D([D]) returns true when H(D,[D]) returns false and H(D,[D]) returns false when D([D]) returns false.
    • So, D([D]) returns true when D([D]) returns false.
  • D([D]) returns false when H(D,[D]) returns true and H(D,[D]) returns true when D([D]) returns true.
    • So, D([D]) returns false when D([D]) returns true.

Due to the obvious contradiction, neither programs D nor H can exist. I hope I got that right.

Also, this is hell.

Also, who cares? “What are the civilian applications?”