Example uncomputability proofs

• Function: zinph( g )
• Description: zinph returns True if its input g, a zero-input function, halts when run. zinph returns False if g does not halt when run. zinph stands for "zero-input halting problem."
• Note: this zinph 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 zinph happens to be not computable.
• Strategy: We assume zinph(g) is computable. Using it as a subroutine, we build a general-purpose haltchecker. This contradiction shows that zinph could not exist (as a program).
• Proof: Presume zinph(g) is computable, i.e., we can use it as a computational subroutine. Using it, we create the function M(f,inp) as follows:

  def M(f,inp):
  
    def g():
      y = f(inp)  # run f on inp
      return 42   # this line is not really important
  
    return zinph(g)
  

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

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

  def M(f,inp):
  
    def g(x):
      y = f(inp)  # run f on inp
      return 42   # this line is not really important
  
    return ainph(g)
  

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

• Function: autograder(g1,g2)
• Description: autograder returns True if its inputs g1 and g2, both one-input functions, both "do the same thing" on all possible inputs. autograder 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, autograder exists as a mathematical function, it just can't be computed.
• Strategy: We assume autograder(g1,g2) is computable. Using it as a subroutine, we build a general-purpose haltchecker. This contradiction shows that autograder could not exist (as a program).
• Proof: Presume autograder is computable, i.e., we can use it as a computational subroutine. Using it, we create the function M(f,inp) as follows:

  def M(f,inp):
  
    def g1(x):
      y = f(inp)  # run f on inp
      return 42   # this line now IS important
  
    def g2(x):
      return 42   # this line is also important
  
    return autograder(g1,g2)
  

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