Theorem and Definition Reference

A

$A_{TM}$

The language of the universal Turing machine $U_{TM}$. Formally written as $A_{TM} = \{ \langle M, w \rangle | M\text{ is a Turing machine that accepts }w\}$.

Source: Lecture 20, slide 38.

Accepting State

An accepting state in an automaton is a state such that if the machine ends in that state, the machine accepts.

Source: Lecture 12, slide 41.

Accepts (Turing Machines)

A Turing Machine accepts a string $w$ if it enters an accept state.

Source: Lecture 20, slide 15.

Accepts (Nondeterministic Turing Machines)

A nondeterministic Turing machine accepts a string $w$ if it enters an accept state on some path.

Source: Lecture 20, slide 50.

Action/Goto Table

In the context of DPDAs, a table that says what operations to perform on the stack and what state toe nter on each input/stack pair.

Source: Lecture 17, slide 42.

$\aleph_0$ (Aleph-Nought)

$\aleph_0$ is the cardinality of $\mathbb{N}$. That is, $|\mathbb{N}| = \aleph_0$.

Source: Lecture 00, slide 91.

Alphabet

An alphabet is a finite set of characters, denoted by $\Sigma$.

Source: Lecture 12, slide 20.

Ambiguity

A CFG is said to be ambiguous if there is at least one string with two or more parse trees. Some languages are inherently ambiguous, meaning no unambiguous grammar exists for them.

Source: Lecture 16, slide 31.

Antecedent

When $P \implies Q$, we call P the antecedent and Q the consequent.

Source: Lecture 02, slide 9.

Antisymmetric

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 \neq x$, then $\lnot(y R x)$. Or equivalently, for any $x \in A$ and $y \in A$, if $xRy$ and $yRx$ then $x = y$.

Source: Lecture 06, slide 10.

Arbitrary Choice

In a proof, an object $x$ is chosen arbitrarily if it is picked without specifying which choice was made. The intent is to leave as much about $x$ unspecified as possible, so that any conclusions reached about $x$ can be said to hold as generally as possible.

Source: Lecture 01, slide 30.

Arity

The number of arguments a given predicate takes.

Source: Lecture 10, slide 10.

Automaton

A mathematical model of a computing device.

Source: Lecture 12, slide 9.

B

Base Case

Proof that a property, $P$, holds for the first segment in an inductive proof

Source: Lecture 03, slide 10.

Biconditional

$P$ If and Only If $Q$. ($P \iff Q$)

Source: Lecture 02, slide 24.

Big-O Notation

Big-O notation is a way of simply describing the time complexity of a problem by ignoring everything except the term that grows the fastest with respect to the input.

Formally, for two functions f : $\mathbb{N} \rightarrow \mathbb{N}$ and g : $\mathbb{N} \rightarrow \mathbb{N}$, then f(n) = O(g(n)) iff there exist constants c $\in \mathbb{R}$ and $n_{0} \in \mathbb{N}$ such that for any n $\geq$ $n_{0}$, f(n) $\leq$ cg(n).

For example, $4n + 4 = O(n)$, while $n^2 + 4 + 17n + n^n = O(n^n)$.

Source: Lecture 24, slide 21.

Bijective Function

A bijective function is a function that is injective and surjective.

Source: Lecture 06, slide 46.

Binary number system

The binary number system is a base 2 representation of numbers, as an example, $100_{2} = 1 * 2^2 + 0 * 2^1 + 0 * 2^0 = 4$

Source: Lecture 04, slide 22.

Binary relation

A binary relation is a property that describes whether two objects are related in some way.

Given binary relation $R$, we write $aRb$ iff $a$ is related to $b$ by relation $R$.

Source: Lecture 05, slide 43.

C

Cardinality

The cardinality of a set $S$, denoted $|S|$, is the number of elements that set contains. Two sets have the same cardinality if there is a one-to-one correspondence between the elements of the two sets.

Source: Lecture 00, slide 47.

Cantor's Pairing Function

$f(a,b) = (a+b)(a+b+1)/2 + a$, used in the proof that $|\mathbb{N}^2| = |\mathbb{N}|$.

Source: Lecture 07, slide 47.

Cantor's Theorem

Cantor's Theorem states that the cardinality of a set is always less than the cardinality of its power set. For any set $S$, $|S| < |\wp(S)|$.

Source: Lecture 00, slide 162.

Cartesian Product

The Cartesian Product of $A \times B$ of two sets is defined as $A \times B = \{(a,b) | a \in A \mbox{ and } b \in B \}$

Source: Lecture 05, slide 6.

Church-Turing Thesis

Every effective method of computation is either equivalent to or weaker than a Turing machine.

Source: Lecture 19, slide 84.

Clause

A clause is a many-way OR (disjunction) of literals.

Source: Lecture 11, slide 50.

Closure Property

A closure property of some class of languages is some operation that, if applied to languages within that class, produces a language still within that class.

