# Chapter 9. Turing Machines

We have seen earlier that FSA have finite amount of memory and hence cannot do certain things. For example, no FSA can accept {*a*^{n}b^{n}|*n* ≥ 1}. Though, it is possible to have FSA for adding two arbitrarily long binary numbers, we cannot have an FSA which can multiply two arbitrarily long binary numbers. Hence the question arises. What happens when we leave this restriction of finite memory? What problems can be solved by mechanical process with unlimited memory? By mechanical process, it is meant a procedure so completely specified that a machine can carry it out. Are there processes that can be precisely described yet still cannot be realized by a machine (computer)?

Programming – the job of specifying the procedure that ...