Lecture 2 Inrtoduction to Computation Theory

Computation theory
Computations are designed to solve problems. Computations are designed for processing information. They can be as simple as estimation for driving time between cities, and as complex as a weather prediction.
Alphabets and Strings
The ability to represent information is crucial to communicating and processing information. Human societies created spoken languages to communicate on a basic level, and developed writing to reach a more sophisticated level.
The English language, for instance, in its spoken form relies on some finite set of basic sounds as a set of primitives. The words are defined in term of finite sequences of such sounds. Sentences are derived from finite sequences of words. Conversations are achieved from finite sequences of sentences, and so forth.
Written English uses some finite set of symbols as a set of primitives. The words are defined by finite sequences of symbols. Sentences are derived from finite sequences of words. Paragraphs are obtained from finite sequences of sentences, and so forth.
Similar approaches have been developed also for representing elements of other sets. For instance, the natural number can be represented by finite sequences of decimal digits.
Computations, like natural languages, are expected to deal with information in its most general form. The ability to represent information is crucial to communicating and processing information to reach a more sophisticated level , are expected to deal with information in its most general form and so forth
A finite, nonempty ordered set will be called an alphabet ? (sigma) if its elements are symbols , or characters. A finite sequence of symbols