We investigate the capacity of energy harvesting binary symmetric channels with deterministic energy arrival process and finite battery size. Using an abstraction of the physical layer, binary symbols are transmitted. A cost function is associated with each transmitted symbol. Upper and lower bounds on the channel capacity are derived as functions of the normalized exponent of the cardinality of the set of feasible input sequences. Upper and lower bounds on the normalized exponent are established by studying supersets defined by relaxed constraints and employing a harvest-and-transmit signaling scheme, respectively. Numerical results validate that bounds on the exponent imply effective bounds on the channel capacity.