This paper explores the link between boundedly rational behavior and incomplete contracts. The bounded rationality of the agents in our world is embodied in a constraint that the contracts they write must be algorithmic in nature. We start with a definition of contract incompleteness that seems both appealing and widely applicable. Our first task is then to show that, by itself, the algorithmic nature of contracts is not enough to generate genuinely incomplete contracts in equilibrium. As in Anderlini and Felli [Q. J. Econom. 109 (1994) 1085], we call this the Approximation Result. We then proceed to consider contractual situations in which the complexity costs of a contract are explicitly taken into account. We consider a broad (axiomatically defined) class of complexity measures and in this framework we show that incomplete contracts obtain in equilibrium. We also discuss extensively some recent literature directly related to the results reported here.