Source: Lecture 13, slide 29.

co-RE

The set of languages whose complements are recognized by a TM.

Source: Lecture 23, slide 32.

co-recognizable

A language in co-RE is called co-recognizable.

Source: Lecture 23, slide 32.

co-unrecognizable

A language which is not in co-RE is called co-unrecognizable.

Source: Lecture 23, slide 32.

Cobham-Edmonds Thesis

A language L can be decided efficiently iff there is a TM that decides it in polynomial time.

Source: Lecture 24, slide 51.

Codomain

The codomain of a function is the set of elements into which the function maps.

Source: Lecture 06, slide 33.

Complement of a Language

If $L$ is a language over $\Sigma$, the complement of $L$ (denoted $\bar{L}$) is the set $\Sigma* - L$.

Source: Lecture 13, slide 27.

Complement Construction

The complement construction converts a DFA $D$ into a DFA $D'$ whose language is the complement of the language of $D$. It consists of switching all accepting states to rejecting states and vice-versa.

Source: Lecture 13, slide 23.

Complexity (Time)

The time complexity of a TM M is a function (typically denoted f(n)) that measures the worst-case number of steps M takes on any input of length n.

Source: Lecture 24, slide 15.

Complexity Class

The time complexity class TIME(f(n)) is the set of languages decidable by a singletape TM with runtime O(f(n)).

Source: Lecture 24, slide 39.

Complexity Class P

The complexity class P contains all problems that can be solved in polynomial time.

Formally, P is the union of all complexity classes TIME($n^k$), from k = 0 to infinity.

Source: Lecture 24, slide 53.

Complexity Class NP

The complexity class NP (nondeterministic polynomial time) contains all problems that can be solved in polynomial time by a single-tape NTM.

Formally, NP is the union of all complexity classes NTIME($n^k$), from k = 0 to infinity.

Source: Lecture 25, slide 48.

Composite

A natural number greater than 1 is composite if it is not prime.

Source: Lecture 20, slide 51.

Composition (Functions)

The composition of two functions $f$ and $g$ is the function $g \circ f$ defined as follows: $g \circ f(x) = g(f(x))$.

Source: Lecture 06, slide 50.

Computable Function

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 06, slide 19.

Concatenation

The concatenation of two languages $L_1$ and $L_2$ over the alphabet $\Sigma$ is the language $L_1 L_2 = \{wx \in \Sigma^{*} \vert w \in L_1 \wedge x \in L_2\}$.

Source: Lecture 14, slide 19.

(CNF) Conjunctive Normal Form

A propositional logic formula $\phi$ is in conjunctive normal form if it is the many-way AND (conjunction) of clauses.

Source: Lecture 11, slide 51.

Context-Free Grammar (CFG)

A formalism for defining the Context-Free Languages. Formally, a collection of four objects: (1) A set of nonterminal symbols (variables), (2) a set of terminal symbols (alphabet), (3) a set of production rules that convert nonterminals to terminals, (4) a start symbol that begins the derivation.

Source: Lecture 16, slide 06.

Context-Free Language (CFL)

If L is a language and there is some CFG G such that L = $\mathscr{L}$(G), then we say that L is a context-free language. Note: the Context-Free Languages are a strict superset of the Regular Languages.

Source: Lecture 16, slide 20.

Contrapositive

The contrapositive of "If $P$, then $Q$" is the statement "If not $Q$, then not $P$."

Source: Lecture 02, slide 49.

Consequent

When $P \implies Q$, we call P the antecedent and Q the consequent.

Source: Lecture 02, slide 9.

Continued Fraction

A continued fraction is either an integer $n$, or $n + 1/F$, where $n$ is an integer and $F$ is a continued fraction. For example, $1 + \frac{1}{2 + \frac{1}{3}}$ is a continued fraction.

Source: Lecture 04, slide 33.

Cook-Levin Theorem

The SAT problem is NP-complete.

Source: Lecture 26, slide 27.

Cycle

A cycle in a graph is a path from some node $u$ to itself.

Source: Lecture 05, slide 26.

D

DAG

See directed acyclic graph

Decidable

A language $L$ is called decidable if and only if there is a decider $M$ such that $\mathcal{L}(M) = L$. These languages are also sometimes called \textit{recursive}.

Source: Lecture 20, slide 19.

Decider

A Turing Machine which always halts (never goes into an infinite loop).

Source: Lecture 20, slide 18.

Decision Problems

A decision problem is a problem whose answer has a yes or no answer.

Source: Lecture 12, slide 16.

De Morgan's Laws

Pair of transformation rules that allow the expression of conjunctions and disjunctions purely in terms of each other via negation:
$\neg(P\land Q)\iff(\neg P)\lor(\neg Q)$

$\neg(P\lor Q)\iff(\neg P)\land(\neg Q)$


