Useful tip: If you use a browser like Google Chrome, clicking on the lecture slide link in an entry will take you to that slide in the PDF.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z$\aleph_0$ is the cardinality of $\mathbb{N}$. That is, $|\mathbb{N}| = \aleph_0$.
Source: Lecture 00, Slide 47.
A procedure for a solving a problem.
Source: Lecture 10, Slide 58.
A finite set of characters, typically denoted with $\Sigma$.
Source: Lecture 11, Slide 17.
The $P$ part of the implication $P \implies Q$.
Source: Lecture 02, Slide 12.
A binary relation $R$ over a set $A$ is called antisymmetric iff: For any $x \in A$ and $y \in A$, if $xRy$ and $y \ne x$, then $yRx$ does not hold. Equivalently: For any $x \in A$ and $y \in A$, if $xRy$ and $yRx$, then $x = y$.
Source: Lecture 05, Slide 72.
In a mathematical proof, an arbitrary choice of $x$ is a statement that $x$ is left unspecified so that any result proven about $x$ will prove the result for any choice of $x$.
Source: Lecture 01, Slide 20.
A binary operator $\ast$ is called associative if for any $a$, $b$, and $c$, we have $a \ast (b \ast c) = (a \ast b) \ast c$.
Source: Lecture 01, Slide 45.
$A_{TM}$ is the language of the Universal Turing machine. In lecture we proved it is recognizable but not decidable.
$A_{TM} = \mathscr{L}(U_{TM}) = \left\lbrace \langle M, w \rangle \Big\vert M \text{ is a Turing Machine and w } \in \mathscr{L}(M) \right\rbrace$
Source: Lecture 19, Slide 31.
$A_{TM}$'s complement is the complement of the language of the Universal Turing Machine. In lecture we proved it is unrecognizable.
Source: Lecture 20, Slide 9.
A mathematical model of a computing device.
Source: Lecture 11, Slide 15.
A binary operator is an operator that takes in two operands.
Source: Lecture 01, Slide 36.
A property that describes whether two objects are related in some way. Eg. $<$, "divides", "tastier than"
Source: Lecture 01, Slide 47.
A statement of the form $P \iff Q$, which means both $P \implies Q$ and $Q \implies P$. It is sometimes written as $P$ iff $Q$, and both statements are read as $P$ if and only if $Q$.
Source: Lecture 02, Slide 26.
A bijection is a function that is both injective and surjective.
Source: Lecture 06, Slide 20.
A bit is a value that is either 0 or 1. The set of all bits is denoted $\mathbb{B}$.
Source: Lecture 01, Slide 35.
A bitstring is a finite sequence of bits.
Source: Lecture 01, Slide 58.
The problem of verifying whether or not some propositional logic formula $\varphi$ is satisfiable..
Source: Lecture 10, Slide 35.
Cantor's theorem states that for any set $S$, that $|S| < |\wp(S)|$.
Source 1: Lecture 00, Slide 75.
Source 2: Lecture 07, Slide 34.
The Cartesian Product of $A \times B$ of two sets is defined as $A \times B \equiv \{(a, b)\,|\,a \in A\ and\ b \in B \}$
Source: Lecture 05, Slide 10.
The cardinality of a set $S$, denoted $|S|$, is the number of elements it contains. By definition, two sets have the same cardinality precisely if their elements can be put into a one-to-one correspondence.
Source: Lecture 00, Slide 46.
States that every effective method of computation is either equivalent to or weaker than a Turing machine.
This is not a mathematical fact -- it's a hypothesis about the nature of computation.
Source: Lecture 18, Slide 65.
In propositonal, a many-way disjunction of literals, like $\not x \vee y \vee \not z$.
Source: Lecture 10, Slide 48.
If $f$ is a function from $A$ to $B$, we call $B$ the codomain of $f$.
Source: Lecture 06, Slide 6.
Conjecture (claim) that the hailstone process terminates (See Hailstone Sequence). This remains an unsolved problem in mathematics.
Source: Lecture 18, Slide 18.
A binary operator $\ast$ is commutative if for any $a$ and $b$, $a \ast b = b \ast a$.
Source: Lecture 01, Slide 54.
$|S| < |T|$ iff $|S| \leq |T|$ and $|S| \neq |T|$
Source: Lecture 07, Slide 13.
The composition of two functions $f$ and $g$ is the function $g \circ f$ defines as $(g \circ f)(x) = g(f(x))$.
Source: Lecture 06, Slide 23.
A function $f: \Sigma_1^{\ast} \rightarrow \Sigma_2^{\ast}$ is called a computable function if there some TM $M$ with the following behavior:
"On input $w$: Determine the value of $f(w)$; Write $f(w)$ on the tape; Move the tape head back to the far left; Halt."
Source Lecture 21, slide 55.
The concatenation of two languages $A$ and $B$ over the alphabet $\Sigma$ is the language $AB = {ab \in \Sigma^* | a \in A \land b \in B}$
Source: Lecture 13, slide 16.
A propositional logic formula $\varphi$ that is a conjunction clauses.
Source: Lecture 10, Slide 49.
The contrapositive of "If $P$, then $Q$" ($P \implies Q$) is the statement "If not Q, then not P" ($Q \implies P$).
Source: Lecture 02, Slide 51.
The $Q$ part of the implication $P \implies Q$.
Source: Lecture 02, Slide 12.
A continued fraction is an expression of the form: $$a_1+\frac{1}{a_2 +\frac{1}{a_3+\frac{1}{...+\frac{1}{a_n}}}}$$
Source: Lecture 04, Slide 28.
co-RE is the set of all co-recognizable languages. We also showed in lecture that all languages in R are both RE and co-RE.
Source: Lecture 21, Slide 25.
A language $L$ is co-recognizable iff there is a TM $M$ such that:
if $w \in L$, then $M$ does not reject w, and
if $w \not\in L$, then $M$ rejects w.
Source: Lecture 21, Slide 25.
A path from a node to itself. A cycle in a graph is a path $((v_1, v_2), ..., (v_n, v_1))$ that starts and ends at the same node.
Source: Lecture 05, Slide 34.
A problem with a yes/no answer.
Source: Lecture 11, Slide 13.
A language $L$ is called decidable iff there is a decider $M$ such that $L(M) = L$. Note also that if $L$ is decidable, it is in the set $R$.
Source: Lecture 20, Slide 24.
A Turing Machine that never loops is called a decider. No matter the input it always halts. It might take ridiculously long time to do so, but it will always accept or reject.
Source: Lecture 20, Slide 23.
The set of descriptions of Turing Machines that do not accept themselves: $L_D = \left\lbrace \langle M \rangle \Big\vert M \text{ is a Turing Machine and} \langle M \rangle \not\in \mathscr{L}(M) \right\rbrace$
We also proved in class that the complement of $L_D$ is recognizable, making $L_D$ a member of co-RE.
Source: Lecture 19, Slide 55.
A mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.
Source: Lecture 07, Slide 31.
The difference of two sets $A$ and $B$, denoted $A - B$ or $A \backslash B$, is the set of all elements in $A$ but not in $B$.
Source: Lecture 00, Slide 31.
A direct proof is a proof of a result that works by beginning with a set of starting assumptions and directly establishing the truth of the statement.
Source: Lecture 01, Slide 9.
A directed graph with no cycles.
Source: Lecture 05, Slide 39.
A Graph where the set of its edges $E$ consists of ordered pairs.
Source: Lecture 05, Slide 24.
Theorem: For any integers $a$ and $b$, with $b > 0$, there exists unique integers $q$ and $r$ such that $a = qb + r$ and $0 \le r < b$ and $q$ is the quotient and $r$ is the remainder.
Source: Lecture 04, Slide 43.
If $f$ is a function from $A$ to $B$, we call $A$ the domain of $f$.
Source: Lecture 06, Slide 6.
A backtracking algorithm for solving satisfiability for CNFs.
Source: Lecture 10, Slide 69.
Arc in a Graph. A pair representing the start and end (or source and sink) of the edge.
Source: Lecture 05, Slide 24.
Is a form of computation with the following properties:
Source: Lecture 18, Slide 64.
An element of a set is some object directly contained within the set. If $x$ is an element of $S$, we write $x \in S$.
Source: Lecture 00, Slide 20.
The empty string (denoted $\varepsilon$) is the string containing no characters.
Source: Lecture 11, Slide 17.
The empty set (denoted $\emptyset$) is the set containing no elements.
Source: Lecture 00, Slide 17.
A sum of no numbers is called the empty sum and is defined to be zero.
Source: Lecture 03, Slide 29.
$|S| = |T|$ iff there is a bijection $f : S \rightarrow T$
Source: Lecture 07, Slide 9.
Two logical formulas $\varphi$, $\psi$ are equisatisfiable iff $\varphi$ is satisfiable iff $\psi$ satisfiable.
Source: Lecture 10, Slide 94.
Two logical formulas are equivalent iff they always take the same truth values.
Source: Lecture 10, Slide 94.
Informally, the set of all elements equal to a. Formally: Given an equivalence relation $R$ over a set $A$, for any $a \in A$, the equivalence class of $a$ is the set $[a]_R \equiv \{x\,|\,x \in A\ and\ aRx\}$
Source: Lecture 05, Slide 67.
Informally, a relation that indicates when objects have some trait in common. Formally, a binary relation $R$ over a set $A$ is called an equivalence relation iff it is reflexive, symmetric, and transitive.
Source: Lecture 05, Slide 62.
An integer $n$ is even if there exists an integer $k$ such that $n = 2k$.
Source: Lecture 01, Slide 10.
An existential statement is a statement of the form "there exists an $x$ for which $P(x)$ is true".
Source: Lecture 01, Slide 31.
An abstraction of computers with finite resource constraints.
Source: Lecture 11, Slide 10.
A logical system for reasoning about properties of objects. Like propositional logic, but augmented with predicates, functions, and quantifiers.
Source: Lecture 10, Slide 3.
A set of strings, either finite or infinite.
Source: Lecture 11, Slide 18.
A function $f$ is a mapping such that every value in $A$ is associated with a unique value in $B$.
Source: Lecture 06, Slide 6.
A problem where answer may be more complex than yes/no.
Source: Lecture 11, Slide 14.
A mathematical structure for representing relationships. An ordered pair $G = (V, E)$ where: $V$ is a set of the vertices (nodes) of the graph and $E$ is a set of the edges (arcs) of the graph.
Source: Lecture 05, Slide 24.
Procedure that starts with a positive integer $n$ and repeatedly:
Source: Lecture 18, Slide 13.
The Halting problem is the question "given a TM M and a string w, does M halt on w?" As a formal language, HALT $= \left\lbrace \langle M, w \rangle \Big\vert M \text{ is a Turing Machine and } M \text{ halts on w} \right\rbrace$
In lecture we proved it is in RE but not in R.
Source: Lecture 21, Slide 10.
An approach to solving a problem that may or may not work correctly.
Source: Lecture 10, Slide 58.
A high-level description of a Turing machine is a description of the form "On input $x$: do something with $x$"
Source: Lecture 19, Slide 9.
An identity element for a binary operator $\ast$ is a value $z$ such that for any $a$, we have $a \ast z = z \ast a = a$.
Source: Lecture 01, Slide 38.
A statement of the form If $P$, then $Q$, often written as $P \implies Q$ (read: $P$ implies $Q$).
Source: Lecture 02, Slide 12.
A function is called injective if each element of the codomain has at most one element of the domain associated with it.
Source: Lecture 06, Slide 15.
Is a string representation of the TM's tape, state, and tape head location. This has the effect of only storing the “interesting” part of the tape, since at any instant in time, only finitely many cells on the TM's tape may be non-blank..
Source: Lecture 18, Slide 43.
An integer is a number with no decimal part (..., -2, -1, 0, 1, 2, ...). The set of all integers is denoted $\mathbb{Z}$.
Source: Lecture 00, Slide 21.
The intersection of two sets $A$ and $B$, denoted $A \cap B$, is the set of all elements contained in $A$ and contained in $B$.
Source: Lecture 00, Slide 30.
Operation on languages defined as
Source: Lecture 13, slide 22.
See Formal language
The language of a Turing Machine is the set of all strings that it accepts.
Source: Lecture 18, Slide 20.
A lemma is a smaller result proven to help establish a larger result.
Source: Lecture 01, Slide 49.
In propositional logic, a variable or its negation, like $x$ or $\neg x$.
Source: Lecture 10, Slide 48.
A logical operator is an operator that takes in a number of bits and produces a bit.
Source: Lecture 01, Slide 35.
A loop invariant is a property or set of properties which if true before an action is performed, will also be true after that action is performed.
Source: Lecture 03, Slide 60.
If for some property $P(n)$, we have that $P(0)$ is true and for any $n \in \mathbb{N}$, we have $P(n) \rightarrow P(n+1)$, then for any $n \in \mathbb{N}$, $P(n)$ holds true.
In general, Mathematical Induction (also referred to as Weak Induction) is good for showing that some property holds by incrementally adding one new piece.
Source: Lecture 03, Slide 3.
If there is a mapping reduction from language A to
language B, then we say A is mapping reducible to
B.
If A $\leq_{M} B$ and $B \in R$ then $A \in
R$
If A $\leq_{M} B$ and $B \in RE$ then $A \in
RE$
Source: Lecture 22, slide 19.
A function $f: \Sigma_1^{\ast} \rightarrow \Sigma_2^{\ast}$ is called a mapping reduction from $A$ to $B$ iff for any $w \in \Sigma_1^{\ast}, w \in A \text{ iff } f(w) \in B$ and $f$ is a computable function.
Source: Lecture 21, slide 59.
A natural number is a nonnegative integer (0, 1, 2, 3, ...). The set of all natural numbers is denoted $\mathbb{N}$.
Source: Lecture 00, Slide 21.
The natural numbers can be defined inductively as seen in Lecture 03, Slide 62.
A propositional logic formula $\varphi$ where the only connectives are $\neg$, $\vee$, and $\wedge$.
Source: Lecture 10, Slide 78.
An NFA (nondeterministic finite automaton) is a finite automaton allowing any number of transitions out of each state on any symbol, as well as epsilon transitions.
Source: Lecture 13, slide 5.
A variant on a Turing machine where there can be any number of transitions for a given state/tape symbol combination. The NTM accepts iff there is some possible series of choices that it can make such that it accepts
They are equivalent in power to deterministic turing machines.
Source: Lecture 18, Slide 20.
An integer $n$ is odd if there exists an integer $k$ such that $n = 2k + 1$.
Source: Lecture 01, Slide 10.
Informally, a relation that ranks elements against one another.
Source: Lecture 05, Slide 71.
A pair of elements $(a,b)$ in a specific order. Two ordered pairs are equal iff each of their components are equal.
Source: Lecture 05, Slide 9.
A collection of n elements $(a_1, a_2, ..., a_n)$ in a specific order. Two ordered tuples are equal iff each of their elements are equal. Also called a Sequence.
Source: Lecture 05, Slide 9.
A binary relation $R$ is a partial order over a set $A$ iff it is reflexive, antisymmetric, and transitive.
Source: Lecture 05, Slide 74.
A pair $(A, R)$, where $R$ is a partial order over $A$.
Source: Lecture 05, Slide 74.
A series of edges connecting two nodes. A path from $v_1$ to $v_n$ is a sequence of edges $((v_1, v_2), (v_2, v_3), ..., (v_{n-1}, v_n))$.
Source: Lecture 05, Slide 28.
The number of edges a path contains.
Source: Lecture 05, Slide 28.
If $m$ objects are placed into $n$ bins, where $m > n$, then some bin contains at least two objects.
Source: Lecture 07, Slide 45.
The power set of a set $S$, denoted $\wp(S)$, is the set of all subsets of $S$.
Source: Lecture 00, Slide 44.
If $R$ is a regular expression, then $L(R)$ is regular
If $L$ is a regular language, then there is a regular expression for $L$.
Source: Lecture 14, Slide 8.
An expression in first-order logic that describes properties of objects. $P(x)$ means that property $P$ holds for $x$.
Source: Lecture 10, Slide 3.
A proof by cases is a proof that branches off into different parts based on a set of possible options.
Source: Lecture 01, Slide 39.
A proof of a statement $P$ that assumes that $P$ is not true and then concludes something impossible based on the assumption.
Source: Lecture 02, Slide 21.
A proof for $P \implies Q$ that shows instead that $\not Q \implies \not P$.
Source: Lecture 02, Slide 52.
To prove some property $P(n)$ holds for all natural numbers:
Source: Lecture 03, Slide 9.
A set $S$ is a proper subset of a set $T$ (denoted $S \subset T$) if $S \subseteq T$ and $S \ne T$.
Source: Lecture 00, Slide 43.
A literal is pure if its negation appears nowhere in the propositional formula.
Source: Lecture 10, Slide 63.
A determiner in first-order logic that describes the quantity of variables for which a proposition is true. $\forall xP(x)$ means that $P(x)$ is true for all $x$. $\exists xP(x)$ means that $P(x)$ is true for some $x$.
Source: Lecture 10, Slide 4.
The set of all decidable languages. Another way to think about it is a language is in R iff there is an algorithm for deciding membership in that language. We also proved in lecture that R is closed under complementation.
Source: Lecture 20, Slide 24.
$|S| \leq |T|$ iff there is a injection $f : S \rightarrow T$
Source: Lecture 07, Slide 13.
A number $r$ that can be written as $r = p/q$ where $p$ and $q$ are integers, $q \neq 0$, and $p$ and $q$ have no common divisors other than $\pm 1$. A number that is not rational is called irrational.
Source: Lecture 02, Slide 30.
The set of all recognizable languages.
Source: Lecture 18, Slide 20.
Denoted $u \rightarrow v$. A node $v$ is reachable from node $u$ iff there is a path from $u$ to $v$.
Source: Lecture 05, Slide 31.
A real number is a number measuring an arbitrary quantity. $e$, $\pi$, and $\sqrt{2}$ are all real numbers. The set of all real numbers is denoted $\mathbb{R}$.
Source: Lecture 00, Slide 21.
A language is called recognizable iff it is the language of some Turing machine.
Source: Lecture 18, Slide 20.
Problem A reduces to problem B iff a solver for B can be used to solve A. It is possible to transform a description of an instance of problem A into an instance of problem B, proceed to use the solver for B on this transformed instance, and then discover the solution for the instance of problem A.
The two formals reductions we handle in this class are Mapping Reductions and Polynomial-time Reductions.
Source: Lecture 21, Slide 45.
A binary relation $R$ over a set $A$ is called reflexive iff: For any $x \in A$, we have $xRx$.
Source: Lecture 05, Slide 56.
A family of descriptions that can be used to capture the Regular Languages
Source: Lecture 13, slide 39.
A language $L$ is called a regular language iff it is accepted by some DFA, i.e. there exists a DFA $D$ such that $L(D) = L$, where $L(D) =$ the set of strings $w$ that cause the DFA to end up in an accepting state.
Source: Lecture 13, Slide 10.
Formally, a relation is a set of ordered pairs representing the pairs for which the relation is true.
Source: Lecture 05, Slide 48.
A propositional logic formula $\varphi$ is satisfiable iff is some assignment to its variables that makes it evaluate to true. An assignment of variables that makes it evaluate to true is called a satisfying assignment.
Source: Lecture 10, Slide 34.
A binary operator $\ast$ with identity element $z$ is called self-inverting when for any $a$, we have $a \ast a = z$.
Source: Lecture 01, Slide 43.
See Ordered Tuple
Source: Lecture 05, Slide 9.
A set is an unordered collection of distinct objects, which can be anything, including other sets.
Source: Lecture 00, Slide 14.
Set-builder notation is a way to describe an arbitrary set by describing a rule by which its elements should be chosen.
Source: Lecture 00, Slide 24.
The principle of strong induction states that if for some property $P(n)$, we have that $P(0)$ is true and for any $n \in \mathbb{N}$ with $n \neq 0$, if $P(0), P(1)$ ,..., and $P(n-1)$ are true, then $P(n)$ is true, then for any $n \in \mathbb{N}$, $P(n)$ is true.
In general, Strong Induction is good for showing that some property holds by breaking a large structure into multiple small pieces.
Source: Lecture 04, Slide 13.
A cycle that does not repeat any nodes or edges (except the first/last node).
Source: Lecture 05, Slide 35.
A path that does not repeat any nodes or edges.
Source: Lecture 05, Slide 35.
A step of a TM is one event where the TM takes a transition.
Source: Lecture 23, Slide 41.
A finite sequence of characters drawn from some alphabet.
Source: Lecture 11, Slide 17.
A subroutine of a Turing machine is a small set of states in the TM such that performs a small computation
Source: Lecture 17, Slide 19.
A set $A$ is a subset of $B$ (denoted $A \subseteq B$) when every element of $A$ is also an element of $B$.
Source: Lecture 00, Slide 41.
A method for transforming an NFA into a DFA.
Source: Lecture 14, slide 9.
A function is called surjective if each element of the codomain has at least one element of the domain associated with it.
Source: Lecture 06, Slide 17.
The symmetric difference of two sets $A$ and $B$, denoted $A \triangle B$, is the set of all elements that belong to exactly one of $A$ and $B$.
Source: Lecture 00, Slide 33.
A binary relation $R$ over a set $A$ is called symmetric iff: For any $x \in A$ and $y \in A$, if $xRy$, then $yRx$.
Source: Lecture 05, Slide 54.
A propositional logic formula $\varphi$ is a tautology iff every assignment to its variables is a satisfying assignment.
Source: Lecture 10, Slide 34.
Time complexity of a TM M is a function f(n) that measures the worst-case number of steps that M takes on an input of length n.
Source: Lecture 23, Slide 43.
An ordering where no node is listed before its predecessors.
Source: Lecture 05, Slide 44.
A binary relation $R$ over a set $A$ is called a total order iff it is a partial order and it is total.
Source: Lecture 05, Slide 79.
A binary relation $R$ over a set $A$ is called total iff for any $x \in A$ and $y \in A$, that $xRy$ or $yRx$ (or both).
Source: Lecture 05, Slide 79.
A binary relation $R$ over a set $A$ is called transitive iff: For any $x,y,z \in A$, if $xRy$ and $yRz$, then $xRz$.
Source: Lecture 05, Slide 59.
A Turing machine is a finite automaton equipped with an infinite tape as its memory. The tape begins with the input to the machine written on it, surrounded by infinitely many blank cells. The machine has a tape head that can read and write a single memory cell at a time.
Source: Lecture 17, Slide 8.
A Graph where the set of its edges $E$ consists of unordered pairs.
Source: Lecture 05, Slide 24.
The union of two sets $A$ and $B$, denoted $A \cup B$, is the set of all elements contained in $A$ or contained in $B$.
Source: Lecture 00, Slide 33.
The quantifier $\exists!$ that expresses that a proposition holds only true for a unique item. In CS103, we instead use the idiom $\exists n. (P(n)\wedge\forall m.(P(m)\rightarrow m=n$)) to express that $P(n)$ is true for only one $n$.
Source: Lecture 10, Slide 6.
A clause that contains just one literal.
Source: Lecture 10, Slide 68.
A universal statement is a statement of the form "for all $x$, $P(x)$ is true".
Source: Lecture 01, Slide 31.
There is a Turing Machine $U_{TM}$, called the universal turing machine that, when run on input <$M,w$>, where $M$ is a Turing machine and $w$ is a string, simulates $M$ running on $w$
Source: Lecture 19, Slide 28.
A set ${a,b}$ of two elements (remember that sets are unordered).
Source: Lecture 05, Slide 9.
A statement is vacuously true if it is true because it does not apply to anything.
Source: Lecture 00, Slide 42.
A Venn Diagram is a picture representing the overlap of two sets.
Source: Lecture 00, Slide 26.
Nodes of a graph.
Source: Lecture 05, Slide 24.
For any regular langague $L$, there exists a positive natrual number $n$ such that for any $w \in L$ with $|w| \geq n$, there exists string x,y,z such that for any natural number $i$,
$w = xyz$
$y \ne \epsilon$
$xy^iz \in L$Source: Lecture 14, Slide 119.
The XOR operator (denoted $\oplus$) is a logical operator that takes in two bits and returns 0 if they are the same and 1 if they are different.
Source: Lecture 01, Slide 36.