A mathematical model describing how a function parses an input of symbols to halt and obtain a boolean output of accept or reject.
This subject will discuss the following models of computation
A string consisting of symbols that is input to some model of computation. Words are conventionally denoted as \(w\)
A word with no symbols, represented by \( \lambda\) or \( \varepsilon\)
Set of all words accepted by some model of computation \(M\). It is often denoted as \(L\) or \(L(M)\) to denote the language of specific machine \(M\). Note that languages are subsets of the set of all words
\(w \in L(M) \iff M \text{ accepts } w\)
Property of a model of computation such that the computation process has a single predetermined sequence of steps to obtain an output
Nondeterminism refers to the property where there are multiple sequences of computation, and the machine accepts iff there exists some sequence that accepts
A computing model that works based on an input string as instructions where the leftmost symbol determines if and to what state the program changes to, and then this symbol is popped off the string. Then when the string is exhausted (becomes an empty string, AKA \(\lambda\)) the string input is accepted if the program's state is in one of the designated states, otherwise the result is rejected.
DFA are defined by a 5 tuple \( M = ( Q , \Sigma , \delta , q_{0} , F) \) where:
We can represent DFAs as graphs such that \(M=G(Q,E)\) where each edge between states is labelled with \(\sigma\)
Merging two DFAs together logically under some operation using the formal definition, where the new DFA's states are based on ordered pairs (or tuples) of all the amalgamated DFAs
State diagrams often give easy-to-understand visual references for the functionality of a DFA
A spin on the DFA. The DFA is deterministic, meaning that \(\delta\) determines a state for the program to enter as an output. NFAs have the pheonomenon that \(\delta\) offers a set of legal states that can be entered which can be chosen from. A word is accepted so long as there exists at least one path to a \(q \in F\). An NFA will reject a string if it cannot find a path. NFAs let you designate a path for \(\lambda\), which is just passing a string without popping anything off. It is also lenient in that a state doesn't need a path for every element in the alphabet
DFA are defined by a 5 tuple \( M = ( Q , \Sigma , \delta , Q_{0} , F) \) where:
NFAs may allow for multiple initial states. In the case that it doesn't, you can easily emulate the idea of multiple start states by having one state lead into the states that you originally wanted to make the start states
An regular expression that has the exact language of the NFA in question
Theorem asserting some DFA recognizes a language iff an NFA recognises that language
\(\exists \text{DFA} : L(\text{DFA}) = L' \iff \exists \text{NFA} : L(\text{NFA}) = L'\)
Language recognizable by some finite automaton
\(L(M)= A \implies \exists N : L(N) = \overline{A}\)
\(L(M)= A \land L(N)= B \implies \exists V : L(V) = A \cup B\)
\(L(M)= A \land L(N)= B \implies \exists V : L(V) = A \cap B\)
\(L(M)= A \implies \exists N : L(N) = A^{R}\)
Expression used to describe regular languages in a more concise and conventient way than finite automata
Regular expressions are defined with some base constants that can be inductively extended through operations
Where \(R_{1},R_{2}\) are regular expressions and \(L_{1},L_{2}\) are languages:
The idea that going to the gym gives you 'the pump'
Lemma claiming that for any regular language \(L\) and any word of that language \(w \in L\), there is a \(P \in \mathbb{N} : P \geq |Q|\) such that \(\forall w:|w| \geq P\)
So \(w \in L : |w| \geq P\) for regular languages have the structure of having padding \(x,y\) on both sides of the string while in between this padding any amount of \(y\) can be 'pumped' inbetween. If there are \(P\) states then any string larger than \(P\) must visit some state multiple times (might remind you a bit about pidgeon hole principle) and hence loop around \(k\) times until going to the end padding. This lets us pose the conditions that a loop exists (\( |y| \gt 0\)), and the path from the start to the end of the first iteration of the loop is at most size of the amount of states (\( |xy| \leq P \)). If we have a loop, we are able to invoke it as many times as we like, so therefore if the language is regular then \(\forall k \geq 0, xy^{k}z \in L\)
Note that the absolute value poles give the strings length
We say that string \(z\) distinguishes strings \(x\) and \(y\) relative to a language \(L\) when \((xz \in L \land yz \notin L) \lor (yz \in L \land xz \notin L)\) (So concatenating \(z\) onto these strings makes one of the strings in the language and the other not in the language, basically partitioning one string in the language and the other not).
When \(x\) and \(y\) can't find a \(z\) that does this, we call them indistinguishable, and write it such that \(x \equiv_{L} y\). logically this means \(xz \in L \iff yz \in L\) and importantly, is an equivalence relation called an equivalence class
For reflexivity, it means \(xz \in L \iff xz \in L\), which is clearly true. For symmetry, \(yz \in L \iff xz \in L\), which is also clearly true, which is also clearly true. For transitivity, \(x \equiv_{L} y \land y \equiv_{L} z \implies x \equiv_{L} z\). Now looking at the LHS only we can see that no matter what we concatenate onto any \(x,y,z\) it will be in \(L\), so it holds for transitivity and hence equivalence relations
If there are a finite amount of equivalence classes for \(\equiv L\) (), then \(L\) is regular
This is because \(\neg (x \equiv_{L} y)\) means that \(x\) and \(y\) are strings leading to different states, and if you have an infinite pair of different states, you have infinite states, and it's called a finite state machine for a reason right?
Data buffer where data is retrieved by pushing (loading data object on the top of the stack) and popping (removing and returning data object on the top of the stack). This access method is known as LIFO (Last In First Out)
A finite automata that has access to a stack
DFA are defined by a 6 tuple \( M = ( Q , \Sigma , \Gamma , \delta , q_{0} , F) \) where:
To represent the base of the stack, we use \($\)
We can represent PDA as graphs just like DFAs and NFAs such that \(M=G(Q,E)\), where each edge is defined by \(\sigma, \gamma_{\text{pull}} \rightarrow \gamma_{\text{push}}\)
Language recognisable by some PDA
CFGs are a 'grammar' (set of lexical rules) analogous to regular expressions for PDAs in the sense that you can represent any context free language with a CFG like how a regular expression can express any regular language
CFGs are defined by a 4 tuple \( M = ( V , \Sigma , R , S) \) where:
If we have two \(s,t \in (V \cup \Sigma)^{*}\) such that we can use rules to either explicity or implicityly (by one or many rules) using \(u_{n} \in (V \cup \Sigma)^{*}\), we say that s derives t, and in mathematical notation, \(s \implies^{*} t\)
It can be shown that a PDA is logically equivalent to some CFG. To convert from CFG to PDA you can simply use the stack transition as a method to emulate the idea of applying rules
To prove the logical equivalence, we also need to ensure that PDAs imply a CFG (so now the other way around). This can be done by viewing the stack against time in a 'graph-like' manner, so we can intuitively see the following:
This is another method highlighting how the stack mimics the properties of grammar through internal stacks as a way to create rules
The same as a regular PDA, however determinism is employed. This is done by two main rule:
If this weren't the case, non-determinism could occur because if the top stack symbol were \(g\), the program could either take \(\lambda\) path or \(s\) path, and non-determinism is not what we want
DFA are defined by a 6 tuple \( M = ( Q , \Sigma , \Gamma , \delta , q_{0} , F) \) where:
Turns out NPDAs are more powerful than DPDAs
Language that can be read by DPDAs
Deriving a word from a grammar can be thought of as trees steming from \(S\) (the start variable) to derive words using combinations of the avalable rules \(r\in R\). A top-down parser aims to build this tree starting from \(S\) to verify whether the word satisfies the grammar
A specific top-down parser that works by using a rule on the leftmost variable and aims to first resolve the leftmost character of the desired word
In some cases, LL(1) can't resolve a DCFL and so a parsing table should be used to help guide which rules can be used to get which results. To construct such a table, the idea of FIRST and FOLLOW sets must be explored
The FIRST set of a variable or terminal represents the set of all terminals that the variable can initiate with even when rules are applied. In the case of the FIRST set of some terminal, it is simply the terminal itself, since terminals are in fact terminal can can't derive any other string.
The FOLLOW set if a variable represents the set of all terminals that can follow the end of a variable when rules are applied.
After creating these sets for each variable, create a table with a terminals column and variables row. Then in each data cell, place the rule that is responsible for making a terminal in a variable's FIRST set. if the terminal in question is empty string, then focus on the FOLLOW set instead
Regular languages have the characteristic of a large enough string (of more accurately, when \(|w| \gt |Q|\)) being guaranteed to reuse some states. Context-free languages have the characteristic of a large enough string being guaranteed to reuse the same variable
A theoretical machine devised by Alan Turing with the following aspects:
TM are defined by a 7 tuple \( M = ( Q , \Sigma , \Gamma , \delta , q_{start} , q_{accept} , q_{reject} ) \) where:
TMs either halt in an accpet, reject, or neither state, or never halt.
Property of a language such that some Turing machine halts on an accept state only when the word is in the language
\(L \text{ is recognizable } \iff \exists M : (M \text{ halts on } q_{accept} \iff w \in L ) \)
Property of a language such that some Turing machine can partition the language using the \(q_{accept},q_{reject}\), that is, all words in the language halt on an accept state and otherwise halt on a reject state
\(L \text{ is decidable } \iff L \text{ is recognizable } \land \exists M : (M \text{ halts on } q_{reject} \iff w \notin L )\)
A model of computation is Turing complete iff it can perform any algorithm that a Turing machine can. The Lambda calculus is an example of such a model of computation.
An algorithm is computable if and only if a turing machine can compute said algorithm
Whether a turing machine given enough tape and time can compute
An array of units of information
Instructions for data handling. Programs themselves can be represented as data
Since programs can be represented as data to be parsed by other programs, Turing machines can be represented as strings to be parsed by other Turing machines. We denote \(\Lambda = \{ 0,1 \}\) as the alphabet of the Turing machine. We can do this because no matter the cardinality of \( \Lambda\), we can always represent each letter as \( \lceil \log_{2}(|\Lambda|) \rceil\) bits concatenated, in the same way that ASCII works. We need to define this standard of encoding ourselves since there doesn't exist any standard
The idea of a Turing machine \(U\) that can take another Turing machine \(M\) as input along with an input string \(w\) and recognise the same language as \(M\). \(U = \{(M,w) : M \text{ is a Turing machine }\land w \in L(M)\} \)
Set theoretical paradox that arises from applying a partitoning class on a set that by definition partitions some class
Consider a barber that cuts hair for all people that don't cut their own hair. Does the barber cut his own hair? Whether he does or doesn't, both lead to a contradiction
There exist languages that no Turing machine can recognize, simply due to the existance of only \(\aleph_0\) Turing machines, yet \(\aleph_1\) languages
Proving unrecognizability simply requires demonstrating the inability to surjectively map each Turing machine to a language.
Let \(TM\) be the set of all Turing machines and \(L\) be the set of languages, note that by Turing machine encoding, \(TM\) is countable.
Before beginning the proof, a necessary lemma is that a set is never surjective to its powerset. To prove this, by WOC, let \(f : S \to 2^{S}\) be a surjective function mapping a set to its powerset and define \(U = \{s \in S : s \notin f(s)\} \in 2^{S}\). The assumption of surjection implies that \(\exists s \in S : f(s)=U\). Now apply Russel's paradox to finish the proof of the lemma:
\(L\) contains all sets of elements of form \( \{0,1\}*\), a subset of which is \(2^{TM}\). By the previous lemma, \(TM\) has no surjective function to \(2^{TM} \subset L\) and hence there exists languages with no associated Turing machine, completing the proof.
There exist languages that no Turing machine can decide. Since all decidable languages are recognizable, this is a simple corrolary of the existance of unrecognisable languages. Moreover, there are languages that are recognizable but undecidable, a notable example being the \(A_{TM}\) language; the language of all Turing Machine-word pairs that accept
Proving undecidability requires demonstrating a contradictory counterexample by assuming a specific language to be decidable only to reveal paradoxes (this screams Russel's paradox).
By WOC, let \( A_{TM} \) be decidable by \(H(M,w)\). consider \(H'(M)\) that accepts when \(H(M,M)\) rejects and rejects when \(H(M,M)\) accepts. Now apply Russel's paradox to complete the proof:
Therefore because of the assumption of deciding \(A_{TM}\), paradoxes occur and hence \(A_{TM}\) is an undecidable language
By WOC, let \(HALT_{TM}\) be decidable by \(H(M,w)\). Under this assumption, a decider for \(A_{TM}\) \(H'\) can be constructed, but since this language has been proved undecidable this is a contradiction, implying that \(HALT_{TM}\) is not in fact decidable. This is essentially a mapping reduction
By WOC, let \(E_{TM}\) be decidable by \(H(M,w)\). Under this assumption, a decider for \(A_{TM}\) \(H'\) can be constructed, but since this language has been proved undecidable this is a contradiction, implying that \(E_{TM}\) is not in fact decidable. This is essentially a mapping reduction
Let \(H'(M,w)\) create an auxiliary Turing machine \(X(w')\) that rejects if \(w' \neq w\) and otherwise returns the result of \(M(w')\). This auxiliary machine is designed to have a language of either no elements or solely the element \( (M,w) \), proving a useful mapping reduction to translate the notion of 'empty sets' to 'rejection'. Then return \(H(X(M,w))\)
\(A \leq_{m} B \iff \exists f : \Sigma^{*} \to \Sigma^{*}, w \in A \iff f(w) \in B\)
\(A\) reduces to \(B\) when some computable function (perhaps represented as a Turing machine) can only map all words in \(A\) to a word in \(B\). This is used as a method of constructing proofs for the decidability of languages.
Let \(f\) be the mapping reducible function from \(A\) to \(B\) and \(h\) the function from \(B\) to \(C\). Then \(w \in A \iff h(f(w)) \in C\), hence proving the transitive property of mapping reducibility
Let \( (M,w) \) be a pair in \(A_{TM}\). Use Turing machine \(M'(M,w)\) as part of the mapping reducible function that accepts when \(M(w)\) accepts, and otherwise loops infinitely (it must not reject, as rejection is a type of 'halt'). Since \( (M,w) \in A_{TM} \iff (M'(M),w) \in HALT_{TM} \), then \(A_{TM} \leq_{m} HALT_{TM}\)
Let \( (M,w) \) be a pair in \(HALT_{TM}\). Use Turing machine \(M'(M,w)\) as part of the mapping reducible function that accepts when \(M(w)\) halts, and otherwise loops infinitely or rejects. Since \( (M,w) \in HALT_{TM} \iff (M'(M),w) \in A_{TM} \), then \(HALT_{TM} \leq_{m} A_{TM}\)
These two conditions are the corrolaries necessary to conclude that \( A_{TM} \equiv_{m} HALT_{TM} \)
A characteristic function that partitions the set of Turing machines \(TM\) into two sets. Less formally, it categorizes Turing machines into two groups based on whether the Turing machine meets a specific boolean condition
\(P : \{\text{TM}\} \to \{ 0,1 \}\)
We say that \(L_P = \{M : P(M) = 1\} \) be the language of all Turing machines fufiling some property \(P\)
\(P \text{ is trivial } \iff \forall M\in TM, P(M) = 1\)
\(P \text{ is semantic} \iff (L(M_1) = L(M_2) \implies P(M_1) = P(M_2) )\)
\(P \text{ is semantic} \land P \text{ is not trivial } \implies L_{P} = {M \in TM : L(M)=1} \text{ is undecidable}\)
All non-trivial semantic properties \(P\) have an undecidable \(L_P\)
Since \(A_{TM} \leq_{m} L_{P} \implies L_{P} \text{ is undecidable}\) one wants to show generally that \(P \text{ is semantic} \land P \text{ is not trivial } \impliex A_{TM} \leq_{m} L_{P}\)
Proving Rice's theorem requires the use of creating Turing machines within a Turing machine (auxiliary Turing machine). For this proof the goal is to find some way that the auxiliary TM satisfies the property \(P\) iff \(M \text{ accepts } w\). In this vein, let \(X_{M,w}(x)\) be the auxiliary TM which accepts iff \(M \text{ accepts } w \land H \text{accepts} x\) and otherwise loops.
Note that the language of this auxiliary TM is empty if \(M \text{ rejects} w\) and satisfies \(P\) when \(M \text{ accepts } w\))
By WOC, assume \( L_{P} \) is decided by \(H\). And let \(H'(M,w)\) be a Turing machine that does the following:
This \(H'\) serves as the function \(f\) to map language \(A_{TM}\) to \(L_{P}\), and since \(A_{TM}\) is undecidable, so it \(L_{P}\)
\(\delta : Q \times \Gamma\to2^{Q \times \Gamma \times \{L,R\}} \)
Since NTMs may take several paths to attempt to invoke an accept, we define acceptance by a history of 'configurations' \(C_0,C_1,C_2,...\)
They have the same power as normal Turing machines, as you can make a normal Turing machines by enumerating the configuration histories
Analysis on the required resources such as time and memory an algorithm requires
Note that Big-O ignores functional translations and multiplicative constants
For some machine \(M\), it has a time complexity function \(T : n \subseteq \mathbb{N} \to \mathbb{N}\) that takes the maximum amount of steps to execute \(M\) for an input of length \(n\)
For sometime function \(T(n)\), \(\text{TIME}(T(n))\) is a set representing all languages decidable with an algorithm in \(O(T(n))\)
The languages that can be resolved with a time complexity \(O(T(n))\)
\( \text{TIME} (T(n)) = \{ L' : \text{There is a Turing machine with time complexity } O(T(n)) \text{ such that } L'=L(M) \}\)
The languages that can be resolved with a time complexity \(O(T(n))\)
\( \text{NTIME} (T(n)) = \{ L' : \text{There is a Nondeterministic Turing machine with time complexity } O(T(n)) \text{ such that } L'=L(M) \}\)
\( P = \bigcup_{k \in \mathbb{N}} \text{TIME}(n^k)\)
\( NP = \bigcup_{k \in \mathbb{N}} \text{NTIME}(n^k)\)
Thesis stating that efficiently computable problems are in the set of polynomial
\(L \text{ is feasibly computable } \iff L \in P \)
\(L \in NP \iff \exists k \in \mathbb{N},V_{TM}(x,y) \text{ running in polynomial time} : L=\{ x : \exists y \in \Sigma^{*} (|y| \leq |x|^k \land V(x,y) \text{ accepts})\}\)
\(L \in NP \iff \exists k, V_{TM}(x,y) : L=\{ x : \exists y \in \Sigma^{*} (|y| \leq |x|^k \land V(x,y) \text{ accepts})\} \land L(V_{TM}) \in P\)
\(M(w)\) accepts in time \(T(n)\) if and only if there exists a history of configurations that accepts
Language A is poly-time reducible to B if there is a poly-time computable function that puts all elements in B in bijection with all elements in A
\(A \leq_{P} B \iff \exists f : \Sigma^{*} \to \Sigma^{*}: \forall w \in A, f(w) \in B\)
\( L \in NP \land (\forall B \in NP, B \leq_P L) \iff L \in \text{ NP-Complete }\)
SAT is an NP-Complete language
\( (\forall B \in NP, B \leq_P L) \iff L \in \text{ NP-Hard }\)
SAT is NP-Complete (so all NP problems can be polynomial-time reduced to SAT). As a corrolary, \(\text{SAT} \in P \iff P=NP \)
Function \(\varphi : \{0,1\}^n \to \{0,1\} \) defined on boolean sets. The logical operators AND, OR, NOT, XOR, XAND, NAND etc. are examples of boolean functions
Language of all satisfiable boolean formulae
\(\text{SAT} = \{ \varphi : \varphi \text{ is a satisfiable boolean formula } \} \)
It is in NP since verifying a string to be in SAT runs in polynomial time due to the simple nature of boolean functions
It is also NP-Hard since one can devise a boolean formula that is logically equivalent to a TM in NTIME, that is, by passing an accepting configuration into the boolean formula it returns true. Consider some tableau with all the computing histories (this will be of size \(n^{2k}\) cells since there are \(n^k\) histories and any TM that runs in polynomial time can only access \(n^k\) tape cells)
\( \varphi = \varphi_{\text{cell}} \land \varphi_{\text{start}} \land \varphi_{\text{accept}} \land \varphi_{\text{move}} \)
\( \varphi_{\text{cell}} = \bigwedge_{1 \leq i,j \leq n^k} [ (\bigvee_{s \in C} x_{i,j,s}) \land (\bigwedge_{s,t \in C,s\neq t} ( \neg x_{i,j,s} \lor \neg x_{i,j,t} ) ) ] \)
Conjunctive Normal Form; where the AND operator acting on a number of clauses where the amount of literals in the entire CNF-formula is less that or equal to \(n\)
\(\bigwedge_{k=0} c_k\)
The OR operator acting on a number of literals
\(c = \bigvee_{k=0} x_k\)
A boolean variable or negation of a boolean variable
\(x\)
\(\text{3SAT} = \{ \varphi : \varphi \text{ is a satisfiable 3CNF-formula } \} \)
3SAT is also NP-Complete, and by reducing other problems to 3SAT we can prove other problems to be NP-Complete too; in a similar way how we can show how languages reducing to \(A_{TM}\) are decidable. You can, for instance, use 3SAT reductions to a logically equivalent graph to prove that the Hamiltonian path problem's language is NP-Complete
A system of proving that some algorithm is true without disclosing the algorithm itself
A valid lambda calculus program, \(\Lambda\) represents the set of all expressions.
An element that represents a number liable to change. There are two types:
\(x\)
An element passing a variable \(x\) to a lambda expression \(M\), the scope of \(x\) is within \(M\)
\(\lambda x.M\)
An element passing one lambda expression to another
\( (M N) \)
Using this knowledge, \(\Lambda\) can be defined as a grammar such that an expression is a sequence of 'abstractions' and 'applications' of variables
The notion that bound variable names can be changed so long as it is within scope and no clashes occur
\( \lambda x.M[x] \equiv_{\alpha} \lambda y.M[y] \)
The notion that an expression can be applied to another expression as substitution into the bound variable
\( (\lambda x.M[x])y \equiv_{\beta} M[x := y] \)
The notion that an abstraction that applies its input to some internal expression is logically equivalent to that internal expression itself
\( \lambda x.(M[y] x) \equiv_{\eta} M[y := x] \)
Multi parameter function syntax by nesting functions inside eachother
\(\lambda x.\lambda y.xy\)
\(\bar{n}=\lambda s.\lambda z.s^{n}(z) \) where:
\(S = \lambda s.\lambda z.(s(ns(z)) \implies S\overline{n} = \overline{n+1}\)
A symbolic element
An element representing the medium through which a message travels
\(c\)
An element whose value may be transmitted and received on a channel
\(x\)
Construct that permits two processes running simultneously (concurrently)
\(P|Q\)
Construct that awaits a message on some channel, this message is then binded to some name
\(c(x)\)
Construct that transmits a message on some channel, this message is then received by a concurrent process
\(\overline{c}\langle y \rangle\)
Construct that can create new instances of a defined process
\(!P\)
\((\nu x)\)
Construct that terminates a process
\(0\)