Chapter 6: Computing with Infinite State
Peter M. Kogge · Society for Industrial and Applied Mathematics eBooks · 2022
The prior chapter focused on automata where the number of state values was limited, and exactly one state value—the prior one—is part of the decision process for the next one. This chapter discusses automata where the second constraint is lifted and a potentially unbounded amount of information from prior steps is kept available. The first of these models, a push-down automaton (PDA) assumes an NFA with a potentially unbounded stack as an auxiliary memory. The second of these models, the Turing machine (TM), is allowed to both read and write to its input tape, and move freely in either direction on that tape. The TM model has proved to be able to perform the same computations as any supercomputer in existence today, albeit slower, and is the basis for our current understanding of “What is computable?” (see Chapter 7).