In simple English: "The negation of a conjunction is the disjunction of the negations" and "The negation of a disjunction is the conjunction of the negations".

Source: Lecture 09, slide 42.

Derivation

The sequence of steps that takes a Context-Free Grammar from nonterminals to terminals (and a member of the language). A leftmost derivation expands the leftmost nonterminal, where a rightmost derivation expands the rightmost nonterminal at each step.

Source: Lecture 16, slide 19.

Deterministic model of computation

A model of computation is deterministic if at every point in the computation, there is exactly one choice that can make.

Source: Lecture 13, slide 32.

DFA

A DFA (deterministic finite automaton) is a finite automaton where for every combination of a state and a symbol $a \in \Sigma$, there is exactly one transition defined.

Source: Lecture 12, slide 52.

Deterministic Context-Free Language (DCFL)

A context-free language that is recognized by a DPDA.

Source: Lecture 17, slide 45.

Deterministic Pushdown Automaton (DPDA)

A PDA with the extra property that for each state in the PDA, and for any combination of a current input symbol and a current stack symbol, there is at most one transition defined.

Source: Lecture 17, slide 39.

Diagonalization Language

The diagonalization language $L_D$ is definde as $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$. That is, $L_D$ is the set of descriptions of Turing Machines that do not accept descriptions of themselves.

Source: Lecture 21, slide 20.

Diagonal Set

The set $D = \{x \in S | x \not\in f(x)\}$. It eliminates the need for a two-dimensional table for diagonalization proofs.

Source: Lecture 07, slide 27.

Difference (set theory)

The difference of two sets (denoted $A - B$ or $A \backslash B$) is the set whose elements are all the elements contained in $A$, but not $B$. Formally, $A - B = \{ x | x \in A \mbox{ and } x \notin B \}$.

Source: Lecture 00, slide 67.

Directed Acyclic Graph

A directed acyclic graph (DAG) is a directed graph with no cycles.

Source: Lecture 05, slide 31.

Direct Proof

A direct proof is a proof that begins with a set of initial assumptions (called hypotheses), then applies sound logical reasoning to arrive at a conclusion.

Source: Lecture 01, slide 7.

Division Algorithm

For any integers $a$ and $b$, with $b > 0$, there exists unique integers $q$ and $r$ such that

$a = qb + r$ and

$0 \leq r < b$

$q$ is the quotient and $r$ is the remainder

Source: Lecture 04, slide 50.

Domain

The domain of a function is the set of elements that the function accepts as inputs.

Source: Lecture 06, slide 33.

Domain of Discourse

In first-order logic, each variable refers to some object in a set called the domain of discourse.

Source: Lecture 10, slide 8.

DPLL Algorithm

The DPLL algorithm is a modification of the simple backtracking search algorithm (named for Davis, Putnam, Logemann, and Loveland).

Source: Lecture 11, slide 62.

E

Effective Method of Computation

A form of computation with the following properties:

Computation consists of a set of steps

Fixed rules governing how one step leads to the next

Any computation that yields an answer does so in finitely many steps

Any computation that yields an answer always yields the correct answer

Source: Lecture 19, slide 83.

Element (set theory)

An element of a set is an object contained in that set. We write $x \in S$ if $x$ is an element of $S$, and $x \notin S$ otherwise.

Source: Lecture 00, slide 47.

Equality Problem

Given two strings $x$ and $y$, decide if $x = y$

Source: Lecture 15, slide 52.

Empty Set

The empty set (denoted $\emptyset$) is the set $\{\}$ containing no elements.

Source: Lecture 00, slide 40.

Empty String

The string containing no characters. Denoted $\epsilon$.

Source: Lecture 12, slide 20.

Empty Sum

A sum of no numbers is called the empty sum and is defined to be zero

Source: Lecture 03, slide 18.

Equisatisfiable

Two formulas $\phi$ and $\psi$ are equisatisfiable if $\phi$ is satisfiable iff $\psi$ is satisfiable.

Source: Lecture 11, slide 87.

Equivalence relation

A binary relation $R$ over a set $A$ is called an equivalence relation iff it is reflexive, symmetric, and transitive.

Source: Lecture 05, slide 58.

Equivalence Classes

Given an equivalence relation $R$ over a set $A$, for any $a \in A$, the equivalence class of a is the set

$[a]_R = \{x | x \in A$ and $aRx \}$

$R$ partitions the set $A$ into a set of equivalence classes

Source: Lecture 05, slide 63.

Even Number

An integer $x$ is even if it can be written as $2k$ for some integer $k$. By this definition, 0 is an even number.

Source: Lecture 01, slide 8.

Existential Quantifier

$\exists$ is the existential quantifier, and $\exists v$ says "for some choice of $v$, the following is true".

Source: Lecture 10, slide 20.

Existential Statement

An existential statement is a statement of the form "there is some $x$ where $P(x)$ is true."

Source: Lecture 01, slide 62.

