O'Reilly logo

Introduction to Formal Languages, Automata Theory and Computation by Kamala Krithivasan, R Rama

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required