Not all Turing-machine variants are as expressive as TM! De?ne a 100-TM to be a one-tape Turing Machine where the tape is in?nite, but the size of the tape alphabet is at most 100, and the number of states is at most 100. Show that 100-TMs are incomparable with DFAs in expressivity power, that is, show that there is a binary language (i.e. |?| = 2) that is recognizable by a 100-TM but not by a DFA, and that there is a binary language that is recognizable by a 100-TM but not by a DFA. (Note that to compare 100-TMs with other models of computation, we have restricted ourselves to binary languages, since any language with alphabet size greater than 100 cannot be recognized by a 100-TM.)