Existence and Uniqueness Proof

An existence proof is a proof that there is exactly one object meeting some criterion. It is typically split into an existence proof that shows that at least one object satisfying the criterion exists, and a uniqueness proof that shows that at most one object satisfying the criterion exists.

Source: Lecture 05, slide 67.

F

Finite Automata

Mathematical machines for determining whether a string is contained within some language. An abstraction of computers with finite resource constraints. Provide upper bounds for the computing machines that we can actually build.

Source: Lecture 12, slide 13.and 26.

Finite Set

A finite set is a set containing finitely many elements.

First-Order Logic

A logical system for reasoning about properties of objects.

Source: Lecture 10, slide 4.

Formal Language

A set of strings.

Source: Lecture 12, slide 21.

Function

A function is a means of associating each object in one set (the domain) with an object in a different set (the codomain).

Source: Lecture 06, slide 29.

G

Graph

A graph is an ordered pair $G = (V,E)$ where $V$ is a set of vertices (nodes) and $E$ is a set of the edges (arcs) of the graph.

Source: Lecture 05, slide 17.- 21.

H

Halts (Turing Machine)

A Turing Machine halts if it accepts or rejects.

Source: Lecture 20, slide 15.

Halting Problem

Give a Turing Machine $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 TM that halts on } w. \right\rbrace$. Additionally, $\overline{HALT} = \left\lbrace \langle M,w \rangle \Big\vert M \text{ is a TM that does not halt on } w\right\rbrace$.

Note: $HALT \in RE$ and $\overline{HALT} \not\in RE$.

Source: Lecture 21, slide 49.and Lecture 22, slide 3.

Hasse Diagram

A Hasse diagram is a drawing of a partial order in which there are no self-loops, no redundant edges, and in which the edges are implicitly directed upward.

Source: Lecture 06, slide 22.- 21.

Heuristic

A heuristic is an approach to solving a problem that may or may not work correctly.

Source: Lecture 11, slide 59.

I

Induction

The principle of mathematical induction states that if for some property $P(n)$, we have that $P(0)$ is true and for any $n \in N$ and we have $P(n)$ $\implies$ $P(n + 1)$, then for any $n \in N$, $P(n)$ is true.

Source: Lecture 03, slide 5.

Inductive Hypothesis

The property $P(n)$ shown to hold over a sequence through an inductive proof

Source: Lecture 03, slide 5.

Inductive Step

Proof within an inductive proof that for all $n \in N$, $P(n) \implies P(n\A0+\A01)$

Source: Lecture 03, slide 10.

Implication

An implication is a statement of the form: If $P$, then $Q$. ($P\implies Q$)

Whenever $P$ is true, $Q$ must be true as well.

Source: Lecture 02, slide 9.

Independent Set

An independent set in an undirected graph is a set of vertices that have no edges between them

Source: Lecture 26, slide 44.

Injective Function

An injective function is a function that associates each element of the domain with a unique element in the codomain. Formally, $f$ is injective iff whenever $f(a_0) = f(a_1)$, we have $a_0 = a_1$.

Source: Lecture 06, slide 41.

Infinite Cardinals

Cardinal numbers introduced to denote the size of infinite sets, such as $\mathbb{Z}$ and $\mathbb{R}$.

Source: Lecture 06, slide 53.

Infinite Set

An infinite set is a set containing infinitely many elements.

Source: Lecture 00, slide 48.

Input String

The string fed into an automaton.

Source: Lecture 12, slide 31.

Instantaneous Description (ID)

An instantaneous description (or ID) of the execution of a program (TM, WB program, etc.) is a string encoding of a snapshot of that program at one instant in time.

Source: Lecture 20, slide 64.

Integer

An integer is a positive or negative whole number (e.g. -3, -2, -1, 0, 1, 2, 3, ...). The set of all integers is denoted $\mathbb{Z}$

Source: Lecture 00, slide 48.

Intersection (set theory)

The intersection of two sets (denoted $A \cap B$) is the set whose elements are all the elements contained in both $A$ and $B$. Formally, $A \cap B = \{ x | x \in A \mbox{ and } x \in B \}$.

Source: Lecture 00, slide 65.

Irrational Number

A number that is not rational is called irrational.

Source: Lecture 02, slide 28.

K

Kleene Clousure

Operation on languages defined as $L^{*} = \bigcup_{i=0}^{\infty} L^{i}$

Source: Lecture 14, slide 25.

L

Language (of an automaton)

The language of an automaton is the set of strings that it accepts.

Source: Lecture 12, slide 48.

Language (of a regular expression)

The language of a regular expression is the language described by that regular expression

Source: Lecture 15, slide 7.

Lemma

A lemma is a small result that helps establish a larger theorem.

Source: Lecture 01, slide 119.

Literal

A literal in propositional logic is a variable or its negation.

Source: Lecture 11, slide 50.

