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 {anbn|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 ...
Get Introduction to Formal Languages, Automata Theory and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
