# Introduction to Theory of Computation

• Aim of the course:

• Determine what can and can’t be computed
• How quickly
• With how memory
• On which type of computational model
• First problem:

• Given a number contains of 500 digits can you find its factors in a reasonable amount of time?
• Answer: no one presently knows how to do that in all cases within the life time of the universe!
• Theory of Computation Central Areas:

• Automata
• Computability
• Complexity
• The three areas are linked together by the question

• What are the fundamental capabilities and limitations of computers?
• History:

• This question goes back to 1930s when mathematical logicians first began to explore the meaning of computation.
• Complexity Theory:

• Computer problems either hard or easy. Easy problems like sorting number even microcomputers can sort million of numbers. Now, consider a scheduling problem for entire university under some constrains (no two classes share the same room at the same time, the instructors limitations…etc), finding the best schedule may require centuries, even with a supercomputers
• So we have a new question that says:

• What makes some problems computationally hard and others easy?
• This is the central question of the complexity theory!
• Researches have discovered and elegant scheme for classifying problems according to their computational difficulty. It’s analogous ( تشبه ) to the periodic table for classifying elements according to their chemical properties
• The Classification Rules, any problem is classified as computationally hard problem according to the following:

• If you can alter the root difficulty of the problem so that it becomes more solvable
• You can settle for less than a perfect solution ( hardness of getting a perfect solution )
• Some problems are hard only in the worst case but in other cases are easy. This alternation of difficulty comes from the application that is solving this problem
• If there isn’t exist alternative types of computation (such as randomization) that can speed up some tasks
• One applied area has been affected directly by complexity theory is the field of cryptography (علم التشفير)
• The key of this relation is that in the other fields they want easy problems to solve but in cryptography we want hard problems instead of easy problems (because secret codes should be hard to break)
• Computability Theory:

• During the first half of the 20s century, mathematics such as Kurt, Alan Turing, Alonzo Church has discovered that certain basic problems couldn’t be solved by the computers. One of these problems is the problem of determining whether a mathematical statement is either true or false!!!
• The previous problem lead to develop the theoretical models of computers that can solve this problems
• There are similarity between complexity and computability that complexity classify according to hard and easy where computability classify according to solvable or not solvable by computers
• Automata Theory:

• Automata theory deals with the definitions and properties of mathematical models of computation
• Examples of these models:

• Finite Automaton: used in text processing, compilers and hardware design
• Context-Free-Grammar: used in programming languages and AI
• The theories of computability and complexity require a precise definition of computer, and this is the role of automata
• Mathematical Notations and Terminology:

• Here we will describe basic mathematical objects, tools and notations that we will use
• Sets (Studied Before ):

• A set is a group of objects represented as a unit
• The objects of the set are called members or elements
• Ways of defining sets:

• By listing the elements of the set inside braces{}:

• {7, 21, 57}
• By rules:

• Set A = {n | rule about n}, Example :

• {n | n = m2 for m }
• Sets notations:

• , ,
• Sets types: Multiset, infinite set, empty set,
• Venn diagram
• Sequence and Tuples (Studied Before ):

• A sequence of objects is a list of these objects in the same order
• Sequences are listed within parentheses ()
• Here we care about the order of elements in the sequence
• Finite sequences are called tuples
• Sequence with k elements is called k-tuple

• 2-tuple is called pair
• Cartesian product
• Functions and Relations (Studied Before ):

• A functions is an object that sets up an input-output relation
• Function are also called mapping
• Domain: the set of possible inputs for a function
• Range: the set of possible outputs for a function
• The input for a function is called arguments to f
• A function with k arguments is called k-ary functions and k is called arity of the function
• If k = 1 then the function is called unary function
• If k = 2 then the function is called binary function
• Infix notation: like we say f = x + y
• Prefix notation: like we say f = add(x, y)
• A predicate or property is a function whose range is {True, False}
• When a property has domain of k-tuples it’s called relation
• The notation for saying that is a function with domain D and range R is:

• Ways of describing functions:

• Table
• When we do modular arithmetic (say by n) on inputs in a function then we define the function with the notation:
• A special type of binary relation called equivalence relation that means two objects are equal in some features
• A binary relation R is an equivalence relation if it satisfies the conditions:

• Reflexive
• Symmetric
• Transitive
• Graphs:

• An undirected graph or simply graph is a set of points with lines connecting some of the points.
• The points are called nodes or vertices and the lines are called edges
• The number of edges at particular node is the degree of the node
• No more than one edge is allowed between any two nodes
• If V is the set of nodes of G and E is the set of edges then we say G = (V, E)
• Graphs are used to represented data
• We say that graph G is a subgraph of graph H if nodes of G are a subset of the nodes of H and the edges of G are a subset of the edges of H
• A path in a graph is a sequence of nodes connected by edges
• A simple path is a path that doesn’t repeat any nodes
• A graph is connected if every two nodes have a path between them
• A path is cycle if it starts and ends in the same node
• A simple cycle is the cycle that contains at least 3 nodes and repeats only the first and last node
• A graph is a tree if it’s connected and has no simple cycles
• The nodes of degree 1 other than the root are called leaves
• If the graph has arrows instead of lines it’s called directed graph
• The number of arrows pointing from a particular node is the outdegree
• The number of arrows pointing to a particular node is the indegree
• A path in which all the arrows point in the same direction as its steps is called a directed path
• A directed graph is strongly connected if a directed path connects every two nodes
• String and Languages:

• Alphabet is any nonempty finite set
• The members of alphabet are called symbols
• We generally use letters to designate alphabets and typewriter front for symbols from an alphabet
• A string over an alphabet is a finite sequence of symbols from that alphabet
• If w is a string over , the length of w (written as |w|) is the number of symbols it contains
• The string of length zero is called empty string written as
• The empty string plays the role of 0 in a number system
• If w has length n we can write w = w1 w2 wn where each wi
• The reverse of w, written as wR is the string obtained by writing the opposite order
• String z is substring of w if z appears consecutively within w
• If we have string x of length m and string y of length n, the concatenation of x and w written xy is the string obtained by appending y to the end of x
• The lexicographic ordering of strings is the same as the familiar dictionary ordering, expect that shorter strings precede longer strings

• Thus, the lexicographic ordering of all strings over the alphabet {0, 1} is: ( , 0, 1, 00, 01, 10, 11, 000, …. )
• A language is a set of strings
• Boolean Logic:

• Boolean logic is a mathematical system built around the two values True and False
• The values True and False are called Boolean values
• Boolean Operations:

• NOT, negation, ¬
• AND, conjunction,
• OR, disjunction,
• XOR, exclusive or,
• XNOR, exclusive nor,
• Equality, ↔
• Implication, →
• We use Boolean operations for combining simple statements into more complex Boolean expression
• Operands of operation
• Distributive low for AND and OR are similar to + and ×
• Definitions, Theorems and Proofs:

• Theorems and proofs are soul and heart of math and definitions are its spirit
• Definitions describe the objects and notations we use
• The definitions may be easy as the definition of set or complex as the definition of security in a cryptography system
• After we have defined various objects and notations we usually make mathematical statements about them, these statements express that some object has a certain property
• Proof is a convincing logical argument that a statement is true
• Theorem is a mathematical statement proved true
• Lemmas Statements are statements that are used to proof other statements
• The theorem or its proof may allow us to conclude easily that other related statements are true these statements are called corollaries
• Finding Proofs:

• Steps to find proof:

• Carefully read the statement you want to proof
• Understand all notations
• Rewrite the statement in your own words
• Break it down and consider each part separately
• Multipart Statements:

• P Q: if P is true then Q is true (iff), forward direction
• P Q: if Q is true then P is true (if), reverse direction
• PQ: P is true if Q is and Q is true if P is
• A = B: every member of A is also a members of B
• If statement says that all objects of a certain type have a particular property, pick a few objects of that type and observe that they actually do have that property. After that try to find object that fails to have the property called a counterexample. If the statement is true then, you won’t find the counterexample object
• If you are stuck to prove a statement, try something easier. Attempt to prove special cases of statement till you can extract a general case of this statement
• Writing proofs:

• A well-written proof is a sequence of statements wherein each one follows by simple reasoning from the previous statement in the sequence
• Proofs Producing Tips:

• Be patient
• Come back to it:

• read the statement then leave it and come back after hours
• Be neat:

• User simple clear pictures and text
• Be concise:

• Brevity helps you express high-level ideas without getting lost in details. Good mathematical notation us useful for expressing ideas concisely
• Types of Proofs:

• Proof By Construction:

• When to user:

• Many theorems state that a particular type of object exists. One way to prove such a theorem is by demonstrating how to construct the object
• Proof By Contradiction:

• Here we assume that the theorem is false and then show that this assumption leads to an obviously false consequence
• Rational number: A number is rational if it’s a fraction m/n where m and n are integers
• Proof By induction:

• Proof by induction is an advanced method used to show that all elements of an infinite set have a particular property
• Construction of Induction Proof:

• Induction Step:

• This step proofs that for each i ≥ 1, so we first
• Assume that P(i) is true then, (Induction Hypothesis)
• Proof that P(i+1) is also true (Induction Step)
• Basis Step: This step proof that P(1) is true (simplest number)