Loop Invariant

A loop invariant is a statement of the conditions that should be true on entry into a loop and that are guaranteed to remain true on every iteration of the loop. Loop invariants are used in some inductive proofs.

Source: Lecture 03, slide 49.

Logical Connectives

Operators used to encode how propositions are related. Examples of logical connectives are logical negation, conjuction, disjunction, implication and biconditional.

Source: Lecture 09, slide 14.

Logical Conjunction: $(p \wedge q)$

Logical AND (read as "p AND q"). $(p \wedge q)$ is true if both p and q are true.

Source: Lecture 09, slide 16.

Logical Disjunction: $(p \lor q)$

Logical OR (read as "p OR q"). $(p \lor q)$ is true if at least one of p and q are true (inclusive OR).

Source: Lecture 09, slide 16.

Logical Equivalence

If two propositional logic statements always have the same truth values as one another, they are called logically equivalent.

Source: Lecture 09, slide 41.

Logical Implication: $(p \to q)$

$(p \to q)$ means: if $p$ is true, $q$ is true as well. Note it doesn't say nothing about what happens when $p$ is false.

Source: Lecture 09, slide 20.

Logical Negation ¬p

Logical NOT (read as "not p"). ¬p is true iff p is false.

Source: Lecture 09, slide 16.

Loops

See loops infinitely.

Loops Infinitely (Turing Machines)

A Turing Machine loops infinitely (or just loops) on a string $w$ if it neither enters an accept nor a reject state.

Source: Lecture 20, slide 15.

Loops Infinitely (Nondeterministic Turing Machines)

A nondeterministic Turing machine loops infinitely on a string $w$ if it doesn't accept on any path and doesn't reject on every path.

Source: Lecture 20, slide 50.

M

Mapping

If $f$ is a function from $A$ to $B$, we sometimes say that $f$ is a mapping from $A$ to $B$, in which $A$ is the domain and $B$ is the codomain of $f$.

Source: Lecture 06, slide 33.

Mapping Reducible

$A$ is mapping reducible if there is a mapping reduction from $A$ to $B$. Notation: $A \le_M B$.

Theorems:

• If $B \in R$ and $A \le_M B$, then $A \in R$.
• If $B \in RE$ and $A \le_M B$, then $A \in RE$.
• If $A \not \in R$ and $A \le_M B$, then $B \not \in R$.
• If $A \not \in RE$ and $A \le_M B$, then $B \not \in RE$.

Source: Lecture 22, slide 25.

Mapping Reduction

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 22, slide 24.

Matching

Given an undirected graph G, a matching in G is a set of edges such that no two edges share an endpoint.

Source: Lecture 25, slide 11.

Maximum Matching

A maximum matching is a matching with the largest possible number of edges.

Source: Lecture 25, slide 11.

Memory Device

A device that an automaton can use to store extra information.

Source: Lecture 17, slide 7.

N

Natural Number

A natural number is a whole number greater than or equal to zero (e.g. 0, 1, 2, 3, ...) . The set of all natural numbers is denoted $\mathbb{N}$.

Source: Lecture 00, slide 48.

NFA

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 31.

(NNF) Negation Normal Form

A function is in Negation Normal Form if the only connectives are $not$, $\wedge$, and $\vee$, and $\neg$ is only applied directly to variables.

Source: Lecture 11, slide 71.

Nondeterministic model of computation

A model of computation is nondeterministic if the computing machine may have multiple decisions that it can make at one point. The machine accepts if any series of choices leads to an accepting state.

Source: Lecture 13, slide 32.

Nondeterministic Turing machine (NTM)

A Turing machine in which there may be multiple transitions defined for a particular state/input combination. If any possible set of choices causes the machine to accept, it accepts.

Source: Lecture 20, slide 49.

NP

The complexity class NP (nondeterministic polynomial time) contains all problems that can be solved in polynomial time by a single-tape NTM.

Formally, NP is the union of all complexity classes NTIME($n^k$), from k = 0 to infinity.

Source: Lecture 25, slide 48.

NP-complete

A language L is called NP-complete iff L is NP-hard and L $\in$ NP

Source: Lecture 26, slide 20.

NP-hard

A language L is called NP-hard iff for every L' $\in$ NP, L' can be polynomial-time reduced to L.

Source: Lecture 26, slide 20.

O

Odd Number

An integer $x$ is odd if it can be written as $2k + 1$ for some integer $k$.

Source: Lecture 01, slide 8.

Order Relation

A relation that ranks elements against one another.

Source: Lecture 06, slide 4.

P

P

The complexity class P contains all problems that can be solved in polynomial time.

Formally, P is the union of all complexity classes TIME($n^k$), from k = 0 to infinity.

Source: Lecture 24, slide 53.

Palindrome

A string that is the same forwards and backwards.

Source: Lecture 17, slide 21.

Parse Tree

A tree encoding the steps in a derivation.

