CS46 Introduction


Math Preliminaries

Welcome to CS46. Please look over the Syllabus, create or sign into your Piazza Acct, get the textbook, and read chapter 0 and section 1.1.

Course has a lab section. Attendance is mandatory. Sometimes we will have small programming exercises. Sometimes we will review or explore lecture material more in depth.

The course will have two midterm exams and a final exam. Midterms will be in the evening and I will try to have them scheduled soon. The registrar's office schedules the final exam time.

What is TOC?
Two fundamental questions of Computer Science: Theory of computation looks more closely at the first questions and answers the second primarily with very broad strokes (${\tt P, NP, EXP, LOGSPACE}$). Complexity Theory is the research area which extends TOC.

Algorithms, e.g., CS41 looks more closely at the second question and refines the broad categories of primarily the complexity class ${\tt P}$ into finer classes e.g., $O(1), O(\log n), O(n), O(n^2)$

Both disciplines answer these questions in the context of a mathematical model of computation. The goal of the model is to abstract away the core concepts of computation without needing to consider a specific hardware setup.

A quick overview of the first ten weeks of this course: exploring computational models
  1. Define model
  2. Explore what model can compute
  3. Prove that some things cannot be computed in model
  4. Expand model (go back to step 1)
Mostly done with math, so we'll need to define/review some terms.

Sets, ordered tuples

A set is a collection of unordered, distinct objects, e.g., $S=\{ a, b, c, d \}$.

The power set of $A, 2^A$ is the set of all possible subsets of $A$. Let $A=\{ a, b \}$. $2^A = \{ \emptyset, \{ a \}, \{ b \}, \{ a, b \} \}$

True or False?

  1. $ \emptyset \subseteq \emptyset$
  2. $ \emptyset \in \emptyset$
  3. $ \emptyset \in \{ \emptyset \}$
  4. $ \emptyset \subseteq \{ \emptyset \}$
  5. $ \{ \{ a, b \} \} \in 2^{ \{ a, b , \{ a, b \} \} }$

  1. $2^{ \{ 7, 8, 9 \} } \setminus 2^{ \{ 7, 9 \} } = $?
  2. $2^\emptyset = $?
For sets, the order of elements does not matter, so $\{ a, b \} = \{ b, a \} \}$. An ordered pair is indicated by the notation $(a, b)$ and in an ordered pair, $(a,b) \neq (b,a)$. An ordered $k$-tuple contains $k$ ordered elements $(a_1, a_2, a_3, \ldots, a_k)$. $(a,a)$ is a valid ordered pair, while $\{ a, a \}$ is not a valid set, because the items must be distinct

Ordered pairs are often formed by the Cartesian product of two sets. Let $A$ and $B$ be two sets. Their Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$, e.g., $\{ a_1, a_2 \} \times \{ b_1 \} = \{ (a_1, b_1), (a_2, b_1) \}$

Relations and functions

A Binary relation on two sets $A$ and $B$ is simply a subset of $A \times B$

A Function from a set $A$ to a set $B$ is a binary relation $R$ with the property that for every $a \in A$ there is exactly one $b \in B$ with $(a,b) \in R$. We say the function $f$ maps the domain of $f, A$ to the co-domain of $f, B$, or $f: A \mapsto B$. We will often use the notation $f(a)=b$ to mean $(a, b) \in f \subseteq A \times B$.

Are the following functions, relations, or neither?

  1. $\{ (a, b) : b = a^2 \}$
  2. $\{ (a, b) : a \geq b \}$
  3. $\{ (a, b) : b^2 = a \}$

We will occasionally classify functions as one-to-one, onto or a bijection. A function $f: A \mapsto B$ is one-to-one if for two distinct elements $a, a' \in A, f(a) \neq f(a')$. Note this implies $|A| \leq |B|$. A function $f$ is onto if for every $b \in B$ there is some $a \in A$ such that $f(a) = B$. $f$ is a bijection if $f$ is one-to-one and onto.

The inverse of a binary relation $R \subseteq A \times B$, denoted $R^{-1}$ is a subset of $B \times A$ such that $(b,a) \in R^{-1}$ iff $(a, b) \in R$. The inverse of a relation is a relation. Is the inverse of a function a relation? Is it a function? What if $f$ is one-to-one? What if it is onto? A bijection?

Alphabets and Languages
An alphabet $\Sigma$ is simply a finite set of symbols. The English alphabet is a natural example, but in this course we will often consider much smaller alphabets such as $\Sigma = \{ 0, 1 \}, \Sigma = \{ a, b \},$ or, if we are feeling really crazy $\Sigma = \{ a, b, c \}$.

A string $w$ is a finite sequence of symbols over an alphabet, e.g, $w_1=baa$ and $w_2=a$ are strings over the alphabet $\Sigma = \{ a, b \}$. The length of the string $w$ is written as $|w|$. The empty string $\varepsilon$ has length 0.

A language $L$ is a set of strings from an alphabet $\Sigma$, The set of all strings over an alphabet $\Sigma$ is denoted $\Sigma^*$. Note that while $\Sigma^*$ consists of finite length strings, the size of $\Sigma^*$ is infinite. $L=\Sigma^*$ is an example of an infinite language.

Even though a language is a set and sets are unordered, sometimes we will list the strings in a modified lexicographical order which the book calls shortlex order. In this order, shorter strings precede longer strings. When two strings are the same length, shortlex order uses the standard lexicographical/dictionary order to compare the strings. To use some earlier defined terminology, we can say the shortlex relation is a relation $R$ on strings $w \in L$ where $(w_1, w_2) \in R$ if $w_1 < w_2$ in shortlex order.

Enough terminology! Why?
To explore the limits of computation models, we will focus on the following types of computational problems. Suppose we are given a language $L \subseteq \Sigma^*$. Can we design a computer program or machine $M(L)$ that identifies/recognizes/accepts only those inputs which are strings in $L$ and rejects all other inputs? Think of this machine $M(L)$ as function that takes as input a single string $w \in \Sigma^*$ over a known alphabet and, after some computation, outputs either a yes or no response. Ideally we would like $M(w)=$yes iff $w \in L$ and $M(w)=$no iff $w \not \in L$.

While this might seem like a gross oversimplification of what computers can do, it gives us a starting point to compare models and analyze their limits. Plus there are some applications in which recognizing patterns is important.

Soon we will define our first computational model, the Deterministic Finite Automata and study its computing power. But first, let's demonstrate an interesting result: that there must exist some language that cannot be recognized by any computer program. To do that, we need to step back and examine countably and uncountably infinite sets.
Infinite sets

Given a finite alphabet $\Sigma$, the set of all strings $\Sigma^*$ is countably infinite. A computer program must have some finite description over some alphabet. So we can think of a computer program as nothing more than a single string over some alphabet. So how many programs can we have? That is certainly no more than the total number of strings over the program alphabet, so that must be countably infinite. Each program recognizes one language. But how many languages are there? Each language is a subset of $\Sigma^*$ and the set of all possible subsets of $\Sigma^*$ is $2^{\Sigma^*}$. A short diagonalization argument should convince you that the number of languages is uncountably infinite. This means there are way more languages than programs, so there must be some language $L$ for which there is no program $M$ such that $M$ accepts $L$. In essence, there are some things that are uncomputable using a finite description of a computer program/algorithm. Hmm. This raises a number of questions.

This course will explore only the first three questions.