  It is commonly accepted that machine translation is a more complex task than
part of speech tagging. But how much more complex? In this paper we make an
attempt to develop a general framework and methodology for computing the
informational and/or processing complexity of NLP applications and tasks. We
define a universal framework akin to a Turning Machine that attempts to fit
(most) NLP tasks into one paradigm. We calculate the complexities of various
NLP tasks using measures of Shannon Entropy, and compare `simple' ones such as
part of speech tagging to `complex' ones such as machine translation. This
paper provides a first, though far from perfect, attempt to quantify NLP tasks
under a uniform paradigm. We point out current deficiencies and suggest some
avenues for fruitful research.