Source: Lecture 16, slide 29.

Partial Order

A binary relation $R$ is a partial order over a set $A$ iff it is reflexive, antisymmetric, and transitive.

Source: Lecture 06, slide 12.

Partially Ordered Set

A pair $(A,R)$, where $R$ is a partial order over $A$, is called a partially ordered set (or poset).

Source: Lecture 06, slide 12.

Path

A path between two nodes $u$ and $v$ in a graph $G$ is a sequence of edges in $G$ that starts at $u$ and ends at $v$.

Source: Lecture 05, slide 21.

Piecewise Function

A piecewise function is a function defined by a rule that is defined by cases.

Source: Lecture 06, slide 39.

Pigeonhole Principle

If $m$ objects are distributed in $n$ bins such that $m$>$n$, then some bin contains at least two objects.

Source: Lecture 02, slide 62.

Polynomial Time

Any problem where the solution requires a number of steps that scales polynomially with the size of the problem is a polynomial-time problem.

More formally, any problem that can be solved in TIME($n^k$) is in polynomial time.

Source: Lecture 24, slide 53.

Polynomial Time Reduction

A polynomial-time mapping reduction is a function $f : \Sigma_1^* \rightarrow \Sigma_2^*$ with the following properties:

$f(w)$ can be computed in polynomial time.

$w \in A \space iff \space f(w) \in B.$

Source: Lecture 24, slide 67.

Polynomial Time Verifier

A polynomial-time verifier is a deterministic TM that takes as input '<'w,x'>' and deterministically checks whether the string x solves the problem w (also a string).

This verifier needs to run in time polynomial with respect to the length of w (not the length of x)

Source: Lecture 25, slide 53.

Pop

To remove a symbol from the top of a stack (of a PDA).

Source: Lecture 17, slide 9.

Power Set

The power set of a set $S$, denoted $\wp(S)$, is the set of all subsets of $S$.

Source: Lecture 00, slide 85.

Predicate

A logical connective in first-order logic which describes the properties of objects.

Source: Lecture 10, slide 4.

Predict/Match Parser

A PDA (corresponding to a CFG) where each step either predicts which production to use or matches some symbol of the input.

Source: Lecture 17, slide 34.

Proposition

A proposition is a statement that is, by itself, either true or false (but not both)

Source: Lecture 09, slide 7. and Rosen, page 2.

Propositional Logic

Propositional logic is a mathematical system for reasoning about propositions and how they relate to one another.

Source: Lecture 09, slide 13.

Propositional Variables

A variable which that is either true or false.represents a proposition.

Source: Lecture 09, slide 14.

Proof by Cases

Proof by Exhaustion

A proof by cases is a proof in which several different possibilities are listed, and each possibility is proven independently. Many proofs contain a proof by cases as a small piece of a larger result.

Source: Lecture 00, slide 84.

Proof by Contradition

Proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition\92s false would imply a contradiction.

Source: Lecture 02, slide 19.

Proof by Contrapositive

To prove $P \implies Q$, prove $\neg Q \implies \neg P$.

Source: Lecture 02, slide 52.

Proper Subset

A set $S$ is a proper subset of a set $T$ (denoted $S \subset T$) when $S \subset T$ and $S \neq T$.

Source: Lecture 00, slide 80.

Pumping Lemma for Regular Language(Weak)

Theorem that describes an essential property of all regular languages. Informally, it says that any string of length 3 or greater can be split into three pieces, the second of which can be “pumped.� that is, have a middle section of the word repeated an arbitrary number of times — to produce a new word which also lies within the same language.

Source: Lecture 15, slide 49.

Pumping Lemma for Context-Free Languages

For any context-free language $L$, there exists a positive natural number $n$ such that for any $w \in L$ with |$w$| $\ge n$, there exists strings $u,v,x,y,z$ such that for any natural number $i$: $w = uvxyz$, |$vxy$| $\le n$, |$vy$| $> 0$, and $uv^ixy^iz \in L$.

Source: Lecture 18, slide 14.

Pure Literal

A literal is called pure if its negation appears nowhere in the formula.

Source: Lecture 11, slide 60.

Push

To put a symbol onto the top of a stack (of a PDA).

Source: Lecture 17, slide 9.

Pushdown Automaton (PDA)

A finite automaton equipped with a stack-based memory.

Source: Lecture 17, slide 10.

Q

Quantifier

A logical connective in first-order logic which allows us to reason about multiple objects simultaneously.

Source: Lecture 10, slide 4.

R

Rational Number

A rational number is a number $r$ that can be written as $r=\frac{p}{q}$ where $p$ and $q$ are integers, $q \neq 0$ and $p$,$q$ have no common divisors other than $\pm$ 1.

Source: Lecture 02, slide 28.

Reachable

A node $v$ is reachable from a node $u$ iff there is a path from $u$ to $v$.

