
Here is an example proof (using words, instead of
pictures) that RC, a regularity checker, is uncomputable.

Let RC(M) be a function of turing machines.
RC is (purportedly) a _regularity checker_:
 * RC outputs "True" if M is a TM that accepts a regular language.
 * RC outputs "False" if M is a TM that does not accept a regular language.

**** Intuition-building on what RC is claiming ****

Since a TM is equivalent to a function of a single string input,
we can write a couple of TMs as follows:

def TM1(s):
  if s == "101010": return True
  else: return False

The language TM1 accepts is { "101010" }, which is regular.

Thus, RC(TM1) returns "True"


Here's another TM:

def TM2(s):
  if len(s) > 0 and s[0] == "1": return True
  else: return False

The language TM2 accepts is expressed by the r.e. 1(0|1)*
Thus, the language that TM2 accepts is regular.

Thus, RC(TM2) returns "True"


Here's a third TM (in pseudocode):

def TM3(s):
  if s is a string of zeros whose length is
     a power of two: return True
  else: return False

The language TM3 accepts is NOT regular.
Thus, RC(TM3) returns "False"

** RC(M) claims to answer "True" and "False" correctly for any M **

** That is, RC claims to known whether any input machine M
            accepts a regular language or not               **

**** end of intuition-building on what RC is claiming ****







PROOF that RC(M) can not exist, i.e., RC is uncomputable:

We proceed by contradiction.
Suppose RC(M) does exist and it works as it claims.
We show a contradiction by building a haltchecker.





Define the following function named fun.
It takes two inputs, a function P and a string w.

def fun(P,w):
  def TM4(s):
    P(w)
    return TM3(s) # using TM3, above

  regularity = RC(TM4)
  stops = not regularity
  return stops

The above function, fun, is completely OK (as long as
RC is a legitimate subroutine). HOWEVER, notice that

when P(w) halts, then
  (1) TM4 accepts a NONregular language (because of TM3)
  (2) the value of regularity == "False"
      -> because we're trusting RC
  (3) the value of stops == "True"
  (4) fun thus returns True

when P(w) never halts, then
  (1a) TM4 accepts no strings
  (1b) TM4 accepts a regular language! {} is regular!
  (2)  the value of regularity == "True"
       -> because we're trusting RC
  (3)  the value of stops == "False"
  (4)  fun thus returns False
      



Notice again the start and finish of these two statements:

when P(w) halts, then fun returns True
when P(w) never halts, then fun returns False

Thus, fun is a working haltchecker!




We know that haltcheckers cannot exist -- thus, our subroutine
RC (which enabled us to build this haltchecker) cannot exist.

Thus, RC is uncomputable.








