Mathematical Foundations of Computing

Computability Theory

• Turing Machine

  • Church–Turing thesis: a Turing machine can simulate every effective form of computation.

    • In other words, no computation can be more effective than a Turing machine.

  • Terminology

    • (accepts, rejects, loops) on a string

    • halts - accepts or rejects (does not loop)

    • does not accept - rejects or loops

  • Decider - TM will always halt, never loops

    • Definitely accepts $w$ when $w\in L$ and rejects $w$ when $w\not\in L$

    • mn TM always decides (never loops)

    • R - set of all languages that have a decider for it

    • if CFG then decidable

  • Recognizer - always accepts $w\in L$. Either rejects or loops on $w$ when $w\not\in L$

    • a Turing machine is a recognizer for $L$ ↔ (it will eventually accept an string $s$ ↔ $s\in L$)

    • mn always recognizes (always accepts when it should)

    • A Turing machine $M$ recognizes (or is a recognizer for) a language $L$ if:

      • If $s \in L$, $M$ eventually accepts $s$

      • If $s \notin L$, $M$ either rejects $s$ or loops forever

    • Formally, $∀w ∈ Σ^*. (w ∈ L ↔ M \text{ accepts } w)$

    • Annoyingly, if you don't know if $w\in L$ and the TM is still running, you can't tell if it loops or just needs more time

    • RE - set of all languages that have a recognizer for it

• Context-free language is the set of strings generated by a context-free grammar

  • There are nonterminal and terminal symbols

  • starting symbol - at the top left

  • Production: a rule going from nonterminal $\Rightarrow$ nonterminal/terminals

  • derivation - set of

    • $A\Rightarrow^*B$ means B can be derived from A (* means multiple)

• Myhill–Nerode Theorem - if $L$ is a language and $S$ is a distinguishing set of $L$ with infinitely many strings then $L$ is nonregular

• Distinguishability - two strings $x$ and $y$ in $\Sigma^\star$ are distinguishable ($x\not\equiv_Ly$) if $xw\in L$ and $yw\not\in L$ (e.g., $x=aa$, $y=aaaa$, and $w=bb$) for some string $w$

  • Formally, $\exists w\in\Sigma^\star.(xw\in L\leftrightarrow yw\not\in L)$

  • Layman: Distinguishable if there is a string w you can add to one that will make it accepting but adding w to the other will make it rejected

  • Distinguishing set - set where each item is distinguishable from each other item

• Constructing NFAs

  • Have the NFA guess the information you want and deterministically check if it is true (guess-and-check technique)

• Regular languages

  • Regular languages are problems that can be solved with finite memory. Nonregular languages correspond to languages that cannot be solved with finite memory, such as $\{a^nb^n|n\in\mathbb N\}$.

  • The following are equivalent: L is a regular language, there exists an NFA or DFA or regex called X such that $\mathscr L(X)=L$ (the language of X is L)

• Kleene closure/star of a language L is L*, which is the set of all strings that can be formed by concatenating any number of strings in L (e.g., L={a,b} means L*={ε, a, b, aa, ab, ba, bb, aaa, ...})

  • Formally, $L^\star=\{w\in\Sigma^\star~|~\exists n\in\mathbb N.w\in L^n~\}$

• Closure properties of languages. If $L_1$ and $L_2$ are regular languages, so are these: $\overline {L_1},\quad L_1\cup L_2,\quad L_1\cap L_2,\quad L_1L_2,\quad L_1^*$

• Language concatenation $L_1L_2$ is the language $\{xy~|~x\in L_1\land y\in L_2\}$

  • xy is the strings x and y concatenated

• Finite automaton - collection of states joined by transitions, has a start state

  • Some states are accepting states. If automaton ends at accepting state, it accepts the input else rejects the input

  • DFA (Deterministic Finite Automaton) - exactly 1 transition at each state for each symbol in $\Sigma$

  • NFA (nondeterministic finite automaton) - each state has 0 or multiple transitions

    • If there is one path that works, NFA accepts

    • Path dies if cannot move at a certain symbol

    • ε-transition - transition that doesn't consume input

    • Works by perfect positive guessing or massive parallelism

    • the term nondeterministic means the automaton has a finite number of choices (possibly 0) to make at a given point

  • Subset construction (AKA powerset construction) is a method for turning an NFA into a DFA

  • A language is regular if there is a DFA D (or NFA) such that $\mathcal L(D)=L$, in which case D recognizes L

