Turbo recognition (TR) is an approach to layout analysis of scanned document images inspired by turbo decoding from communication theory. The TR algorithm is based on a generative model of image production in which two regular grammars simultaneously describe structure in horizontal and vertical directions. The TR model thus embodies non-local constraints while retaining many of the features of local statistical methods. This grammatical basis allows TR to be quickly retargeted to new domains. While TR, like turbo decoding, is not guaranteed to recover the statistically optimal solution, we present experimental evidence of its ability to produce near-optimal results for a non-trivial synthetic problem. We explore the expressiveness of TR for describing abstract structure in two dimensions, and develop a hierarchy of grammars of increasing complexity. We demonstrate the application of the TR framework to the analysis of simple text documents. We discuss how TR can be applied to the analysis of composite documents and images corrupted with extreme amounts of noise, and show how it can be applied to problems such as the layout analysis of journal article title pages.