Since the universe of strings over any finite alphabet is a countable set, every language can be mapped to a unique set A of natural numbers; thus, every language has a unary version {1k | k in A}.
Conversely, every unary language has a more compact binary version, the set of binary encodings of natural numbers k such that 1k is in the language.
TALLY is contained in P/poly—the class of languages that can be recognized in polynomial time given an advice function that depends only on the input length.
In this case, the required advice function is very simple—it returns a single bit for each input length k specifying whether 1k is in the language or not.
[3] The complexity class P1 is the class of the unary languages that can be recognized by a polynomial time Turing machine (given its input written in unary); it is the analogue of the class P. The analogue of NP in the unary setting is NP1.