Theory of Computation: Automata, Computability, Complexity

Introduction

• The text introduces the theory of computation areas explored in the book: automata, computability, and complexity.
• The focus is on the fundamental capabilities and limitations of computers.
• The order of exploration begins with complexity, then computability, and finally automata theory.

Complexity Theory

• Computer problems vary in difficulty; some are easy (e.g., sorting), while others are hard (e.g., scheduling).
• Complexity theory aims to classify problems based on computational difficulty.
• A significant achievement involves classifying problems analogous to the periodic table for elements.
• Confronting computationally hard problems involves altering the problem for easier solutions, settling for approximate solutions, accepting occasional slowness, or using alternative types of computation.
• Cryptography benefits from complexity theory by utilizing computationally hard problems for designing secure codes.

Computability Theory

• Mathematicians discovered that some basic problems are unsolvable by computers.
• An example is determining the truth of mathematical statements.
• This discovery led to theoretical models of computers.
• Computability theory classifies problems as solvable or not, differing from complexity theory's easy/hard classification.
• Computability theory introduces concepts used in complexity theory.

Automata Theory

• Automata theory focuses on mathematical models of computation and their properties.
• Models like finite automata are used in text processing, compilers, and hardware design.
• Context-free grammars are used in programming languages and artificial intelligence.
• It provides a precise definition of a computer, formal definitions of computation, and introduces relevant concepts to computer science.

Mathematical Notions and Terminology

• The section introduces essential mathematical concepts, tools, and notation.

Sets

• A set is a group of objects represented as a unit, which are called elements or members.
• Sets can be described by listing elements inside braces, e.g., {7, 21, 57}.
• The symbols ∈ and ∉ denote set membership and nonmembership, respectively.
• A is a subset of B (A ⊆ B) if every member of A is also a member of B.
• A is a proper subset of B (A ⊂ B) if A is a subset of B and not equal to B.
• The order and repetition of members in a set do not matter.
• An infinite set contains infinitely many elements.
• The notation "..." is used to indicate the continuation of a sequence in an infinite set.
• The set of natural numbers N is written as {1, 2, 3, ...}.
• The set of integers Z is written as {..., -2, -1, 0, 1, 2, ...}.
• The empty set (∅) has 0 members.
• Sets can be described using a rule, e.g., {n | rule about n}.
• The union of sets A and B (A ∪ B) combines all elements in both sets.
• The intersection of sets A and B (A ∩ B) contains elements in both sets.
• The complement of A (A) contains elements under consideration that are not in A.
• Venn diagrams represent sets as regions enclosed by circular lines to clarify concepts.

Sequences and Tuples

• A sequence is a list of objects in a specific order, written within parentheses, e.g., (7, 21, 57).
• Order matters in a sequence. (7, 21, 57) is different from (57, 7, 21).
• Repetition matters in a sequence.
• Finite sequences are called tuples; a k-tuple has k elements.
• A 2-tuple is called a pair.
• Sets and sequences can be elements of other sets and sequences.
• The power set of A is the set of all subsets of A.
• The Cartesian product of A and B (A × B) is the set of all pairs where the first element is in A and the second is in B.

Functions and Relations

• Functions establish an input-output relationship; the same input always yields the same output.
• If f is a function and f(a) = b, then f maps a to b.
• The domain of a function is the set of possible inputs.
• The range of a function is the set from which the outputs come.
• Notations: f: D → R, means f is a function with domain D and range R.
• A function is onto the range if it uses all elements of the specified range.
• Functions can be described with procedures or tables.
• A k-ary function has k arguments; unary has one, and binary has two.
• Infix notation places the symbol between two arguments, e.g a+b.
• A predicate or property is a function whose range is {TRUE, FALSE}.
• A relation on A is a property whose domain is a set of k-tuples A × ... × A.

Graphs

• A graph contains points (nodes or vertices) connected by lines (edges).
• Degree counts the edges at a nodes.
• In a graph G with nodes i and j, (i, j) indicates edge connecting i and j.
• Undirected graphs consider edge (i,j) the same as (j,i).
• G = (V, E), where V is the set of nodes and E is the set of edges.
• Labeled graphs have labeled nodes and/or edges.
• A subgraph of graph H has subset of H's nodes and edges.
• A path in a graph is a sequence of nodes connected by edges.
• A simple path has no repeating nodes.
• A connected graph has paths between any two nodes.
• A cycle is a path starting and ending in the same node.
• A simple cycle has at least three nodes repeats only first and last nodes.
• A tree is a connected graph without simple cycles.
• The root is a specially designated node in a tree.
• Tree nodes of degree 1, other than the root, are called leaves of the tree.
• Directed graphs have arrows instead of lines; outdegree is arrow count leaving a node, indegree is arrow count entering.
• Directed graphs represent edge from i to j as pair (i, j).
• A directed path's arrows all point in same direction as its steps.
• A strongly connected graph has directed path connecting any two nodes.

Strings and Languages

• An alphabet is any nonempty finite set of symbols.
• A string over an alphabet is symbols concatenated.
• Length of w indicates the number of symbols concatenated.
• The empty string, ε, has length 0.
• String vr is the reverse of string v.
• String z is a substring of v if it appears contiguously within v.
• The concatenation of x and y, written xy, appends y to x
• The lexicographic ordering of strings orders as in a dictionary except shorter strings come first.
• A langugage is a set of strings.

Boolean Logic

• Boolean logic: mathematical system built around TRUE and FALSE.
• Used for digital electronics and computer design.
• Boolean values (TRUE, FALSE) often represented by 1 and 0.
• Boolean operations manipulate Boolean values
• Negation (¬) is NOT operation (flips value).
• Conjunction (∧) is AND operation (both inputs must be 1).
• Disjunction (∨) is OR operation (any inputs must be 1).
• The distributive law for AND and OR helps manipulate Boolean expressions
• P ∧ (Q ∨ R) equals (P ∧ Q) ∨ (P ∧ R), and its dual
• P ∨ (Q ∧ R) equals (P ∨ Q) ∧ (P ∨ R).

Theorems and Proofs

• Definitions describe objects.
• Theorems are proven mathematical statements.
• Proofs give logical reasons why the mathematical statement is true.
• Lemmas: statements for special purpose.
• Corollaries: related statements based on the theorem.
• Finding a proof sometimes requires re-writing known and unknown values to find new meanings.
• When attempting a proof: -Read the statement carefully -Try experimenting with examples -Try finding a counterexample -Try proving a special case
• Producing a proof -Be patient because finding a proof takes time -Come back to the proof after giving it time -Be neat with simple pictures and text -Be concise and ensure details are easily readable

Common Proof Types

• Proof by Construction shows how to construct an object
• Proof by Contradiction assumes theorem false, show assumption implies contradiction
• Proof by Induction shows that all elements of infinite set have given property -In the induction step the assumption that P(i) is true is called the induction hypothesis -Variations may be useful such as "stronger induction hypothesis" -The format for writing down a proof by induction is as follows: -Basis: Prove that P(1) is true -Induction step: For each i ≥ 1, assume that P(i) is true and use this assumption to show that P(i + 1) is true