Theory of Computation (ePub)

Theory of computation is seen as a branch of both theoreticalcomputer science and modern mathematics (however, it alsocontains some concepts from pure mathematics). Theory ofcomputation shows how one can effectively solve a problemusing a computational model. A number of computationalmodels are described in theory of computation. Algorithm ismost common format of computational model. Algorithm is alogical, systematic presentation of the process of problemsolution. It theoretically represents the procedure of solving aparticular problem. Flowchart is another form of such model ofcomputation. Simply, flowchart is a graphical representation ofany algorithm, using various symbols. Each symbol of flowchartrepresents a particular action. Algorithms and flowcharts possessa strong relation among each other. Yet, theory of computationtalks more deeply and descriptively about algorithms and lessabout flowcharts.Theories, which are too broad, are often divided into subtheories or branches. Such division allows one to approach andlearn the theory efficiently. Theory of computation is dividedinto four main branches. Many people see these branches asindividual sub theories (sub theories and branches are bothdifferent terms). These main branches/ sub theories are asfollowing:Automata TheoryFormal Language TheoryComputability TheoryComputational Complexity TheoryHere, it should be noticed that many theories treat AutomataTheory and Formal Language Theory as individual concepts. Itis same for vice versa situation. Many treat them as a whole.In this book, they are described as individual concepts.However, you will find many connections between theirconcepts. The whole structure of computation theory isdedicated to describe the capabilities and limitations of moderncomputer system; in terms of solving a particular problem,(This process includes various steps and operations).Model of computations are mathematical abstractions ofcomputers and their functionality. These models are used todescriptive studies and researches related to computers andvarious functions provided by them (capabilities, limitations, etc).These computational models are divided in various typesaccording to the characteristics and results they provide.Turning machine is one of these many models of computations.This model is being referred here since it is arguably the mostreasonable and powerful model compared to othercomputational models. This model has a simple andstraightforward structure that is easy to interpret andunderstand which makes the formulation and analyzing processmuch easier. Other models consider that infinite memorycapacity is essential in order to provide results related todecidable problems. However, turning machine requires only afinite amount of memory in order to solve and provide resultsfor a decidable problem. It means that if a turning model iscapable of solving a problem; the very same problem can besolved using any other computer that has a finite amount ofavailable memory.