• Language - string[]

  string - character[]

  alphabet - set<character>

  • (formal) language - set of strings

    • language over $\Sigma$ if is set of strings each over $\Sigma$

    • $\Sigma^*$ is the set of all strings composed from letters in $\Sigma$

  • String

    • empty string - $\varepsilon$

    • String over $\Sigma$ - finite sequence of characters from $\Sigma$ (such as aaaabbaba for $\Sigma=\{a,b\}$)

  • Alphabet $\Sigma$ - set of characters

  • Characters

• Automaton - mathematical model of a computer (abstraction of real computer)

• states linked by transitions

Discrete Math

• Induction

  • P(0) is true - basis/base case

  • P(k) → P(k+1) - inductive step

    • P(k) - inductive hypothesis

  • To prove

• Pigeonhole principle

  • if $n$ items are put into $m$ containers, with $n > m$ , then at least one container must contain more than one item

  • Generalized pigeonhole principle (AKA strong pigeonhole principle)

    • For p pigeons and h holes,

      • some crowded hole will have at least $\lceil {p\over h} \rceil$ pigeons in it

      • not all holes can have more than $\lfloor{p \over h}\rfloor$ pigeons in them

        • some hole will have $\lfloor{p \over h}\rfloor$ or fewer pigeons

• $G^C$ is the graph complement of $G$. All edges are turned into not edges and all not edges are turned into edges in $G^C$.

• subset symbols

  • $\subsetneq$ - proper/strict subset. Cannot be itself.

  • $\subseteq$ - subset or equal

    • includes the improper subset case in which a set is the (improper) subset of itself

  • $\subset$ is ambiguous (could mean $\subseteq$ or $\subsetneq$ in different textbooks)

• Generalized pigeonhole principle

  • For p pigeons and h holes,

    • some hole will have at least $\lceil {p\over h} \rceil$ pigeons in it

    • some hole will have at most $\lfloor{p \over h}\rfloor$ pigeons in it

• The "composition of f and g" is $g\circ f$

• Translating first-order logic to English in a proof:

  

• Functions

  • domain - function defined for every element of domain

  • codomain - output is always in codomain. Not all els in codomain must have an associated output of the f tho

    

  • $f : A\to B$ means f has domain A and codomain B

  • Involution: a function f is an involution if $\forall a\in A.f(f(a))=a$

    • Layman: apply twice gives same thing back. f is an involution if f(f(x))=x

  • Surjective: $\forall b\in B.\exists a\in A.(f(a)=b)$

    • Layman: all outputs have an input that points to it

  • Injective: $\forall a_1\in A.\forall a_2\in A.(a_1\not=a_2\to f(a_1)\not=f(a_2))$

    • Equivalently $\forall a_1\in A.\forall a_2\in A.(f(a_1)=f(a_2)\to a_1=a_2)$

    • Layman: one-to-one function. No no output maps to two inputs. Every output maps to 1 or 0 inputs.

      • one-to-one function (not every codomain element needs to be used)

      • horizontal line test in y=f(x) tells you if a function is injective

  • Said differently, surjective associates each codomain element with at least one domain element and injective associates each codomain element with at most one domain element

  • bijective - injective and surjective, one-to-one correspondence (ever codomain element used)

  • Function needs to be:

    1. $\forall a\in A.\exists b\in B.(f(a)=b)$ - total

       • Defined on every element in domain, as opposed to partial, which means that f(a) is undefined for some a in the domain

         • Partial - $\exists a\in A.f(a)\text{ is undefined}$

    2. $\forall a_1\in A.\forall a_2\in A.(a_1=a_2\to f(a_1)=f(a_2))$ - deterministic (same input always produces same output)

• Proof explains why theorem is true

  Disproof explains why claim is false (such as through a counterexample)

