I study how limited abilities to process information affect choice behavior. I model the decision-making process by an automaton, and measure the complexity of a specific choice rule by the minimal number of states an automaton implementing the rule uses to process information. I establish that any choice rule that is less complicated than utility maximization displays framing effects. I then prove that choice rules that result from an optimal trade-off between maximizing utility and minimizing complexity are history-dependent satisficing procedures that display primacy and recency effects.