Source: Lecture 05, slide 23.

Real Number

A real number is any number that can be represented by a number with a (possibly repeating) infinite decimal (e.g. $0, 137, e, \pi, \sqrt{2}$, ...). The set of all real numbers is denoted $\mathbb{R}$.

Source: Lecture 00, slide 48.

Recognizable

See recursively enumerable.

Recognizer

A Turing Machine for a language $L$ is a recognizer for $L$.

Source: Lecture 20, slide 17.

Recursive

See decidable.

Recursively Enumerable

A language is called recognizable or recursively enumerable if it is the language of some Turing Machine. The set of all recognizable languages is denoted $RE$.

Source: Lecture 20, slide 16.

Reduction

A reduction from A to B is a function $f: \Sigma_1^{\ast} \rightarrow \Sigma_2^{\ast}$ such that for any $w \in \Sigma_1^{\ast}, w \in A \text{ iff } f(w) \in B$

Source: Lecture 22, slide 11.

Reflexive

A binary relation R over a set A is called reflexive iff

For any $x \in A$ we have $xRx$

Source: Lecture 05, slide 52.

Refuter

A language $L$ is in co-RE if and only if there is a refuter for it: a Turing Machine which rejects a string $w$ if $w \not\in L$ and accepts $w$ if $w \in L$.

Source: Lecture 23, slide 33.

Regular Expression

A family of descriptions that can be used to capture the Regular Languages.

Source: Lecture 14, slide 36.

Regular Language

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 22.

Rejects (Turing Machines)

A Turing Machine rejects a string $w$ if it enters a reject state.

Source: Lecture 20, slide 15.

Rejects (Nondeterministic Turing Machines)

A nondeterministic Turing machine rejects a string $w$ if it enters a reject state on every path.

Source: Lecture 20, slide 50.

S

SAT (Boolean Satisfiability Problem)

Given a propositional logic formula $\phi$, is $\phi$ satisfiable?

Source: Lecture 11, slide 37.

Satisfiability

A propositional logic formula $\phi$ is called satisfiable if there is some assignment to its variables that makes it evaluate to true.

Source: Lecture 11, slide 36.

Satisfying Assignment

An assignment of true and false to variables of $\phi$ that makes it evaluate to true.

Source: Lecture 11, slide 36.

Set

A set is an unordered collection of distinct elements, which can be anything (including other sets).

Source: Lecture 00, slide 23.

Set-Builder Notation

Set-builder notation is a notation for describing sets by listing some property of their elements. Formally, the set $\{\mbox{variable }|\mbox{ conditions on variable}\}$ is the set of all objects matching the specified condition. It is also possible to use set-builder notation to describe a transformation to be applied the the elements in the set.

Source: Lecture 00, slide 55.

Simple Cycle

A simple cycle in a graph is a path with no duplicated nodes or edges, other than the very first and very last node.

Source: Lecture 05, slide 27.

Simple Path

A simple path in a graph is a path with no duplicated nodes or edges.

Source: Lecture 05, slide 27.

Simulation

A technique used in computability theory, where we learn about the relationships of automata $A'$ and $A$ by building $A'$ to simulate the behavior of $A$.

Source: Lecture 14, slide 11.

Stack Alphabet

The set of symbols that can be puhsed onto the stack.

Source: Lecture 17, slide 18.

Stack Start Symbol

The symbol that the stack contains at the beginning of a PDA simulation.

Source: Lecture 17, slide 18.

Start State

The initial state that an automaton begins in.

Source: Lecture 12, slide 32.

States

Each finite automaton consists of a set of states connected by transitions.

Source: Lecture 12, slide 27.

String

A finite sequence of characters drawn from some alphabet.

Source: Lecture 12, slide 20.

