Halting Problem
Imagine someone claims to have a program that tells whether another program halts or not
testHalt(programCode As String, data As String, answer As String)
You write a program as follows
Private Sub refuteClaim(programCode As String)
Call testHalt(programCode, programCode, ans)
testHalt(“Private Sub refuteClaim(…”, “Private Sub refuteClaim(…”, reply)
There can be no reply … “yes” implies “no”, “no” implies “yes”!
The claimed program cannot
exist since a task can be set up for it for which all outputs are logically inconsistent