This is a very well-written essay which explains its computing concepts effectively and thoroughly. I upvoted.

However, the bit at the end with the balanced parentheses matchers being a bad interview question seems to be missing the forest for the trees. A simple solution to this problem which has nothing to do with any of the computational theory discussed:

   def is_balanced_parens(s):
       nesting_depth = 0
       contains_nesting = False

       for c in s:
           if c == '(':
               nesting_depth += 1
               contains_nesting = True
           elif c == ')':
               nesting_depth -= 1
           else:
               return False

           if nesting_depth < 0:
               return False

       return contains_nesting and nesting_depth == 0

This isn't that hard of a problem, and if an interview candidate couldn't come up with a basic solution like this, I'd very much like to know that.