• Transformations

  • $\underline{\lnot\forall x.A}$

    $\exists x.\lnot A$

  • $\underline{\lnot\exists x.A}$

    $\forall x.\lnot A$

  • $\underline{ \lnot (A\land B)} - \text{2 ways}$

    $\lnot A\lor \lnot B$ (De Morgan's Law)

    $A\to\lnot B$

  • $\underline{\lnot(A\lor B)}$

    $\lnot A\land \lnot B$ (De Morgan's Law)

  • $\underline{\lnot(A\to B)}$

    $A\land\lnot B$

  • $\underline{\lnot(A\leftrightarrow B)}$

    $\lnot A\leftrightarrow B$

    $A\leftrightarrow\lnot B$

  • Mnemonics

    • "Pushing" $\lnot$ inward and flipping between operators (or vice versa):

      • $\land$ to $\to$

      • $\forall$ to $\exists$

    • De Morgan's Law is like distributing the $\lnot$ and flipping the operator (from $\land$ to $\lor$ or vice versa)

    • When applying $\lnot$ to the biconditional ($\leftrightarrow$) negate either side and keep the operator same

    • $p \to q$ is the same as $\lnot(p \land \lnot q)$

      • only false when p is true and q is false

  • Others

    • $p\to b\to r$ same as $p\land q\to r$

• The Aristotelian Forms

  • All As are Bs: $\forall x.(A(x) \to B(x))$

  • No As are Bs: $\forall x.(A(x)\to \lnot B(x))$

  • Some As are Bs: $\exists x.(A(x) \land B(x))$

  • Some As aren't Bs: $\exists x.(A(x)\land\lnot B(x))$

• First-order logic

  • Terms

    • Functions - object → object

      Predicate - object → bool

    • Connective - bool(s) → bool

      • conjunction - $\land$ (binary)

      • disjunction - $\lor$

      • implication - $\to$

      • biconditional - $\leftrightarrow$

      • negation - $\lnot$ (unary)

      • truth - $\top$ (nullary)

      • falsity - $\bot$

    • Quantifier - bool → bool

  • Examples

    • = operates on objects, $\leftrightarrow$ operates on predicates

    • Some P is a Q translates to $\exists x.(P(x) \land Q(x))$

    • All Ps are Qs translates to $\forall x.(P(x)\to Q(x))$

  • Try to pair $\exists$ with $\land$ and $\forall$ with $\to$

• Precedence (highest to lowest)

  • $\lnot$

  • $\forall$ and $\exists$

  • $\land$ (and before or)

  • $\lor$

  • $\to$

    • $\to$ is right-associative so $a\to b\to c$ is $a \to (b\to c)$. Most operators like $\land$ are left-associative.

  • $\leftrightarrow$

• Propositional logic

  • Propositional variable

  • Propositional connectives

• Universal statement - for all x, some [property] holds for x (mn works on x universally)

• Existential statement - there is some x where [property] holds for x (mn some x exists for it to work)

• Proof types

  • Implication: If antecedent, then consequent.

    • Assume step: assume the antecedent is true

    • Want-to-show steps

    • demonstrate that the consequent is true

    • Reiterate what you wanted to show$\square$

Derivations

Myhill-Nerode Theorem

Myhill–Nerode Theorem: if L is a language and S is a distinguishing set for $L$ that contains infinitely many strings then $L$ is nonregular.

Proof: Pick an arbitrary language $L$ and a distinguishing set for $L$ that contains infinitely many strings. We want to show that $L$ is nonregular. To do so, assume for the sake of contradiction that $L$ is regular. This means that there exists a DFA D such that $\mathscr L(D)=L$. Let $k$ be the number of states in $D$. Pick $k+1$ strings from $S$. Since we picked $k+1$ strings and there are $k$ states in the DFA, there must be one state with $2$ strings $s_m$ and $s_n$. Since $S$ is a distinguishing set, $s_m$ and $s_n$ cannot map to the same state of a DFA. We have reached a contradiction, so our earlier assumption must have been false. Therefore, $L$ is nonregular.

$p\to q\equiv\lnot p\vee q$

De Morgan's Laws

$(A\lor B)\leftrightarrow(\lnot A\to B)\leftrightarrow(\lnot B\to A)$