In this paper we consider the problem of binary hypothesis testing with\nfinite memory systems. Let $X_1,X_2,\\ldots$ be a sequence of independent\nidentically distributed Bernoulli random variables, with expectation $p$ under\n$\\mathcal{H}_0$ and $q$ under $\\mathcal{H}_1$. Consider a finite-memory\ndeterministic machine with $S$ states that updates its state $M_n \\in\n\\{1,2,\\ldots,S\\}$ at each time according to the rule $M_n = f(M_{n-1},X_n)$,\nwhere $f$ is a deterministic time-invariant function. Assume that we let the\nprocess run for a very long time ($n\\rightarrow \\infty)$, and then make our\ndecision according to some mapping from the state space to the hypothesis\nspace. The main contribution of this paper is a lower bound on the Bayes error\nprobability $P_e$ of any such machine. In particular, our findings show that\nthe ratio between the maximal exponential decay rate of $P_e$ with $S$ for a\ndeterministic machine and for a randomized one, can become unbounded,\ncomplementing a result by Hellman.\n