
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
 ContextFreeGrammar: 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 = m^{2} 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 ktuple
 2tuple is called pair
 Cartesian product

Functions and Relations (Studied Before ):
 A functions is an object that sets up an inputoutput 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 kary 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 ktuples 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 = w_{1} w_{2}… w_{n} where each w_{i}
 The reverse of w, written as w^{R} 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 wellwritten 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 highlevel 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)