Example uncomputability proofs

• Function: NIHC( g )
• Description: NIHC returns True if its input g, a zero-input function, halts when run. NIHC returns False if g does not halt when run. NIHC stands for "zero-input halting problem."
• Note: this NIHC function exists and is well-defined as a mathematical object. After all, every zero-input function either does halt or does not halt when run! It's just that NIHC happens to be not computable.
• Strategy: We assume NIHC(g) is computable. Using it as a subroutine, we build a general-purpose haltchecker. This contradiction shows that NIHC could not exist (as a program).
• Proof: Presume NIHC(g) is computable, i.e., we can use it as a computational subroutine. Using it, we create the function M(P,w) as follows:

  def HC(P,w):
  
    def Q():
       P(w)
       return  
  
    return NIHC(Q)
  

  Note that HC is a haltchecker! There are two cases to consider: either P(w) halts or it does not.
  1. If P(w) does halt, then so does the zero-input function g. By assumption, NIHC detects this and returns True. Thus, if P(w) halts, M returns True.
  2. If P(w) runs forever, then so does g(). Again, NIHC would detect this and return False. Thus, if P(w) runs forever, HC returns false.
  Since HC returns True iff P(w) halts, HC is a haltchecker, which is a contradiction. Since everything in HC is standard except NIHC, it must be that NIHC can not exist (as a program). Thus, NIHC is uncomputable.

• Function: AIHC( g )
• Description: AIHC returns True if its input g, a one-input function, halts when run on all possible inputs. AIHC returns False if there exists one or more inputs x such that g(x) does not halt when run. AIHC stands for "all-input halting problem."
• Note: this AIHC function exists and is well-defined as a mathematical object. It's just that AIHC happens to be not computable.
• Strategy: We assume AIHC(g) is computable. Using it as a subroutine, we build a general-purpose haltchecker. This contradiction shows that AIHC could not exist (as a program).
• Proof: Presume AIHC(P) is computable, i.e., we can use it as a computational subroutine. Using it, we create the function HC(P,w) as follows:

  def HC(P,w):
  
    def Q(x):
      P(w)
      return
  
    return AIHC(Q)
  

  Note that HC is a haltchecker! There are two cases to consider: either P(w) halts or it does not.
  1. If P(w) does halt, then note that Q will halt on all possible inputs x, since Q ignores x! By assumption, AIHC detects this and returns True. Thus, if P(w) halts, M returns True.
  2. If P(w) runs forever, then so does Q(x) for all possible inputs x -- again, because x does not influence the behavior of Q. As before, AIHC would detect this and return False. Thus, if P(w) runs forever, HC returns false.
  Since HC returns True iff P(w) halts, HC is a haltchecker, which is a contradiction. Since everything in HC is standard except AIHC, it must be that AIHC can not exist (as a program). Thus, AIHC is uncomputable.

• Function: EQ(g1,g2)
• Description: EQ returns True if its inputs g1 and g2, both one-input functions, both "do the same thing" on all possible inputs. EQ returns False if g1(x) does something different from g2(x) for some input x. "Do the same thing" means that g1 and g2 either both halt (with the same return value - or the same error!) or they both run forever, when given the same input.
• Note: As before, EQ exists as a mathematical function, it just can't be computed.
• Strategy: We assume EQ(g1,g2) is computable. Using it as a subroutine, we build a general-purpose haltchecker. This contradiction shows that EQ could not exist (as a program).
• Proof: Presume EQ is computable, i.e., we can use it as a computational subroutine. Using it, we create the function M(f,inp) as follows:

  def HC(P,w):
  
    def Q1(x):
      P(w)      
      return 42   
  
    def Q2(x):
      return 42   
  
    return EQ(Q1,Q2)
  

  Note that HC is a haltchecker! There are two cases to consider: either P(w) halts or it does not.
  1. If P(w) does halt, then notice that Q1(x) does the same thing as Q2(x) for all inputs x. By assumption, EQ detects this and returns True. Thus, if P(w) halts, M returns True.
  2. If P(w) runs forever, then Q1(x) runs forever when Q2(x) halts. Again, EQ would detect this and return False. Thus, if P(w) runs forever, HC returns false.
  Since HC returns True iff P(w) halts, HC is a haltchecker, which is a contradiction. Since everything in HC is standard except EQ, it must be that EQ can not exist (as a program). Thus, EQ is uncomputable.