Strong Induction

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 N$ with $n \neq 0$, if $P(n')$ is true for all $n' < n$, then $P(n)$ is true then

for any $n \in N$, $P(n)$ is true

Source: Lecture 04, slide 15.

String Homomorphism

Given two alphabets $\Sigma_1,\Sigma_2$, and a function $h: \Sigma_1 \to \Sigma_2^*$, the function $h^* : \Sigma_1^* \to \Sigma_2^*$ formed by applying $h$ to each character of a string $w$ is called a homomorphism.

Source: Lecture 15, slide 35.

Subset

A set $S$ is a subset of a set $T$ (denoted $S \subseteq T$) when every element of $S$ is also an element of $T$.

Source: Lecture 00, slide 78.

Subset Construction

A method for transforming an NFA into a DFA.

Source: Lecture 14, slide 13.

Surjective Function

A surjective function is a function such that every element in the codomain is mapped to by some element of the domain. Formally, $f$ is surjective iff whenever for any $b$ in the codomain, there is some $a$ in the domain such that $f(a) = b$.

Source: Lecture 06, slide 43.

Symmetric Difference (set theory)

The symmetric difference of two sets (denoted $A \triangle B$) is the set whose elements are all the elements contained in exactly one of $A$ and $B$. Formally, $A \cup B = \{ x | x \in A \mbox{ and } x \notin B \mbox{, or } x \notin A \mbox{ and } x \in B \}$.

Source: Lecture 00, slide 70.

Symmetry

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 50.

T

Tautology

A statement that is always true

Source: Lecture 09, slide 57.

Time Complexity

The time complexity of a TM M is a function (typically denoted f(n)) that measures the worst-case number of steps M takes on any input of length n.

Source: Lecture 24, slide 15.

Time Complexity Class

The time complexity class TIME(f(n)) is the set of languages decidable by a singletape TM with runtime O(f(n)).

Source: Lecture 24, slide 39.

NTime Complexity Class

The time complexity class NTIME(f(n)) is the set of languages decidable by a singletape NTM with runtime O(f(n)).

Source: Lecture 25, slide 47.

Topologogical ordering

A topological ordering of the nodes of a DAG is one where no node is listed before its predecessors

Source: Lecture 05, slide 40.

Total Relation

A binary relation $R$ over a set $A$ is called total iff for any $x \in A$ and $y \in A$, $xRy$ or $yRx$.

Source: Lecture 06, slide 17.

Total Order

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 06, slide 17.

Transitions

Each finite automaton consists of a set of states connected by transitions. The automaton always follows the transition corresponding to the current symbol being read.

Souce: Lecture 12, slides 27 and 34.

Transitivity

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 55.

Turing Machine

A finite automaton equipped with an infinite tape as its memory. The machine has a tape head that can read and write a single memory cell at a time.

Source: Lecture 18, slide 34.

U

Unit Clause

A unit clause is a clause containing just one literal.

Source: Lecture 11, slide 61.

Union (set theory)

The union of two sets (denoted $A \cup B$) is the set whose elements are all the elements contained in at least one of $A$ or $B$. Formally, $A \cup B = \{ x | x \in A \mbox{ or } x \in B \}$.

Source: Lecture 00, slide 63.

Universal Quantifier

$\forall$ is the universal quantifier, and $\forall n$ says "for any choice of $n$, the following is true."

Source: Lecture 10, slide 18.

Universal Statement

A universal statement is a statement of the form "for all $x$, $P(x)$ is true."

Source: Lecture 01, slide 62.

Universal Turing Machine

A Turing machine $U_{TM}$ that, when run on $\langle M, w \rangle$, where $M$ is a Turing machine and $w$ is a string, simulates $M$ running on $w$.

Source: Lecture 20, slide 34.

Uniqueness Proof

To prove there is a unique object with some property we can consider any two arbitary objects $x$ and $y$ with that property and show that $x = y$

Source: Lecture 05, slide 69.

Unsatisfiable

A propositional logic formula $\phi$ is called unsatisfiable if no assignment to its variables makes it evaluate to true.

Source: Lecture 11, slide 36.

V

Vacuous Truth

A statement is vacuously true if it is true because it does not apply to anything.

Source: Lecture 00, slide 79.

Venn Diagram

A Venn Diagram is a pictorial representation of how the elements of various sets overlap with one another.

Source: Lecture 00, slide 57.

w

WB

A programming language ("Wang B-machine") controls a tape head over a singly-infinite tape, as in a normal Turning machine. Any WBn langauge can be written in the terms of a WBn-1 language. The WB language can be written as a Turing Machine.

Language has six commands: Movie left or right, write a symbol to tape, go to an instruction, if reading a symbol $s$ go to instruction $n$, and Accept and Reject commands that end the program

Source: Lecture 19, slide 08.

WB2

The programming language WB2 is the language WB with two new commands

Move left until the tape head reads a symbol in a set $S$

Move right until the tape head reads a symbol in a set $S$

Source: Lecture 19, slide 25.

WB3

The programming language WB3 is the language WB2 with support for variables (only finitely many, each holds a single tape symbol, and each initially holds the blank symbol) and the following new commands

Set a variable $v$ equal to a tape symbol $s$

Set a variable $v$ equal to the currently-scanned tape symbol

If two variables have the same value, go to instruction $n$

Source: Lecture 19, slide 36.

WB4

WB4 is equivalent to WB3 except it has finitely many tracks on the tape.

The tape head still moves as a unit and all previous commands are updated to specify which track is to be read or written.

Source: Lecture 19, slide 52.

WB5

WB5 is equivalent to WB4 with the addition of a finite number of stacks and the following three commands.

Push symbol $s$ onto stack $v$

If stack $v$ is empty, go to instruction $n$

Pop stack $v$ into stack $w$

Source: Lecture 19, slide 58.

WB6

WB6 is equivalent to WB5 with the addition of multiple tapes, all tape commands have to be updated to specify which tape they apply to, with tape 1 as the default.

Source: Lecture 19, slide 69.