We're allowed an unlimited amount of paper, but each piece has a finite size, and hence each piece is in one of only finitely-many distinguishable states. Turin

We're allowed an unlimited amount of paper, but each piece has a finite size, and hence each piece is in one of only finitely-many distinguishable states. Turing called these piece-of-paper-states "symbols", and arranged the pieces of paper in a "tape" of unlimited length (a stack of sheets, or a library of books would also work; but moving between the pieces would be more complicated). In fact, we only ever need 2 symbols, e.g. 0 and 1. This is because any set of symbols can be replaced by a set of numbers, and those numbers can be written in binary (with a fixed width, to avoid needing 'spacers'). This can require a lot more machine states, since those states allow the machine to 'remember' the bits it's read so far (e.g. if we're using 8 bits at a time, then we need enough states to "remember" what the first 7 bits were as we're reading the 8th). For a calculation like pi, we can use the tape to (a) write down the digits (or bits) of pi, and (b) keep track of intermediate variables needed for the calculation. One simple approach to keeping track of intermediate variables is to store them in order on the tape, where each variable is a sequence of 1 symbols, separated by 0 symbols. For example a tape like: 111010010 represents four variables with values 3, 1, 0 and 1 (the number of 1s we see before we hit a 0). This actually corresponds to Peano arithmetic, if we use the symbols S and Z instead like SSSZSZZSZ. An algorithm which spits out digits of pi forever (e.g. http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/sp... ) could work by moving its 'variables' section further and further to the right, allowing the digits of pi to accumulate, e.g. Start ^ Initialise variables and output/variables separator |VARIABLES Move variables to make space for next digit _|VARIABLES Calculate and write next digit 3|VARIABLES Move variables to make space for next digit 3_|VARIABLES Calculate and write next digit 31|VARIABLES and so on