\documentclass[12pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[margin=2.5cm]{geometry}
\usepackage{float}

\usepackage{subcaption}
\usepackage{graphicx}
\usepackage{amsmath}

\usepackage{hyperref}
\graphicspath{ {images/} }
\renewcommand{\figurename}{Slika}

\title{IRZ definicije}
\author{Čipson}
\date{\today}

\begin{document}
\maketitle
\tableofcontents
\newpage
\section{Preliminaries}

A \emph{model of computation} is a formal definition of
the basic notions of algorithmic computation. It rigorously defines
\begin{itemize}
    \itemsep0em
    \item what is meant by the notion of the algorithm,
    \item what is the environment required to execute the algorithm,
    \item how the algorithm executes in this environment. 
\end{itemize}

\section{Finite Automata and Regular Expressions}

A \emph{deterministic finite automaton} (DFA)
is a 5-tuple ($Q$,$\sum$,$\delta$,$q_0$,$F$) where:
\begin{itemize}
    \itemsep0em
    \item $Q$ is a finite set of states,
    \item $\sum$ is a finite input alphabet,
    \item $q_0 \in Q$ is the initial state,
    \item $F \subseteq Q$ is the set of final states, and
    \item $\delta$ is the transition function, i.e. $\delta: Q\times \Sigma \rightarrow Q$.
\end{itemize}
That is, $\delta(q,a)$ is a state (for each state q and input symbol a).\\
Note: $\delta$ is the program of DFA. Every DFA has its own, specific $\delta$. 
\\\\
\noindent A string x is said to be \emph{accepted by a DFA} $M = (Q,\sum,\delta,q_0,F)$
if $\delta(q_0 ,x) = p$ for some $p \in F$.
\\\\
\noindent The \emph{language accepted by a DFA} M is defined as the set 
$L(M) = {x \in \sum^* | \delta(q_0,x) \in F}$
\\\\
\noindent A language L' is said to be a \emph{regular set} (or just regular) if L' is accepted by
some DFA (if L' is accepted by some DFA (i.e. if $\exists$ DFA M : L' = L(M))).
\\\\
\subsection{Nondeterminism}
Question: Given an input word $a_1a_2\dots a_n$, who decides whether or not
there exists a sequence of transitions leading from initial to some final state?\\
Answer: NFA itself!
\\\\
Question: How does NFA do that?\\
Answer: The NFA is not a realistic model of computation: it is assumed that
NFA can always guess right. That is, it is assumed that NFA has the magic
capability of choosing, from any given set of options, the right option, i.e. the
option that leads to a success (if such an option exists; otherwise, NFA halts).
\\ 
{\footnotesize In particular, if there are several transitions from a state on the same input symbol, the NFA
can immediately choose the one (if there is such) which eventually leads to some final state.}
\\\\
Question: If NFA is unrealistic, who needs it?\\
Answers:
\begin{itemize}
    \item NFA (and other nondeterministic models that we will see later) can be used to find
    lower bounds on the time required to solve computational problems. The reasoning
    is as follows: If a problem P requires time T to be solved by a nondeterministic
    model M, then solving this problem on any deterministic version D of the model M
    must require at least time T (because D lacks the ability of prediction).
    \item Often it is much easier to design a NFA (or some other nondeterministic model) for a
    given problem P. We then try to construct an equivalent deterministic version
    (equivalent in the sense that it solves P too, regardless of the time needed).
\end{itemize}

\subsubsection{Nondeterministic finite automaton}
\noindent A \emph{nondeterministic finite automaton} (NFA) is a 5-tuple $(Q,\sum,\delta,q_0,F)$ where:
\begin{itemize}
    \itemsep0em
    \item $Q$ is a finite set of states,
    \item $\sum$ is a finite input alphabet,
    \item $q_0 \in Q$ is the initial state,
    \item $F \subseteq Q$ is the set of final states and
    \item $\delta$ is the transition function, i.e. $\delta:Q\times\sum\rightarrow2^Q$\\
    That is, $\delta(q,a)$ is the set of all states p, such that there is a transition labeled
    a from q to p.
\end{itemize}
\noindent {\footnotesize Note: $\delta$ is the program of NFA. Every NFA has its own specific $\delta$.}
\\\\
A string x is said to be \emph{accepted by a NFA} $M = (Q,\sum,\delta,q_0,F)$ if $\delta(q_0,x)$
contains some $p \in F$ (i.e.,$\delta(q_0,x)\cap F \neq \emptyset$).
\\\\
The \emph{language accepted by a NFA} $M = (Q,\sum,\delta,q_0,F)$ is the set\\
$L(M) = \{x\in\sum^* \mid \delta(q_0,x)$ contains a state in $F\}$
\\\\
Every DFA is also NFA.
\\\\
Let L be a set accepted by a NFA M. Then there exists a DFA M' that accepts L.
\\\\
\subsubsection{Nondeterministic finite automaton with $\varepsilon$ moves}
A \emph{NFA with $\varepsilon$-moves} ($NFA_\varepsilon$) is a 5-tuple $(Q,\sum,\delta,q_0,F)$ where:
\begin{itemize}
    \itemsep0em
    \item $Q$ is a finite set of states,
    \item $\sum$ is a finite input alphabet,
    \item $q_0 \in Q$ is the initial state,
    \item $F \subseteq Q$ is the set of final states and
    \item $\delta$ is the transition function, i.e. $\delta:Q\times(\sum\cup\{\varepsilon\})\rightarrow2^Q$\\
    That is, $\delta(q,a)$ is the set of all states p, such that there is a transition labeled
    a from q to p, where a is either a sybol in $\sum$ or $\varepsilon$.
\end{itemize}
A string x is said to be \emph{accepted by a $NFA_\varepsilon$} $M = (Q,\sum,\delta,q_0,F)$ if
the set \\
$L(M) = \{x\in\sum^*\mid\hat{\delta}(q_0,x)$ contains a state in $F\}$
\\\\
Let L be a set accepted by a NFA$_\varepsilon$ M. Then there exists a DFA M' that accepts L.
\\\\
The set of all states reachable from the state $q$ with $\varepsilon$-transitions only: $\varepsilon$-Closure($q$).
\\\\
Let $\sum$ be an alphabet. Let $L_1$ and $L_2$ be sets of words from $\sum^*$. The
concatenation of $L_1$ and $L_2$, denoted $L_1L_2$, is the set\\
$L_1L_2$ = \{$xy \mid x \in L_1$ and y $\in L_2$\}
{\footnotesize Words in $L_1L_2$ are formed by taking an x in $L_1$ and following it by a y in $L_2$,
for all possible x, y.}
\\\\
Let $L\subseteq \sum^*$. Define $L^0$ = \{$\varepsilon$\} and $L^i = LL^{i-1}$ for $i\geq1$.
The \emph{Kleene closure} (in short closure) of $L$, denoted $L^*$, is the set
    \[L^* = \bigcup_{i=0}^{\infty}L^i\]
and the \emph{positive closure} of $L$, denoted $L^+$, is the set
\[L^+ = \bigcup_{i=1}^{\infty}L^i\]

\noindent {\footnotesize $L^*$ is the set of words that are constructed by concatenating \emph{any number} of words from $L$.}\\
{\footnotesize $L^+$ is the same, but the case of \emph{zero} words (whose concatenation is defined to be $\varepsilon$),
is excluded.\\
\emph{Note:} $L^+$ contains $\varepsilon$ \emph{iff} $L$ contains $\varepsilon$.}
\\\\
\subsubsection{Regular expressions}
Let $\sum$ be alphabet. The \emph{regular expressions} (r.e.) over $\sum$ (and the sets that
they denote) are defined inductively as follows:
\begin{enumerate}
    \itemsep0em
    \item $\emptyset$ is a r.e.; it denotes the \emph{empty set}, $\emptyset$;
    \item $\varepsilon$ is a r.r.; it denotes the set \{$\varepsilon$\};
    \item For each $a\in\sum$, a is a r.e.; it denotes the set \{a\};
    \item If $r$ and $s$ are r.e.s denoting languages $R$ and $S$, respectively, then
    \begin{itemize}
        \itemsep0em
        \item $(r + s)$ is a r.e.; it denotes the set $R \cup S$; \small (union of $R$ and $S$)
        \item $(rs)$ is a r.e.; it denotes the set $RS$; \small (concatenation of $R$ and $S$)
        \item $(r^*)$ is a r.e.; it denotes the set $R^*$. (Kleene closure of $R$)
    \end{itemize}
\end{enumerate}
{\footnotesize Note. The basic r.e.s are defined explicitly (1,2,3). All the other r.e.s are defined
inductively (4a,b,c). Definitions of this kind are called inductive. Properties of
the defined objects are often proved by induction.}
\\\\
Conventions
\begin{enumerate}
    \item We can omit many parentheses
    \begin{itemize}
        \itemsep0em
        \item if we assume that * has higher precedence than concatenation and concatenation
        has higher precedence than +.
        \item if we abbreviate the expression $rr^*$ by $r^+$.
    \end{itemize}
    \item When
    \begin{itemize}
        \itemsep0em
        \item necessary to distinguish between a regular expression r and the language denoted by
        r, we use $L(r)$ for the latter;
        \item no confusion is possible we use r for both the regular expression
        and the language denoted by the regular expression.
    \end{itemize}
\end{enumerate}

\noindent Let r be an arbitrary r.e. Then there exists an NFA$_\varepsilon$ that accepts $L(r)$.\\
\emph{Proof idea: } We use induction on the number of operators in r to show that, for any
r.e. $r$, there exists an NFA$_\varepsilon$ $M = (Q,\sum,\delta,q_0,\{f_0\})$ with one final
state and no transitions out of it, such that $L(M) = L(r)$.\\
{\footnotesize Note: NFA$_\varepsilon$s with just one final state will enable us to easily
combine them into larger NFA$_\varepsilon$s. No generality will be lost in this way. (Why?
 Show how an arbitrary general NFA can be transformed into such equivalent NFA$_\varepsilon$.)}
\\\\
Let $M$ be an arbitrary DFA. There exists a r.e. that denotes $L(M)$.\\
\emph{Proof idea: }
\begin{itemize}
    \itemsep0em
    \item We view $L(M)$ as a union of finitely many sets.
    \item Each of the sets corresponds to a final state of $M$ and contains exactly the words
    that take $M$ from its initial state to this final state.
    \item We then define these sets inductively (bottom up, by simpler sets).
    Simultaneously we construct to each such set the corresponding r.e. 
\end{itemize}

\section{Properties of regular sets}
\subsection{Pumping lemma}
Let $L$ be a regular set. Then there
is a constant n (that only depends on L) such that the following holds:\\
if z is any word such that
\begin{itemize}
    \item[] $z \in L$ and $|z| \geq n$ {\scriptsize (obstaja beseda z, ki je daljša od n)}
\end{itemize}
then there exist words $u,v,w$ such that
\begin{itemize}
    \itemsep0em
    \item[] $z = uvw$, {\scriptsize (sestavljena iz u,v,w)}
    \item[] $|uv| \leq n$,
    \item[] $|v| \geq 1$, {\scriptsize (sredinja beseda dolga vsaj 1)}
    \item[] $\forall i \geq 0: uv^iw \in L$. {\scriptsize (to besedo lahko poljubno ponavljamo)}
\end{itemize}
{\footnotesize In addition, n is at most the number of states of the smallest FA accepting L.}
\\\\
\emph{Informally: }\\
Given any sufficiently long word z accepted by an FA, we can find a subword v (near the beginning of z)
that may be repeated ("pumped”) as many times as we like but the resulting word will still be accepted by the FA.
\\\\
\emph{Applications - from p.101}\\
Proving some languages are not regular\\
$(\exists z)(\forall u,v,w)(\exists i \geq 0)uv^iw \notin L \Rightarrow L$ not regular\\
{\footnotesize (for 'good' n,z,u,v,w)}\\
: If we prove, for a given L, that the left-hand side of ‘$\Rightarrow$’ holds, then L is not regular.\\
There exist non-regular languages! For these we will need a model of
computation that is more powerful than FA. 

\subsection{Closure under union, concatenation, and Kleene closure}

The class of regular sets is closed under union, concatenation, and Kleene closure.\\
{\scriptsize \emph{Remark: }So the union $L_1 \cup L_2$ and concatenation $L_1L_2$ 
of regular sets  $L_1$, $L_2$ is a regular set, and the Kleene closure $L^*$ of a regular 
set $L$ is a regular set.}

\subsection{Closure under complementation and intersection}
The class of regular sets is closed under complementation and intersection.\\
{\scriptsize \emph{Remark: }The theorem states that the complement $\sum^* - L$ of a 
regular set $L$ is a regular set, and the intersection $L_1 \cap L_2$ of regular sets 
$L_1$, $L_2$ is a regular set.}

\subsection{Closure under substitution and homomorphism}
Let $\Sigma, \Delta$ be alphabets. A \emph{substitution} is a function $f$ that maps each symbol
of $\Sigma$ to a language over $\Delta$; i.e. $f(a)\subseteq \Delta^*$ for each a $\in \Sigma$.
We extend $f$ to words in $\Sigma^*$ by defining $f(\varepsilon)=\varepsilon$ and $f(wa)=f(w)f(a)$;
and then to languages by defining $$f(L) = \bigcup_{x \in L}f(x)$$
The definition of substitution says nothing about the kind of the set $L$ and the sets $f(a)$,
$a\in \Sigma$. What if we additionally require that $L$ and all $f(a)$, $a\in \Sigma$ are
regular? Is then $f(L)$ regular too?
\\\\
A homomorphism is a substitution $h$ such that $h(a)$ contains a \emph{single word} for each
$a\in \Sigma$. We extend $h$ to words and languages as in the case of substitution. The 
\emph{inverse homomorphic image} of a word $w$ is the set $h^{-1}(w)=\{x\mid h(x)=w\}$ and of
a language $L$ is the set $h^{-1}(L)=\{x\mid h(x) \in L\}$.
\\\\
The class of regular sets is closed under substitution, homomorphism and inverse homomorphism.\\
\emph{Proof idea:}
\begin{itemize}
    \item (\emph{substitution}) Let $L$ and all $f(a)$, $a\in \Sigma$ be regular sets. Let $L$
    be denoted by r.e. $r$ and $f(a)$ by $r_a$.\\
    \emph{Idea: }replace each occurence of $a$ by $r$ by $r_a$. Then prove that the resulting
    r.e. $r'$ denotes $f(L)$.\\
    ({\scriptsize Use induction on the number of operators in $r'$.})
    \item (\emph{homomorphism}) Closure under homomorphism follows directly from closure under substitution\\
    ({\scriptsize because every homomorphism is by definition a (special) substitution})
    \item (\emph{inverse homomorphism}) Let $L$ be regular and $h$ a homomorphism. We want to prove that 
    $h^{-1}(L)$ is regular. Let $M$ be DFA accepting $L$. We want to construct a DFA $M'$ such that
    $M'$ accepts $h^{-1}(L)$ \emph{iff} M accepts $L$.\\
    \emph{Idea: }construct $M'$ so that when $M'$ reads $a\in \Delta$, it simulates $M$ on $h^{-1}(L)$.
\end{itemize}
\subsection{Closure under quotient}
The \emph{quotient} of languages $L_1$ and $L_2$ is the set $L_1/L_2$ defined by\\
$L_1/L_2 = \{x\mid \exists y \in L_2:xy \in L_1\}$.\\
{\footnotesize\emph{Informally: }$L_1/L_2$ contains prefixes of words in $L_1$ whose corresponding suffixes
are words in $L_2$.}\\
The class of regular sets is closed under quotient with arbitrary sets.

\section{Decision algorithms for regular sets}
\subsection{Emptiness and finiteness of regular sets.}
The set $L(M)$ accepted by a FA $M$ with $n$ states is:
\begin{enumerate}
    \itemsep0em
    \item \emph{nonempty iff} $M$ accepts a word of length $l$, where $l < n$.
    \item \emph{infinite iff} $M$ accpets a word of length $l$, where $n \leq l < 2n$
\end{enumerate}
Naive algorithms for both could systematically generate all words of appropriate lengths $l$ and,
for each generated word, check whether $M$ accepts that word.\\
\emph{Both algorithms eventually halt and return a YES or NO.}

\subsection{Equivalence of finite automata.}
Two finite automata $M_1$ and $M_2$ are said to be equivalent if they accept the same language, 
i.e. if $L(M_1) = L(M_2)$.\\
There exists an algorithm to decide whether two FAs are \emph{equivalent}.\\
\emph{Proff: }\\
Let $M_1$ and $M_2$ be FAs and $L_1 = L(M_1)$ and $L_2 = L(M_2)$. Define a language $L_3$ as follows:\\
$$L_3 = (L_1 \cap \overline{L_2})\cup (\overline{L_1} \cap L_2)$$
$L_3$ is regular (due to closure properties) and therefore accepted by some FA $M_3$. This
$M_3$ is important because we can show that\\
\centerline{$M_3$ accepts a word \emph{iff} $L_1 \neq L_2$.}\\
So we need to check whether $M_3$ accepts any word, i.e. whether $L_3$ is non-empty.

\section{The Myhill-Nerode theorem and minimization of FA}
Let $L \subseteq \Sigma^*$ be an arbitrary language. Define a relation $R_L$ on $\Sigma^*$ by\\
\centerline{$xR_Ly$ iff $\forall z \in \Sigma^*:xz \in L \Leftrightarrow yz \in L$.}
{\footnotesize \emph{Remarks:} Two words $x,y \in \Sigma^*$ are in relation $R_L$ \emph{iff}
their arbitrary extensions xz,yz are either both in $L$ or both outside $L$. Now, $R_L$ is an
\emph{equivalence relation}. So, $R_L$ partitions $L$ into \emph{equivalence classes}. The
number of these is called the index of $R_L$ and it can be finite or infinite.}
\\\\
Let $M=(Q,\Sigma,\delta,q_0,F)$ be a DFA. Define a relation $R_M$ on $\Sigma^*$ by\\
\centerline{$xR_My$ \emph{iff} $\delta(q_0,x) = \delta(q_0,y)$.}
{\footnotesize \emph{Remarks:} Two words $x,y\in\Sigma^*$ are in relation $R_M$ \emph{iff}
they take $M$ from $q_0$ to the same state q. $R_M$ is \emph{equivalence relation}. It partitions
$\Sigma^*$ into \emph{equivalence classes, one for each state q reachable from $q_0$}. The
number of the classes is the \emph{index of $R_M$}. The index of $R_M$ is finite (since $Q$
is finite). $L(M)$ is the union of some equivalence classes (that correspond to final states
$q\in F$).} 
\\\\
We can prove that $R_M$ is right invariant, i.e. that\\
$$xR_My \Rightarrow \forall z\in\Sigma^*:xzR_Myz$$
\\\\
(Myhill-Nerode) The following statements are \emph{equivalent}:
\begin{enumerate}
    \itemsep0em
    \item $L\subseteq \sigma^*$ is a regular set;
    \item $R_L$ is of finite index;
    \item $L$ is the union of some of the equivalence classes of a right invariant equivalence
    relation of finite index.
\end{enumerate}
{\footnotesize \emph{Remarks:} The theorem is useful when, for a given $L$, we have proved
one of the items (1,2,3). Then by Myhill-Nerode theorem, the other two items hold too, and so
reveal additional information about $L$.}
\\\\
A consequence of the Myhill-Nerode Theorem is that for every regular set there is an 
essentially unique \emph{minimum state} DFA.
\\\\
The minimum state DFA accepting a regular set $L$ is \emph{unique up to an isomorphism}
(renaming of the states).
\\\\
Proof idea:
\begin{itemize}
    \item Let $L$ be regular. By Myhill-Nerode theorem there are finitely many equivalence
    classes of $R_L$. Denote by [$x$] the eq. class containing $x\in \Sigma^*$. So
    $\{[x]\mid x\in \Sigma^*\}$ is the set of all eq. classes of $R_L$.
    \item Construct a DFA $M = (Q,\Sigma,\delta,q_0,F)$ as follows:
        \begin{itemize}
            \item[] $Q := \{[x]\mid x\in \Sigma^*\};$ {\footnotesize (each state will
            correspond to an eq. class of $R_L$)}
            \item[] $\delta([x],a):=[xa]$, for $a\in\Sigma$
            \item[] $q_0 := [\varepsilon]$
            \item[] $F := \{[x]\mid x\in L\}$
        \end{itemize}
    \item \emph{Note:} $\delta(q_0,w)=\delta(q_0,a_1a_2\dots a_n)=[a_1a_2\dots a_n]=[w]$.\\
    Thus, $M$ accepts $w$ \emph{iff} $[w]\in F$. This means that $M$ accepts $L$.
    \item It follows from the proof of Myhill-Nerode theorem that this $M$ is the minimum
    state DFA for $L$.
\end{itemize}

\section{Context-Free grammars and languages}
A \emph{context-free grammar} (CFG) is a 4-tuple $G = (V,T,P,S)$ where:
\begin{itemize}
    \itemsep0em
    \item $V$ is a finite set of variables
    \item $T$ is a finite set of terminals
    \item $P$ is a finite set of productions, each of which is of the form $A \Rightarrow \alpha$,
    where $A\in V$ and $\alpha$ is a word in the language $(V\cup T)^*$;
    \item $S$ is a special variable called the \emph{start symbol}.
\end{itemize}
Let $A \rightarrow \beta$ be a production and $\alpha, \gamma \in (V \cup T)^*$ arbitrary string.
\begin{itemize}
    \itemsep0em
    \item We say that we apply the production $A \rightarrow \beta$ to $\alpha A \gamma$ and
    obtain $\alpha \beta \gamma$ if we substitute $A$ by $\beta$ in $\alpha A \gamma$. In this
    case we say that $\alpha A \gamma$ directly derives $\alpha \beta \gamma$ by the production
    $A \rightarrow \beta$.
    \item We say that two strings are in the relation $_G\Rightarrow$ if the $1^{st}$ directly
    derives the $2^{nd}$ one by one application of a production in $G$.
    \item Let $\alpha_1,\alpha_2,\dots,\alpha_m \in (V\cup T)^*, m\geq 1$, be strings.\\
    If $\alpha_1$ $_G\Rightarrow \alpha_2 \wedge \alpha_2$ $_G\Rightarrow \alpha_3 \wedge \dots \wedge
    \alpha_{m-1}$ $_G\Rightarrow^*\alpha_m$\\
    then we say that $\alpha_1$ derives $\alpha_m$ in $G$ and denote this fact by $\alpha_1$ $_G\Rightarrow^*\alpha_m$.\\
    {\footnotesize \emph{Note:} The relation $_G\Rightarrow^*$ is reflexive and transitive
    closure on the relation $_G\Rightarrow$.}
\end{itemize}
The \emph{language generated} by a CFG $G=(V,T,P,S)$ is the set\\
\centerline{$L(G)=\{w\mid w\in T^* \wedge S$ $_G\Rightarrow^*w\}$.}
{\footnotesize So the language generated by $G$ is the set of all terminal strings that can
be derived from $S$.}
\\\\
A language $L$ is called \emph{context-free} (CFL) if $L=L(G)$ form some CFG $G$.
\\\\
A string $\alpha \in (V\cup T)^*$ is called a \emph{sentential form} if $S$ $_G\Rightarrow^*\alpha$.
\\\\
Two grammars $G_1$ and $G_2$ are said to be \emph{equivalent} if $L(G_1) = L(G_2)$.
\subsection{Derivation trees}
Let $G=(V,T,P,S)$ be a CFG. A tree is called a \emph{derivation} (or parse) tree for $G$ if:
\begin{enumerate}
    \itemsep0em
    \item Every vertex \textbf{v} has a label that is a symbol in $V\cup T \cup \{\varepsilon\}$.
    \item The label of the \emph{root} is $S$.
    \item If a vertex \textbf{v} is \emph{interior} and has label $A$, then $A$ must be in $V$.
    \item If a vertex \textbf{v} has label $A$  and vertices \textbf{$v_1$},\textbf{$v_2$},$\dots$
    ,\textbf{$v_k$} are the \emph{sons} of v (from left to right) with labels $X_1,X_2,\dots,X_k$,
    respectively, then $A\rightarrow X_1X_2\dots X_k$ must be a \emph{production} in $P$.
    \item If vertex \textbf{v} has label $\varepsilon$, then \textbf{v} is a \emph{leaf} and
    is the only son of its father.
\end{enumerate}
If we read the labels of all \emph{leaves} visited by the \emph{preorder traversal} of the tree
we obtain a string that is called the \emph{yield} of the \emph{derivation tree}.
\\\\
A \emph{subtree} of a derivation tree is a particular vertex of the tree together with all of
its descendants, edges among them, and their labels. If the root of a subtree is labeled $A$,
then the subtree is called $A$-tree.\\
{\footnotesize A subtree is just like a derivation tree, but the label of its root may not
be the start symbol $S$ of the grammar.}
\subsubsection{The relationship between derivation trees and derivations}
Let $G=(V,T,P,S)$ be a CFG. Them $S$ $_G\Rightarrow^*\alpha$ \emph{iff} there is a derivation 
tree for $G$ with yield $\alpha$.\\
{\footnotesize \emph{Proof idea:} Induction on the number of interior vertices of the tree.}

\subsubsection{Leftmost and righmost derivations}
A derivation is said to be \emph{leftmost} if at \emph{each step} of the derivation
a production is applied to the \emph{leftmost variable}. Similarly, a derivation is
\emph{rightmost} if at \emph{each step} a production is applied to the \emph{rightmost} variable. 

\subsubsection{Ambiguity}
A CFG $G$ is said to be \emph{ambiguous} if some word has more than one derivation tree.\\
{\footnotesize \emph{Equivalently:} A CFG is ambiguous if some word has more than one
leftmost (rightmost) derivation.}
\\\\
A CFL $L$ is \emph{inherently ambiguous} if every CFG for $L$ is ambiguous.

\subsection{Simplification of context-free grammars}
There are several ways to \emph{restrict the form of productions without
reducing the power} of CFGs. If $L$ is a nonempty CFL then $L$ can be
generated by a CFG $G$ having the following properties: 
\begin{itemize}
    \item Each variable and terminal of $G$ appears in the derivation of some word in $L$. 
    \item There are no productions of the form $A\rightarrow \varepsilon$.
    \item If $\varepsilon \notin L$, there are no productions of the form $A \rightarrow \varepsilon$.
    \item If $\varepsilon \notin L$, we can require that
        \begin{itemize}
            \item[] every production is of the form $A\rightarrow BC$ or $A\rightarrow b$\\
            {\footnotesize (Chomsky normal form) where $A,B,C$ are variables and $b$ is a terminal}
            \item[] or, every production is of the form $A\rightarrow b \gamma$\\
            {\footnotesize (Greibach normal form) where $b\in T$ and $\gamma \in V^*$  (a string of variables).} 
        \end{itemize}
\end{itemize}

\subsubsection{Elimination of useless symbols}
Let $G=(V,T,P,S)$ be a grammar. A symbol $X$ is useful if there exists a derivation
$S\Rightarrow^*\alpha X \beta \Rightarrow^*w$ for some $\alpha,\beta,$ and $w \in T^*$.
Otherwise $X$ is useless.\\
Lemmas:
\begin{itemize}
    \item Given a CFG $G=(V,T,P,S)$ with $L(G) \neq \emptyset$, we can effectively find 
        an equivalent CFG $G'=(V',T,P',S)$ such that for each $A \in V'$ there is a
        $w\in T^*$ so that $A\Rightarrow^*w$
    \item Given a CFG $G'=(V',T,P',S)$, we can effectively find an equivalent CFG
        $G''=(V'',T,P'',S)$ such that for each $X\in V''\cup T$ there are 
        $\alpha,\beta \in (V''\cup T)^*$ so that $A\Rightarrow^*\alpha X \beta$.
\end{itemize}
Applying the lemmas \emph{in this order}, we can convert a CFG G to the equivalent G''
\emph{without useless symbols}. (Applying the lemmas in the reverse order may fail to
eliminate all useless symbols.)
\\\\
Every nonempty CFL is generated by a CFG with no useless symbols.

\subsubsection{Elimination of $\varepsilon$-productions}
An $\varepsilon$-production is a production of the form $A \rightarrow \varepsilon$.\\
{\footnotesize Clearly, if $\varepsilon$ is in $L(G)$, we cannot eliminate all 
$\varepsilon$-productions from $G$. (Otherwise, $\varepsilon$ would no longer be in
the generated language.) But if $\varepsilon$ is not in $L(G)$, we can eliminate all 
$\varepsilon$-productions from $G$.}
\\\\
If $L=L(G)$ for some CFG $G=(V,T,P,S)$, then $L-\{\varepsilon\}$ can be generated by a
CFG $G'$ that has no useless symbols and no $\varepsilon$-productions.\\
{\footnotesize \emph{Proof idea:}
\begin{itemize}
    \itemsep0em
    \item Determine for each $A\in V$ whether $A\Rightarrow^* \varepsilon$. If so, call
    $A$ nullable.
    \item Then replace each production $B\rightarrow X_1X_2\dots X_n$ by all productions
    formed by striking out some subset of those $X_i$'s that are nullable, but do not
    include $B\rightarrow \varepsilon$, even if all $X_i$'s are nullable.
\end{itemize}}

\subsubsection{Elimination of unit productions}
A unit production is a production of the form $A\rightarrow B$.\\
{\footnotesize The right-hand side must be a single variable; all other productions,
including $A \rightarrow a$ and $\varepsilon$-production, are non-unit.}
\\\\
Every CFL without $\varepsilon$ can be generated by a grammar
that has no useless symbols, no $\varepsilon$-productions, and no unit productions. 

\subsubsection{Chomsky normal form}
Every CFL without $\varepsilon$ can be generated by a grammar in which every
production is of the form\\
\centerline{$A\rightarrow BC$ or $A\rightarrow a$}\\
where $A,B,C$ are variables and $a$ is a terminal.\\
{\footnotesize\emph{TLDR "proof" p.142:}
\begin{itemize}
    \item [] The input CFG should be without useless variables, unit productions 
        and $\varepsilon$-productions
    \item[] Replace all terminals in productions so they only appear this form: 
        $A \rightarrow a$ (one variable $\rightarrow$ one terminal)
    \item[] Break up all productions that include more than 2 ($\geq 3$) variables into 2 parts.
        (the maximum amount of variables in a production is 2: $A\rightarrow BC$)
\end{itemize}}

\subsubsection{Greibach normal form}
Every CFL without $\varepsilon$ can be generated by a grammar in which every production is
of the form.
$$A\rightarrow b\gamma$$
where $A$ is a variable, $b$ is a terminal, and $\gamma$ is a (possibly empty) string of
variables ($\gamma \in V^*$).
{\footnotesize\emph{"proof" p.144}}
\subsubsection{Inherently ambiguous context-free languages}
The CFL $L = \{a^nb^nc^md^m \mid n,n \geq 1\} \bigcup \{a^nb^mc^md^n \mid n,m \geq 1\}$
is inherently ambiguous.

\section{Pushdown automata}
A \emph{pushdown automaton} (PDA) is a 7-tuple $M=(Q,\Sigma, \Gamma, \delta, q_0, Z_0,F)$,
where
\begin{itemize}
    \itemsep0em
    \item $Q$ is a finite set of states,
    \item $\Sigma$ is the input alphabet,
    \item $\Gamma$ is the stack alphabet,
    \item $q_0 \in Q$ is the initial state,
    \item $Z_0 \in \Gamma$ is the start symbol,
    \item $F \subseteq Q$ is the set of final states and 
    \item $\delta$ is the transition function,\\
        {\footnotesize i.e. a mapping from $Q \times (\Sigma \cup \{\varepsilon\})\times\Gamma$
        to finite subsets of $Q \times \Gamma^*$.}
\end{itemize}
{\footnotesize \emph{Note:} $\delta$ can be viewed as a program of PDA. Every PDA has its
own specific $\delta$.}

\subsection{Moves of the PDA}
The interpretation of the move
\begin{itemize}
    \item $\delta(q,a,Z)=\{(p_1,\gamma_1),(p_2,\gamma_2),\dots,(p_m,\gamma_m)\}$
        is that the PDA in state $q$, with input symbol $a$ and $Z$ the top symbol
        on the stack can, for any $i$, $1 \leq i \leq m$, enter state $p_i$,
        replace symbol $Z$ by string $\gamma_i$, and advance the window one symbol.
        We call this the \emph{regular move}.
    \item $\delta(q,\varepsilon,Z)=\{(p_1,\gamma_1),(p_2,\gamma_2),\dots,(p_m,\gamma_m)\}$
        is that the PDA in state $q$, independently of the input symbol being scanned and
        with $Z$ the top symbol on the stack, can enter state $p_i$, and replace 
        $Z$ by $\gamma_i$, for any $i$, $i \leq i\leq m$. In this case, the window is not
        advanced. We call this the $\varepsilon$-move.
\end{itemize}
{\footnotesize \emph{Conventions:} the leftmost symbol of $\gamma_i$ is placed highest on
the stack and the rightmost symbol of $\gamma_i$ lowest on the stack. We use $a,v,c,\dots$
for input symbols, $u,v,w,\dots$ for strings of input sybols, captal letters for stack
symbols, and Greek letters for string of stack symbols.}

\subsection{Instantaneous descriptions of the PDA}
An instantaneous description (ID) is a tripple $(q,w,\gamma)$, where $q$
is a state, $w$ a string of input symbols to be read, and $\gamma$ a string of stack symbols.
\begin{itemize}
    \item If $M=(Q,\Sigma, \Gamma, \delta, q_0, Z_0,F)$ is a PDA, we say that ID $(q,ax,Z\beta)$
        can directly become $ID(p_i,ax,\gamma_i\beta)$, --- written\\
        \centerline{$(q,ax,Z\beta)$ $\vdash (p_i, x, \gamma_i\beta)$,}
        if $\delta(q,a,Z)$ contains $(p_i,\gamma_i)$. Here, a may be an input symbol or $\varepsilon$.
    \item We write $_M\vdash^*$ for the reflexive and transitive closure of $_M\vdash$ and
        say that an ID $I$ can become ID $J$ if $I _M\vdash^* J$. We write 
        $I _M\vdash^k J$ if $I _M\vdash^*J$ in exactly k moves.
\end{itemize}
{\footnotesize The subscript $M$ can be dropped whenever the particular PDA $M$ is understood.}

\subsection{Accepted languages of the PDA}
For PDA $M=(Q,\Sigma, \Gamma, \delta, q_0, Z_0,F)$ we define two language:
\begin{itemize}
    \item $L(M)$, the language accepted by final state, to be\\
        $L(M)=\{w\in \Sigma^*\mid (q_0,w,Z_0) \vdash^* (p,\varepsilon,\gamma)$ for some
        $p\in F$ and $\gamma \in \Gamma^*\}$
    \item $N(M)$, the language accepted by empty stack, to be\\
        $N(M)=\{w\in \Sigma^*\mid (q_0,w,Z_0)\vdash^*(p,\varepsilon,\varepsilon)$ for some
        $p \in Q\}$.
\end{itemize}
{\footnotesize $L(M)$ contains a word $w$ if after reading $w$, $M$ can be (nondeterminism!)
in some final state.\\
$N(M)$ contains a word $w$ if after reading $w$, $M$ can have (nondeterminism!) its stack empty.
If acceptance is by empty stack, final states are irrelevant; in this case, we usually 
let $F=\emptyset$.}

\subsection{Deterministic pushdown automata}
A PDA $M=(Q,\Sigma, \Gamma, \delta, q_0, Z_0,F)$ is said to be deterministic if $\delta$
fulfills two conditions for every $q\in Q$ and $Z \in \Gamma$:
\begin{enumerate}
    \item $\delta(q,\varepsilon,Z) \neq \emptyset \Rightarrow \forall a \in \Sigma:\delta(q,a,Z)=\emptyset$
    \item $\forall a \in \Sigma \cup \{\varepsilon\}: |\delta(q,a,Z)|\leq 1$
\end{enumerate}
{\footnotesize What does that mean? Condition 1 prevents the possibility of a choice between
$\varepsilon$-moves and regular moves. Condition 2 prevents the possibility of a choice for
$\varepsilon$-moves and the possibility of a choice for regular moves.}\\
\emph{Note:} Unlike FA, a PDA is assumed to be non-deterministic unless we state
otherwise. In this case, we denote it by DPDA (for deterministic PDA).

\subsection{Pushdown automata and context-free languages}
\subsubsection{Equivalence of acceptance by final state and empty stack}
If $L=L(M_2)$ for some PDA $M_2$, then $L=N(M_1)$ for some PDA $M_1$.\\
{\footnotesize \emph{Proof idea:} Given an arbitrary $L=L(M_2)$, construct a PDA $M_1$ that
simulates $M_2$ but erases the stack whenever $M_2$ enters a final state. So we have $L=N(M_1)$}
\\\\
If $L=L(M_1)$ for some PDA $M_1$, then $L=N(M_2)$ for some PDA $M_2$.\\
{\footnotesize \emph{Proof idea:} Given an arbitrary $L=L(M_1)$, construct a PDA $M_2$ that
simulates $M_1$ but enters a final state whenever $M_1$ erases its stack. So we have $L=N(M_2)$}
\\\\
$\Rightarrow$ The class of languages accepted by PDAs by final state is
the same as the class of languages accepted by PDAs by empty stack.

\subsubsection{Equivalence of PDAs and CFLs}
If $L$ is a $CFL$, then there exists a PDA $M$ sucha that $L=N(M)$.
{\footnotesize \emph{Proof idea:} Let $L$ be an arbitrary CFL. $L$ can be generated by a CFG
$G$ in Greibach normal form. Constructa PDA $M$ that simulates leftmost derivations of $G$. 
(It is easier to have $M$ accept by empty stack.) So $L=N(M)$}
\\\\
If $L=N(M)$ for some PDA $M$, then $L$ is a CFL
{\footnotesize \emph{Proof idea:} Let $M$ be an arbitrary PDA. Construct a CFG $G$ in such
a way that a leftmost derivation in $G$ of a sentence x is a simulation of the PDA $M$ when
given the input x. So $L=L(G)$, a CFL.}
\\\\
The class of languages accepted by PDAs is exactly the class of CFLs.

\subsubsection{Deterministic vs. nondeterministic PDAs}
DPDAs are less powerful than PDAs (they dont accept the same class of languages).
\\\\
$\{ww^R\mid w\in (0+1)^*\}$ is accepted by a PDA and by no DPDA.

\section{Properties of Context-Free Languages}
\subsection{The Pumping Lemma for CFLs}
Let $L$ be a CFL. Then there is a constant $n$ (depending on $L$ only) such that the
following holds:\\
if $z$ is any word such that
\begin{itemize}
    \item[] $z\in L$ and $|z| \geq n$,
\end{itemize}
then there exist words $u,v,w,x,y$ such that
\begin{itemize}
    \item[] $z = uvwxy$,
    \item[] $|vx| \geq 1$,
    \item[] $|vwx| \leq n$, and
    \item[] $\forall i \geq 0:uv^iwx^iy\in L$   
\end{itemize}
{\footnotesize \emph{Informally:} Given any sufficiently long word $z$ in a CFL $L$,
we can find two short sub-words $v$ and $x$ close together that may be repeated, both the
same arbitrary number of times, and the resulting word is still in $L$.}
\\\\
There exist languages that are not context-free!
For such languages we’ll need a model of computation more powerful than PDA.

\subsection{Closure properties for CFL's}
The class of CFLs is closed under
\begin{itemize}
    \item union,
    \item concatenation,
    \item Kleene closure,
    \item substitution (and hence homomorphism),
    \item inverse homomorphism
\end{itemize}
The class of CFLs is not closed under
\begin{itemize}
    \item intersection (unless $\downarrow$),
    \item complementation
\end{itemize}
If $L$ is a CFL and $R$ is a regular set, then $L \cap R$ is a CFL

\subsection{Emptiness and finiteness of CFLs}
There are decision algorithms to determine whether or not a CFL is:
\begin{enumerate}
    \item empty;
    \item finite.
\end{enumerate}
{\footnotesize \emph{Proof idea: }Let $G=(V,T,P,S)$ be a CFG
\begin{itemize}
    \item $L(G)$ is nonempty \emph{iff} $S$ generates some string of terminals
    \item $L(G')$ is finite \emph{iff} the graph has no cycles.\\
        G' is the Chomsky Normal Form (with no useless symbols) of G
\end{itemize}
}

\subsection{Membership}
The Membership for CFGs is the question "Given a CFG $G=(V,R,P,S)$ and a word $x\in T^*$,
is $x \in L(G)$?"\\
\emph{Question: }Does there exist a decision algorithm such that, given an arbitrary CFG $G$
and an arbitrary word $x\in T^*$, answers the question "Is x a member of $L(G)$?"\\
\emph{Answer: }The answer is YES; there is the following naive algorithm:
\begin{enumerate}
    \item Convert G to Greibach normal form (GNF) $G'$
    \item If $x=\varepsilon$ then test whether $S$ $_G\Rightarrow^*\varepsilon$ else\\
        check all possible derivations in G'. A total of $\leq k^{|x|}$ leftmost derivations
        need to be examined.
\end{enumerate}
The CYK algorithm (Cocke-Younger-Kasami)
\begin{itemize}
    \item dynamic programming
    \item $O(n^3)$ time, where $n=|x|$.
    \item algorithm described \emph{p.181/182}
\end{itemize}

\section{Turing machines}
An ‘‘algorithm’’ for solving a problem is
a \emph{finite set of instructions} that lead the processor, in a \emph{finite number of steps},
from the \emph{input data} of the problem to the corresponding \emph{solution}. 
\\\\
History lesson \emph{p.187}
\\\\
To systematically eliminate all possible recipes for solving a problem we need a model of computation:\\
A \emph{model of computation} is a definition that formally characterizes the basic notions of algorithmic computation, that is,
the algorithm, its environment, and the computation.
\\\\
Several were proposed:
\begin{itemize}
    \itemsep0em
    \item $\mu$-recursive functions
    \item general recursive functions
    \item $\lambda$-calculus
    \item Turing machine
    \item Post machine
    \item Markov algorithms
\end{itemize}
The majority of researchers accepted the Turing machine as the model which most
adequately captures the basic concepts of computation.
\\\\
Moreover, surprisingly, it was soon proved that the models are equivalent in the sense:\\
What can be computed by one can also be computed by the others.
\\\\
Computability thesis (Church-Turing thesis). The basic intuitive concepts
of computing are perfectly formalized as follows: 
\begin{itemize}
    \itemsep0em
    \item ‘‘algorithm’’ is formalized by Turing program
    \item ‘‘computation’’ is formalized by execution of a Turing program in a Turing machine
    \item ‘‘computable function’’ is formalized by Turing-computable function
\end{itemize}
The Computability Thesis established a bridge between our intuitive understanding of
the concepts of the “algorithm,” “computation,” and “computability” on the one hand,
and their formal counterparts defined by models of computation on the other.
In this way it finally enabled a mathematical treatment of these intuitive concepts.

\subsection{The Turing machine model}
The basic variant of the Turing machine has
the following components: a control unit containing a Turing program; a tape
consisting of cells; and a movable window over the tape, which is connected to
the control unit. The details are:
\begin{itemize}
    \item The tape is used for writing and reading the input data, intermediate data, and
    output data (results). It is divided into equally sized cells, and is potentially infinite in
    one direction (i.e., it can be extended in that direction with a finite number of cells)
    \item[] Each cell contains a tape symbol belonging to a tape alphabet
    $\Gamma=\{z_1,\dots ,z_t\},t\geq 3$. The symbol $z_t$ is special, for it indicates that
    a cell is empty; for this reason it is denoted by $\sqcup$ and called the empty space.
    In addition to $\sqcup$ there are at least two additional symbols: 0 and 1. We will
    assume that $z_1=0$ and $z_2=1$.
    \item[] The input data are contained in the input word. This is a word over an input
    alphabet $\Sigma$, such that $\{0,1\} \subseteq \Sigma \subseteq \Gamma - \{\sqcup\}$.
    Initially, all the cells are empty (each contains $\sqcup$) except for the leftmost
    cells, which contain the input word.
    \item The control unit is always in some state from a finite set of states
    $Q =\{q_1,\dots ,q_s\},s\geq 1$. We call $q_1$  the initial state. Some states are
    called final; they are gathered in the set $F \subseteq Q$. All the other states are
    non-final. If the index of a state is of no importance, we use $q_{yes}$ and $q_{no}$
    to refer to any final and non-final state, respectively.
    \item[] There is a Turing program (TP) in the control unit. TP directs TM’s components.
    TP is characteristic of the particular TM, i.e., different TMs have different TPs.
    A TP is a partial function
    $\delta : Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R,S\}$, called the
    transition function.\\
    {\footnotesize \emph{Note:} The TM is by definition deterministic, having at most
    one choice for a move in each situation.}
    \item[] We can view $\delta$ as a table $\Delta = Q \times \Gamma$, where
    \begin{itemize}
        \item $\Delta[q_i,z_r] =(q_j,z_w,D)$ if $\delta(q_i,z_r) = (q_j, z_w, D)$ is an 
            instr. of $\delta$,
        \item $\Delta[q_i,z_r]=0$ if $\delta(q_i,z_r)\uparrow$ (undefined).
    \end{itemize} 
    \item[] Without loss of generality, we can assume that there
    is always a transition from a $q_{no}$, and none from $q_{yes}$.
    \item The window can move over any cell. Then, the control unit can read a symbol
    through the window, and write a symbol through the window, substituting the
    previous symbol. In one step, the window can only move to the neighboring cell.
    \item Before the TM is started, the following must take place:
        \begin{enumerate}
            \item an input word is written to the beginning of the tape
            \item the window is shifted to the beginning of the tape
            \item the control unit is set to the initial state
        \end{enumerate}
    \item From now on the TM operates independently, in a mechanical stepwise fashion as
    instructed by its TP. If the TM is in a state $q_i \in Q$ and it reads a symbol
    $z_r \in \Gamma$, then:
        \begin{itemize}
            \item[] if $q_i$ is a final state, then TM halts
            \item[] else, if $\delta (q_i, z_r) \uparrow$ (i.e. TP has no next instruction),
                then the TM halts
            \item[] else, if $\delta (q_i, z_r) \downarrow = (q_j,z_w,D)$, then the TM does
                does the following:
                \begin{enumerate}
                    \item changes the state to $q_j$
                    \item writes $z_w$ through the window
                    \item moves the window to the next cell in the direction $D\in \{L,R\}$
                        (for left and right), or leaves the window where it is ($D=S$, for stay)
                \end{enumerate} 
        \end{itemize}
\end{itemize}
Formally, a TM is a seven-tuple $T=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$. To fix a
particular TM, we must fix $Q,\Sigma,\Gamma,\delta,F$.
\\\\
An instantaneous description (ID) of a TM is the string $I = \alpha_1q\alpha_2$, if the
current configuration of the TM has the window over the first symbol of $\alpha_2$ and
$\alpha_2$ ends at the rightmost non-blank symbol.\\
{\footnotesize An ID is the ``snapshot’’ of a current configuration (status) of TM’s
components between successive instructions.}
\\\\
An ID $I$ can directly change to $J$ -- written $I \vdash J$ -- if there is an
instruction in TM's program whose execution changes $I$ to $J$. The reflexive and
transitive closure of $\vdash$ is $\vdash^*$; if $I \vdash^*J$, then we say that
ID $I$ can change to $J$.
\subsection{Use of a turing machine}
There are three elementary tasks where TMs are used:
\begin{itemize}
    \item Function computation\\
        ''Given a function $\varphi$ and arguments $a_1,\dots,a_k$, compute $\varphi(a_1,\dots,a_k)$.''
    \item Set recognition\\
        ''Given a set $S$ and an object $x$, decide whether or not $x \in S$.''
    \item Set generation\\
        ''Given a set $S$, generate a list $x_1,x_2,x_3,\dots$ of exactly the members of $S$.''
\end{itemize}

\subsubsection{Function computation on TMs}
Each TM $T$ induces, for any $k\geq 1$, a function $\varphi_T$ that maps $k$ words into 1 word.
We define $\varphi_T$ as follows.\\
Let $T=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a TM and $k\geq 1$. The $k$-ary proper function
of $T$ is a partial function $\varphi_T:(\Sigma^*)^k\rightarrow \Sigma^*$, defined as follows:\\
If the input to $T$ is $k$ words $u_1,\dots,u_k \in \Sigma^*$, then the value of $\varphi_T$
at $u_1,\dots,u_k$ is defined to be\\
\begin{equation*}
    \varphi(u_1,\dots,u_k) :=
    \begin{cases}
        v, & \text{if $T$ halts $\wedge$ returns on the tape the word $v \wedge v \in \Sigma^*$;} \\
        \uparrow, & \text{if $T$ doesn't halt $\vee$ the tape doesn't have a word in $\Sigma^*$.}
    \end{cases}
\end{equation*}
The interpretation of $u_1,\dots ,u_k$ and $v$ is arbitrary.
\\\\
In practice, however, we usually face the opposite task:\\
``Given a $k$-ary function $\varphi : (\Sigma^*)^k \rightarrow \Sigma^*$, find a TM $T$
that can compute $\varphi$'s values.''\\
{\footnotesize That is, given $\varphi$, we must construct a TM $T$ such that $\varphi_T = \varphi$.}
\\\\
Let $\varphi : (\Sigma^*)^k \rightarrow \Sigma^*$ be a function. Then:
\begin{itemize}
    \item $\varphi$ is computable if $\exists$TM that can compute $\varphi$ anywhere on
        $dom(\varphi) \wedge dom(\varphi) = (\Sigma^*)^k$;
    \item $\varphi$ partial computable (p.c.) if $\exists$TM that can compute $\varphi$ anywhere on $dom(\varphi)$;
    \item $\varphi$ incomputable if there is no TM that can compute $\varphi$ anywhere on $dom(\varphi)$.
\end{itemize}

\subsubsection{Set recognition on TMs}
Each TM $T$ induces a language $L(T)$, the language accepted by $T$.
\\\\
Let $T=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a TM and $w \in \Sigma^*$ a string. We
say that $w$ is accepted by $T$ if $q_1w\vdash^*\alpha_1p\alpha_2$, for some $p\in F$ and
$\alpha_1\alpha_2 \in \Gamma^*$. The language accepted by $T$ is the set
$L(T)=\{w\mid w\in \Sigma \wedge w$ is accepted by $T\}$.\\
{\footnotesize So, a word is accepted by $T$ if it causes $T$ to enter a final state
(if submitted as input). The language accepted by $T$ consists of exactly such words.}
\\\\
The interpretation of $w$ is arbitrary.
\\\\
In reality, however, we usually face the opposite task:\\
``Given a set $S \subseteq \Sigma^*$, find a TM $T$ that accepts $S$.''\\
{\footnotesize That is, given a language (set) $S$, we must construct a TM $T$ such that
$L(T) = S$.}
\\\\
Let $S \subseteq \Sigma^*$ be a language (set). Then:
\begin{itemize}
    \item S is decidable if $\exists$TM that answers YES/NO to ``Is $x\in S$?'' for any $x\in \Sigma^*$.
    \item S is semi-decidable if $\exists$TM that answers YES to ``Is $x\in S$?'' whenever $x \in S$
    \item S in undecidable if there is no TM that answers YES/NO to ``Is $x\in S$? for any $x\in \Sigma^*$''
\end{itemize}
It looks that for some sets $S$ we cannot algorithmically decide the question ``Is $x\in S$?''\\
Why?
\begin{itemize}
    \item[] If $S=L(T)$ is semi-decidable and $x\in \Sigma^*$ an arbitrary word, then:
        \begin{itemize}
            \item[$\bullet$] if $x$ is in $S$, then $T$ will eventually halt on input $x$ (and accept $x$).
            \item[$\bullet$] But if $x$ is not in $S$, then $T$ may not halt on input $x$ (and never reject $x$).
        \end{itemize}
    \item[] For such an $S$, as long as $T$ is still running on input x, we cannot tell whether
        \begin{itemize}
            \item[$\bullet$] T will eventually halt (and accept/reject $x$) if we let $T$ run long enough, or
            \item[$\bullet$] T will run forever.
        \end{itemize}
    \item[] In other words:
        \begin{itemize}
            \item[$\bullet$] If, in truth, $x\in S$, then $T$ will (halt and accept x and) answer YES
            \item[$\bullet$] It, in truth, $x\notin S$, then
                \begin{itemize}
                    \item[$-$] T may (halt and reject x and) answer NO; or
                    \item[$-$] T may (never halt and) never answer NO. 
                \end{itemize}
        \end{itemize}
\end{itemize}

\subsubsection{Set generation on TMs}
Let $T=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a TM. $T$ is called a generator if it
writes to its tape, in succession and delimited by \#, (some) words from $\Sigma^*$.
(We assume that \# is in $\Gamma - \Sigma$.) The language generated by $T$ is defined
to be the set $G(T) = \{w \mid w \in \Sigma^* \wedge T$ eventually writes $w$ to the tape\}.
\\\\
In practice, we usually face the opposite task:\\
``Given a set $S$, generate a list $x_1,x_2,x_3,\dots$ of exactly the members of $S$.''\\
{\footnotesize That is, given a language (set) $S$, we must construct TM $T$ such that $G(T)=S$.}
\\\\
\emph{Questions:} When can the elements of a given set $S$ be generated, i.e. listed in
a sequence so that every element of $S$ eventually appears in the sequence?
When can such a sequence be algorithmically generated, i.e., by a TM?
Can every countable set be algorithmically generated?

\subsubsection{C.E. languages (sets)}
Suppose that the elements of a given set $S$ can be listed in a sequence so that every element
of $S$ eventually appears in the sequence. If $x$ is an arbitrary element of $S$, then $x$ will
eventually appear in the list; it will appear as $n$th in order, for some $n \in N$. So we can
speak of the $1^{st},2^{nd},3^{rd},\dots n^{th}, \dots$ element of $S$. Because the elements
of $S$ can be enumerated, we say that $S$ is enumerable.
\\\\
A set $S$ is computably enumerable (c.e.) if $S=G(T)$ for some TM $T$; that is, if $S$ can be
generated by a TM.
\\\\
A set $S$ is c.e. \emph{iff} $S$ is semi-decidable.

\subsection{Modifications of the Turing machine}
This holds true for all following modified TMs:\\
Although $V$ seems to be more powerful than the basic model $T$, it is not so; $T$ can
compute anything that $V$ can compute. We prove this by describing how $T$ can simulate $V$.
(The other way round is obvious as $T$ is a special case of $V$.)
\subsubsection{TM with finite storage}
This variant $V$ has in its control unit a finite storage capable of memorizing $k \geq 1$
tape symbols and using them during the computation. The Turing program (TP) is the function
$\delta_V:Q\times\Gamma \times \Gamma^k \rightarrow Q\times \Gamma \times \{L,R,S\} \times \Gamma^k$.

\subsubsection{TM with multiple-track tape}
This variant $V$ has the tape divided into $tk\geq 2$ tracks. On each track there are
symbols from the alphabet $\Gamma$. The window displays $tk$-tuples of symbols, one symbol
for each track. The TP is $\delta_V: Q \times \Gamma^{tk} \rightarrow Q \times \Gamma^tk \times \{L,R,S\}$.

\subsubsection{TM with two-way infinite tape}
This variant $V$ has the tape unbounded in both directions. Formally, the TP is the function
$\delta_V:Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R,S\}$.

\subsubsection{TM with multiple tapes}
This variant $V$ has $tp \geq 2$ unbounded tapes. Each tape has its own window that is
independent of other windows. TP is $\delta_V:Q\times \Gamma^{tp} \rightarrow Q\times (\Gamma \times \{L,R,S\})^{tp}$.

\subsubsection{TM with multidimensional tape}
This variant $V$ has a $d$-dimensional tape, $d\geq 2$. The window can move in $d$ dimensions,
i.e., 2$d$ directions $L_1,R_1,L_2,R_2,\dots , L_d,R_d$. The turing program is
$\delta_V:Q\times \Gamma \times \{L_1,R_1,L_2,R_2,\dots ,L_d,R_d,S\}$.

\subsubsection{TM with nondeterministic program}
This variant $V$ has a Turing program $\delta$ that assigns to each $(q_i,z_r)$ a finite
set of alternative transitions $\{(q_{j1},z_{w1},D_1),(q_{j2},z_{w2},D_2),\dots \}$. The
machine nondeterministically chooses a transition from the set and performs it.
\\\\
How does $V$ choose a transition out of the current alternatives?\\
The following is assumed: the machine \emph{chooses} a transition that leads it to a solution
(e.g., to a state $q_{yes}$), if such transitions exist; otherwise, the machine halts.\\
{\footnotesize The nondeterministic TM is not a reasonable model of computation because it can foretell the future when
choosing from alternative transitions. Nevertheless, it is a very useful tool, which makes it possible to define the
minimum number of steps needed to compute the solution (when a solution exists). This is important when we
investigate the computational complexity of problem solving. We will see that in the following chapters. }

\subsubsection{The importance of the modifications of the TM}
The modifications are useful when we try to prove the existence of a TM
for solving a given problem $P$. Usually, the construction of such a TM is easier if we choose a
more versatile modification of TM.
\begin{itemize}
    \item[] Sometimes, we can even avoid the complicated construction of the actual TM for solving $P$.\\
    How? We do as follows:
        \begin{enumerate}
            \item We devise an intuitive algorithm $A$ (a ``recipe’’, finite list of instructions) for solving $P$. 
            \item Then we say: ``By the Computability Thesis, there is a TM $T$ that does the same as $A$.”
            Then, we can refer to this $T$ (as the true algorithm for solving $P$) and treat it mathematically.
        \end{enumerate}
\end{itemize}
Since none of the modifications is more powerful than the basic TM, this additionally
supports our belief that the Computability Thesis is true. 
\\\\
The computations on the modifications of TM can considerably differ in \emph{time} (number of steps) and
\emph{space} (number of visited cells). But this will become important only in Computational Complexity
Theory (where we will investigate the time and/or space complexity of problem solving).

\subsection{Universal turing machine}
\subsubsection{Coding of TMs}
Given a TM $T=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$, we want to encode $T$, i.e. represent
$T$ by a word over some coding alphabet.
\\\\
How will we encode TM $T$?
\begin{itemize}
    \item The coding alphabet will be $\{0,1\}$.
    \item We'll only encode $\delta$, but in such a way that $Q,\Sigma,\Gamma,F$ which
        determine the particular $T$, can be restored (obtained) from the encoded $\delta$.
        How will we encode TP $\delta$?
        \begin{enumerate}
            \item If $\delta(q_i,z_j)=(q_k,z_l,D_m)$ is an instruction of $\delta$,
                then we will encode the instruction by the word\\
                $$K=0^i10^j10^k10^l10^m$$
                where $D_1=L,D_2=R,D_3=S$.
            \item In this way, we will encode each instruction of $\delta$.
            \item From the obtained codes $K_1,K_2,\dots ,K_r$ we will construct the code
                $\langle\delta\rangle$ of $\delta$:
                $$\langle\delta\rangle = 111K_111K_211\dots 11K_r111$$
        \end{enumerate}
    \item We will identify the code $\langle T \rangle$ of the TM $T$ with
        $\langle\delta\rangle$, i.e. $\langle T \rangle := \langle\delta\rangle$.
\end{itemize}

\subsubsection{Enumeration of TMs}
We can interpret $\langle T \rangle$ as the binary code of some natural number. We call this
number the index of $T$.
\\\\
Notice that some natural numbers are not indexes (because their binary codes do not have
the required form, which results from the encoding method).
\begin{itemize}
    \item To avoid this we introduce the following convention:\\
        Any natural number whose binary code is not of the required form is an index of
        the empty TM.
    \item[] The $\delta$ of the empty TM is everywhere undefined; for every input, this
        TM immediately halts (in 0 steps).
\end{itemize}
Now we can say: every natural number is the index of exactly one TM.
\\\\
Given an arbitrary $n\in N$, we can obtain from the $n$ the components $Q,\Sigma,\Gamma,F$
that define the particular TM (i.e. the TM whose index is $n$). How?
\begin{enumerate}
    \item We inspect the binary code of $n$ to check if it is of the required form
        $111K_111K_211\dots 11K_r111$.
    \item If it is, we partition the code into strings $K_1,K_2,\dots ,K_r$ and
        by analyzing these we can collect all the information needed to obtain all the
        components $\delta,Q,\Sigma,\Gamma,F$ of the TM $T$.
\end{enumerate}
The restored TM can be viewed as the $n$th basic TM and denoted by $T_n$.
\\\\
By letting $n$ run through $0,1,2,\dots$ we obtain the sequence of TMs
$$T_0,T_1,T_2,\dots$$
Notice that this is an enumeration of all basic TMs.

\subsubsection{The existence of a universal turing machine}
There is a Turing machine $U$ that can compute whatever is computable by any other Turing
machine.\\\\
{\footnotesize\emph{Proof idea: } The idea is to construct a Turing machine U that will be capable
of simulating any other TM $T$. To achieve this, we use the method of proving
by Computability Thesis (CT):
\begin{enumerate}
    \item first, we describe the concept of the machine U and describe the intuitive
    algorithm (that should be) executed by U’s Turing program, and 
    \item then we refer to CT to prove that U exists.
\end{enumerate}}

Proof
\begin{itemize}
    \item The input tape contains an input word consisting of two parts: the code
        $\langle T \rangle$ of an arbitrary Turing machine
        $T=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$, and an arbitrary word w.
    \item The work tape is initially empty. The machine $U$ will use it in exactly the
        same way as $T$ would use its own tape when given the input $w$.
    \item The auxiliary tape is initially empty. The machine $U$ will use it
        to record the current state in which $T$ would be at that time, and for
        checking whether this state is a final state of $T$.
    \item The control unit contains a Turing program that executes an algorithm.
\end{itemize}
The Turing program of $U$ should execute the following intuitive algorithm: 
\begin{enumerate}
    \item Check if the input word is $\langle T,w \rangle$, where $\langle T \rangle$ is
        a code of some TM. If it is not, halt.
    \item From $\langle T \rangle$ restore $F$ and write  $\langle q_1,F \rangle$ to the
        auxiliary tape.
    \item Copy $w$ to the work tape and shift its window to the beginning.
    \item (Let the auxiliary tape have  $\langle q_i,F \rangle$ and the work tape window scan $z_r$).\\
        If $q_i \in F$, halt. ($T$ would halt in the final state $q_i$).
    \item On the input tape, search in  $\langle T \rangle$ for the code of the instruction
        $\delta(q_i,z_r) = \dots$
    \item If not found, halt ($T$ would halt in the final state $q_i$).
    \item (The instruction $\delta(q_i,z_r) = \dots$ was found and is $\delta(q_i,z_r)=(q_j,z_w,D)$.\\
        On the work tape, write the symbol $z_w$ and move the window in the direction $D$.
    \item On the auxilliary tape, replace  $\langle q_i,F \rangle$ by  $\langle q_j,F \rangle$.
    \item Return to step 4.
\end{enumerate}
This algorithm can be executed by a human. By the Computability thesis, there exists a TM
$U = (Q_U,\Sigma_U,\Gamma_U,\delta_U,q_1,\sqcup,F_U)$ whose $\delta_U$ does the same
(executes the algorithm). We call $U$ the \emph{Universal turing machine} (UTM).

\subsubsection{Construction of an UTM}
What is the simplest UTM?
\begin{itemize}
    \item We focus on UTMs with no storage and a single two-way infinite tape with one track.
    \item How shall we measure the `simplicity’ of such UTMs?
        \begin{itemize}
            \item Shannon proposed the product $|Q_U|$·$|\Gamma_U|$ (the maximal number of instructions in $\delta_U$)
            \item A more realistic measure would be the actual number of instructions in $\delta_U$. 
        \end{itemize}
\end{itemize}
Researchers focused on different classes of UTMs, denoting them by $UTM(s,t)$ where $s,t \geq 2$,
containing all UTMs with $s$ states and $t$ tape symbols.
\\\\
The smallest one (for now) is UTM(4,5) = 22 instructions

\subsubsection{The importance of the Universal Turing Machine}
Turing’s discovery of a universal TM was a theoretical proof that
a general-purpose computing machine is possible, at least in principle. 
\\\\
Turing was certain that such a machine could be built in reality:\\
It is possible to construct a physical computing machine that can
compute whatever is computable by any other physical computing machine.\\
He envisaged something that is today called the general-purpose computer. 

\subsection{The first basic results}
\emph{Theorems}\\
Let $S,A,B$ be arbitrary sets. Then:
\begin{enumerate}
    \item $S$ is decidable $\Rightarrow$ $S$ is semi-decidable
    \item $S$ is decidable $\Rightarrow$ $\overline{S}$ is decidable
    \item $S$ and $\overline{S}$ are semi-decidable $\Rightarrow$ $S$ is decidable
    \item $A$ and $B$ are semi-decidable $\Rightarrow$ $A \cap B$ and $A \cup B$ are semi-decidable
    \item $A$ and $B$ are decidable $\Rightarrow$ $A \cap B$ and $A \cup B$ are decidable
\end{enumerate}

\section{Undecidability}
\subsection{Decision problems and other kinds of computational problems}
We define the following four kinds (classes) of computational problems:
\begin{itemize}
    \item \emph{Decision problems} (also called yes/no problems). The solution of a
    decision problem is the answer YES or NO (The solution is a single bit.)
    \item \emph{Search problems}. Given a set $S$ and a property $P$, the solution of the
    search problem is an element $x$ of $S$ such that $x$ has the property $P$.
    (The solution is an element of a set.) 
    \item \emph{Counting problems}. Given a set $S$ and a property $P$, the solution of a
    counting problem is the number of elements of $S$ that have the property $P$.
    (The solution is a natural number.) 
    \item \emph{Generation problems} (also called enumeration problems). Given a set $S$
    and a property $P$, the solution of a generation problem is a list of elements of
    $S$ that have the property $P$.
    (The solution is a sequence of elements of a set.) 
\end{itemize}
We will focus on the decision problems.\\
Because the decision problems ask for the simplest possible solutions, i.e.
solutions representable by a single bit. (We are pragmatic and hope that this
will make our study of other kinds of computational problems simpler.) \\

\subsection{Problem solving}
\subsubsection{Language of a decision problem}
There is a link between decision problems and sets that enables us to reduce the
questions about decision problems to questions about sets. We’ll uncover it in 4 steps. 
\begin{enumerate}
    \item Let $D$ be a decision problem. 
    \item We are usually faced with a particular instance $d$ of the problem $D$. The instance $d$ is
    obtained from $D$ by replacing the variables in the definition of $D$ with actual data.
    The problem $D$ can be viewed as the set of all the possible instances of $D$. We will say
    that an instance $d\in D$ is positive/negative if the answer to $d$ is YES/NO, respectively. 
    \item {\scriptsize In the natural-language description of $d$ there can be various actual data (numbers,
    matrices, graphs, $\dots$). However, to compute the answer on a machine—be it an
    abstract model such as the TM or a modern computer—we must represent these
    actual data in a form that is understandable to the machine. How? }\\
    Since any machine uses some alphabet $\Sigma$ (e.g. $\Sigma=\{0,1\}$), we must choose a
    function that will transform (code) every instance of $D$ into a word in $\Sigma^*$. 
    We call such a function the \emph{coding function} and denote it by ‘code’. Thus, code:
    $D \rightarrow \Sigma^*$, and
    $code(D)$ is the set of codes of all instances of $D$. We will write $\langle d \rangle$
    instead of code($d$).
    \item Gather the codes of all the positive instances of D in a set L(D).\\
        The language of a decision problem $D$ is the set $L(D)$ which is defined as
        $L(D)= \{\langle d \rangle \in \Sigma^* | d$ is a positive instance of $D\}$.
\end{enumerate}
Now observe that the following relation holds:\\
\centerline{$d\in D$ is positive $\Leftrightarrow \langle d \rangle \in L(D)$}\\
This is the link between decision problems and sets (formal languages).
\\\\
What we gain: \\
Solving a decision problem $D$ can be reduced to recognizing the set $L(D)$ in $\Sigma^*$.\\
{\footnotesize The answer to the instance $d$ of $D$ can be found if we determine where is
$\langle d \rangle$ relative to $L(D)$}\\
The link is important because it enables us to apply --when discussing and/or
solving decision problems --all the theory that we developed to recognize sets. 
\\\\
What does the recognizability of $L(D)$ tell us about the solvability of $D$ ? 
\begin{itemize}
    \item $L(D)$ is decidable $\Rightarrow$ There is an algorithm that, for any $d\in D$,
        answers yes or no.\\
        {\footnotesize \emph{Proof: }There is a TM that, for any $\langle d \rangle \in \Sigma^*$,
        decides whether or not $\langle d \rangle \in L(D)$}
    \item $L(D)$ is semi-decidable $\Rightarrow$ Then there is an algorithm that,
    \begin{itemize}
        \item for any positive $d\in D$, answers yes;
        \item for a negative $d\in D$, may or may not answer no in finite time
    \end{itemize}
        {\footnotesize \emph{Proof: }There is a TM that, for any $\langle d \rangle \in L(D)$,
        accepts $\langle d \rangle$. However, if $\langle d \rangle \notin L(D)$, the algorithm
        may or may not reject $\langle d \rangle$ in finite time.}
    \item $L(D)$ is undecidable $\Rightarrow$ Then there is no algorithm that,
        for any $d\in D$, answers yes or no.\\
        {\footnotesize \emph{Proof: } There is no TM capable deciding, for any 
        $\langle d \rangle \in \Sigma^*$, whether or not $\langle d \rangle \in L(D)$.}
\end{itemize}
Let D be a decision problem. We say that the problem
\begin{itemize}
    \item $D$ is decidable (or computable)      $L(D)$ is a decidable set;
    \item $D$ is semi-decidable                 $L(D)$ is a semi-decidable set;
    \item $D$ is undecidable (or incomputable)  $L(D)$ is an undecidable set.
\end{itemize}
\emph{Terminology}\\
{\footnotesize Instead of a decidable/undecidable problem we can say computable/incomputable
problem. But the latter notion is more general: it can be used with all kinds of
computational problems, not only decision problems. The terms solvable/unsolvable is
even more general: it addresses all kinds of computational and non-computational problems. }

\subsection{Halting problem}
The halting problem $D_{Halt}$ is defined by\\
\centerline{$D_{Halt}=$ ``Given a TM $T$ and $w\in \Sigma^*$, does $T$ halt on $w$?''}
\\\\
The halting problem $D_{Halt}$ is undecidable.\\
{\footnotesize \emph{Comment:} This means that there exists no algorithm capable of answering,
for arbitrary $T$ and $w$, the question “Does $T$ halt on $w$?”
So, any algorithm whatsoever, which we might design now or in the future for
answering this question, will fail to give the answer for at least one pair $T$, $w$. }
\\\\
The universal language, denoted by $K_0$, is the language of the Halting problem, that is,\\
\centerline{$K_0 = L(D_{Halt}) = \{\langle T,w \rangle \mid T$ halts on $w\}$.}
\\\\
The second language is obtained from $K_0$ by imposing the restriction $w:=\langle T \rangle$.\\
The diagonal language, denoted by $K$, is defined by\\
\centerline{$K=\{\langle T,T \rangle \mid T$ halts on $\langle T \rangle\}$}
\\\\
\emph{Note:}
\begin{itemize}
    \item $K$ is the language of the problem $D_H$ = ``Given a TM $T$ does $T$ halt on $\langle T \rangle$''
    \item $D_H$ is a subproblem of $D_{Halt}$ (since it is obtained from $D_{Halt}$ by fixing $w$ to $w=\langle T \rangle$).
\end{itemize}
\emph{Proof idea:}\\
We suppose that K is a decidable set.\\
Then there must exist a TM $D_K$ that for any $T$, answers $\langle T,T \rangle \in ? K$:\\
\begin{equation*}
    D_K(\langle T,T \rangle) =
    \begin{cases}
        \text{yes}, & \text{if $T$ halts on $\langle T \rangle$;} \\
        \text{no}, & \text{if $T$ doesn't halt on $\langle T \rangle$;}
    \end{cases}
\end{equation*}
Our intention is to construct $S$ in such a way that, when given as input its own code $\langle S \rangle$,
$S$ will expose the incapability of $D_K$ to predict whether or not $S$ will halt on $\langle S \rangle$
\\\\
$D_K$ is unable to correctly decide the question $\langle S,S \rangle \in ? K$, but this
contradicts out supposition that $K$ is a decidable set $D_K$ its decider. So $K$ is not decidable.

\subsection{The basic kinds of decision problems}
\subsubsection{The are undecidable sets that are still semi-decidable}
$K_0$ is a semi-decidable set
\begin{itemize}
    \item[] We must find a TM that accepts $K_0$. Here is an idea. Given an arbitrary
        $\langle T,w \rangle$, the machine must simulate $T$ on $w$, and if the simulation
        halts, the machine must return yes and halt. So, if such a machine exists, it will
        answer yes \emph{iff} $\langle T,w \rangle \in ? K_0$. But we already know that
        such a machine exists: it is the Universal Turing machine U. Hence, $K_0$ is
        semi-decidable.
    \item[] \emph{Comment:} this is why $K_0$ is called the universal language.
\end{itemize}
\emph{Corollary:} $K_0$ is an undecidable (but still) semi-decidable set.\\
Similarly we prove for $K$.

\subsubsection{The are undecidable sets that are not even semi-decidable}
$\overline{K_0}$ is not a semi-decidable set.
\begin{itemize}
    \item[] If $\overline{K_0}$ were semi-decidable, then both $K_0$ and $\overline{K_0}$
        would be semi-decidable. But then $K_0$ would be decidable (Post's theorem). This
        would be a contradiction. So $\overline{K_0}$ is not semi-decidable.
\end{itemize}
In the same way we prove that $\overline{K}$ is not a semi-decidable set.
\\\\
A decision problem D can be of one of the 3 kinds (classes):
\begin{itemize}
    \item $D$ is decidable\\
        This means that there is an algorithm that can solve any instance $d\in D$.
        Such an algorithm is called the decider of the problem $D$.
    \item $D$ is semi-decidable undecidable\\
        This means that no algorithm can solve any instance $d\in D$. But there is an
        algorithm that can solve any positive $d\in D$. It is called the recognizer of $D$. 
    \item $D$ is not semi-decidable\\
        This means that for any algorithm there is a positive instance and a
        negative instance of $D$ such that the algorithm cannot solve either of them
\end{itemize}

\subsection{Some Other Incomputable Problems}
There are many other incomputable problems about algebra, programs, grammars that 
no algorithm can completely solve.
\\\\
\subsubsection{Busy beaver problem}
Informally, a busy beaver is the most ‘productive’ TM of its kind.\\
It does not waste time with writing symbols other than 1 or not
moving the window. Let us group such TMs into classes $\tau_n,N=1,2,\dots$ where $\tau_n$
contains TMs with the same number of states.
\\\\
Define $\tau_n$ (for $n\geq 1)$ to be the class of all TMs that have:
\begin{itemize}
    \item the tape unbounded in both ways;
    \item $n$ non-final states (including $q_1$) and one final state $q_{n+1}$;
    \item $\Sigma=\{0,1\}$ and $\Gamma = \{0,1,\sqcup\}$;
    \item $\delta$ that writes only the symbol 1 and moves the window either to L or R.
\end{itemize}
For any $n \geq 1$, there are finitely many TMs in $\tau_n$.
\\\\
We say that a TM $T\in \tau_n$ is a stopper if T halts on an empty input.\\
For every $n \geq 1$, there exists a stopper in $\tau_n$. Hence there is at least one
and at most finitely many (i.e. $|\tau_n|$) stoppers in $\tau_n$.
\\\\
So, there must exist in $\tau_n$ a stopper that attains, among all the stoppers in $\tau_n$,
the maximum number of 1s that are left on the tape after halting.
\\\\
Such a stopper is called the $n$-state busy beaver and denoted $n$-BB.
\\\\
The \emph{busy beaver function} is $s(n)=$ `the number of 1s attained by $n$-BB'\\
The busy beaver function is incomputable. 

\section{Computational complexity theory}
\subsection{Deterministic time and space(classes DTIME, DSPACE)}
\subsubsection{Deterministic time complexity \& complexity classes DTIME}
Let $M=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a DTM with $k \geq 1$ 2-way infinite tapes.
We say that DTM M has \emph{(det.)} time complexity $T(n)$ if, for every $w\in \Sigma^*$
of length $n$, $M$ makes $\leq T(n)$ steps before halting.
\begin{itemize}
    \item It is assumed that $M$ reads all of $w$; thus $T(|w|) \geq |w| + 1$, so $T(n) \geq n+1$.
        So $T(n)$ is at least linear. 
\end{itemize}
A TM $M$ of time complexity $T(n)$ can decide $w\in? L(M)$ in $\leq T(|w|)$ steps.
\\\\
A language $L$ has (det.) time complexity $T(n)$ if there is a DTM $M$ of (det.) time
complexity $T(n)$ such that $L=L(M)$. We define the class of all such languages by\\\\
\centerline{DTIME($T(n)$)=$\{L\mid L$ is a language $\wedge L$ has (det.) time complexity $T(n)\}$}\\\\
{\footnotesize Informally, DTIME($T(n)$) contains all $L$s for which the problem $w\in?L$
can be det. solved in $\leq T(|w|)$ time.}\\
This can be extended to a decision problem D and its language $L(D)$ (p.277).

\subsubsection{Deterministic space complexity \& complexity classes DSPACE}
Let $M=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a DTM with 1 input tape and $k\geq 1$ work
tapes. We say that DTM $M$ has (det.) space complexity $S(n)$ if, for every input
$w\in \Sigma^*$ of length $n$, $M$ uses $\leq S(n)$ cells on each work tape before halting.
\begin{itemize}
    \item input-tape cells do not count
    \item It is assumed that M uses at least the cell under the initial position of the window.
        So $S(n)$ is at least constant function 1.
\end{itemize}
A TM $M$ of space complexity $S(n)$ can decide $w\in ? L(M)$ on space $\leq S(|w|)$.
\\\\
A language $L$ has (det.) space complexity $S(n)$ if there is a DTM $M$ of (det.)
space complexity $S(n)$ such that $L=L(M)$. We define the class of all such languages by
\centerline{DSPACE($S(n)$)$=\{L\mid L$ is a language $\wedge L$ has (det.) space complexity $S(n)\}$}
{\footnotesize Informally, DSPACE($S(n)$) contains all $L$s for which the problem $w\in? L$
can be det. solved on $\leq S(|w|)$ space.}\\
This can be extended to a decision problem D and its language $L(D)$ (p.279).

\subsection{Nondeterministic time and space (classes NTIME, NSPACE)}
\subsubsection{Nondeterministic time complexity \& complexity classes NTIME}
$N=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a NTM. We say that NTM $N$ is of nondet. time
complexity $T(n)$ if, for every input $w\in \Sigma^*$ of length $n$, there exists a
computation in which $N$ makes $\leq T(n)$ steps before halting.
\begin{itemize}
    \item Again it is assumed that $N$ reads all of $w$; thus $T(|w|)\geq |w| +1$, so
        $T(n) \geq n+1$. So $T(n)$ is at least a linear function.
\end{itemize}
A NTM $N$ of time complexity $T(n)$ can decide $w\in = L(N)$ in $\leq T(|w|)$ steps.
\\\\
A language $L$ is of nondet. time complexity $T(n)$ if there is a NTM $N$ of nondet. time
complexity $T(n)$ such that $L=L(N)$. The class of all such languages is\\
\centerline{NTIME($T(n)$)=$\{L\mid L$ is a language $\wedge L$ has nondet. time complexity $T(n)\}$}
{\footnotesize Informally, NTIME($T(n)$) contains all $L$s for which the problem $w\in ? L$
can be nondet. solved in $\leq T(|w|)$ time}.
This can be extended to a decision problem D an its language $L(D)$ (p.282).

\subsubsection{Nondeterministic space complexity \& complexity classes NSPACE}
Let $N=(Q,\Sigma,\Gamma,\delta,q_1,\sqcup,F)$ be a NTM with 1 input tape and $k \geq 1$
work tapes. We say that NTM $N$ is of nondet. space complexity $S(n)$ if, for every input
$w \in \Sigma^*$ of length $n$, there exists a computation in which $N$ uses, before halting,
$\leq S(n)$ cells on each work tape.
\begin{itemize}
    \item Again, the input-tape cells do not count.
    \item It is assumed that $N$ uses at least the cell under the initial position of the window.
        So $S(n)$ is at least constant function 1.
\end{itemize}
A NTM $N$ of nondet. space complexity $S(n)$ can decide $w \in ? L(N)$ on $\leq S(|w|)$ space.
\\\\
A language $L$ has nondet. space complexity $S(n)$ if there is a NTM $N$ of nondet. space
complexity $S(n)$ such that $L=L(N)$. The class of all languages is\\
\centerline{NSPACE($S(n)$)=$\{L\mid L$ is a language $\wedge L$ is of nondet. space
complexity $S(n)\}$}
{\footnotesize Informally, NSPACE($S(n)$) has all $L$s for which $w\in ?L$ can be
nondeterministically solved on $\leq S(|w|)$ space.}\\
This can be extended to a decision problem D an its language L(D) (p.284).

\subsubsection{Summary of complexity classes}
In terms of formal languages:
\begin{itemize}
    \item[] DTIME($T(n)$) $= \{L \mid L$ is a language $\wedge$ $L$ has time complexity $T(n)\}$
    \item[] DSPACE($S(n)$) $= \{L \mid L$ is a language $\wedge$ $L$ has space complexity $S(n)\}$
    \item[] NTIME($T(n)$) $= \{L \mid L$ is a language $\wedge$ $L$ has nondet. time complexity $T(n)\}$
    \item[] NSPACE($S(n)$) $= \{L \mid L$ is a language $\wedge$ $L$ has nondet. space complexity $S(n)\}$
\end{itemize}
In terms of decision problems:
\begin{itemize}
    \item[] DTIME($T(n)$)  $= \{D \mid D$ is a decision problem $\wedge$ $L(D)$ has time complexity $T(n)\}$
    \item[] DSPACE($S(n)$) $= \{D \mid D$ is a decision problem $\wedge$ $L(D)$ has space complexity $S(n)\}$
    \item[] NTIME($T(n)$)  $= \{D \mid D$ is a decision problem $\wedge$ $L(D)$ has nondet. time complexity $T(n)\}$
    \item[] NSPACE($S(n)$) $= \{D \mid D$ is a decision problem $\wedge$ $L(D)$ has nondet. space complexity $S(n)\}$
\end{itemize}
Informally:
\begin{itemize}
    \item[] DTIME($T(n)$)  = \{decision problems solvable deterministically in time $T(n)$\}
    \item[] DSPACE($S(n)$) = \{decision problems solvable deterministically on space $S(n)$\}
    \item[] NTIME($T(n)$)  = \{decision problems solvable nondeterministically in time $T(n)$\}
    \item[] NSPACE($S(n)$) = \{decision problems solvable nondeterministically on space $S(n)$\}
\end{itemize}

\subsection{Tape compression, linear speedup, and reductions in the number of tapes}
\subsubsection{Tape compression}
We can encode several symbols to one symbol from a larger alphabet.
\\\\
For any $c > 0$ is DSPACE($S(n)$) = DSPACE($cS(n)$) and NSPACE($S(n)$) = NSPACE($cS(n)$)

\subsubsection{Linear speedup}
We can group several steps into a new, larger step.
\\\\
Two conditions need to be fulfilled:
\begin{itemize}
    \item TM must have at least 2 tapes (e.e. $k>1$),
    \item $inf_{n\rightarrow \infty}T(n)/n = \infty$ must hold
    \item[] \emph{Informally:} $T(n)$ must grow faster than $n$ (at least slightly). Only
        then will there remain, after reading the input, some time available for computation.
\end{itemize}
If $inf_{n\rightarrow \infty}T(n)/n = \infty$, then for any $c>0$\\
DTIME($T(n)$) = DTIME($cT(n)$) and NTIME($T(n)$) = NTIME($cT(n)$)

\subsubsection{Summary}
Under certain conditions:
\begin{itemize}
    \item[] DTIME($T(n)$) = DTIME($cT(n)$) 
    \item[] NTIME($T(n)$) = NTIME($cT(n)$)
    \item[] DSPACE($S(n)$) = DSPACE($cS(n)$)
    \item[] NSPACE($S(n)$) = NSPACE($cS(n)$) 
\end{itemize}
Instead of saying that a decision problem $D$ is in $DTIME(n^2)$, we can say that $D$
has det. time complexity of the order $O(n^2)$.

\subsubsection{Reductions in the number of tapes}
\begin{itemize}
    \item[] If $L\in DTIME(T(n))$, then $L$ is accepted in time $O(T^2(n))$         by a 1-tape TM.
    \item[] If $L\in NTIME(T(n))$, then $L$ is accepted in time $O(T^2(n))$         by a 1-tape NTM.
    \item[] If $L\in DTIME(T(n))$, then $L$ is accepted in time $O(T(n)logT(n))$    by a 2-tape TM.
    \item[] If $L\in NTIME(T(n))$, then $L$ is accepted in time $O(T(n)logT(n))$    by a 2-tape NTM.
\end{itemize}
If $L$ is accepted by a $k$-work tape TM of space complexity $S(n)$, then $L$ is accepted
by a 1-work-tape TM of space complexity $S(n)$.

\subsection{Relations between DTIME, DSPACE, NTIME, NSPACE}
\subsubsection{Relations between different complexity classes}
\begin{itemize}
    \item $DTIME(T(n)) \subseteq DSPACE(T(n))$\\
        {\footnotesize i.e. What can be solved in time $O(T(n))$, can also be solved on space $O(T(n))$}
    \item $L \in$DSPACE$(S(n)) \wedge S(n) \geq log_2n \Rightarrow \exists c: L \in $DTIME$(c^{S(n)})$\\
        {\footnotesize i.e. What can be solved on space $O(S(n))$, can also be solved in
         (at most) time $O(c^{S(n)})$. (Here c depends on $L$.)}
    \item $L \in $NTIME $(T(n)) \Rightarrow \exists c:L \in $DTIME($c^{T(n)}$)\\
        {\footnotesize i.e. What can be solved nondeterministically in time $O(T(n))$, can
        be solved deterministically in (at most) time $O(c^{T(n)})$.\\
        Consequently, the substitution of a nondeterministic algorithm with a deterministic
        one causes at most exponential increase in the time required to solve a problem.}
    \item NSPACE($S(n)$) $\subseteq$ DSPACE($S^2(n)$), if $S(n) \geq log_2n \wedge S(n)$ is
        ``well-behaved''
        {\footnotesize i.e. What can be solved nondeterministically on space $O(S(n))$,
        can also be solved deterministically on space $O(S^2(n))$.\\
        Consequently, the substitution of a nondeterministic algorithm with a
        deterministic one causes at most quadratic increase in the space required to
        solve a problem.}
\end{itemize}

\subsubsection{``Well-behaved'' complexity}
A function $S(n)$ is space constructible if there is a TM $M$ of space complexity $S(n)$
such that for each $n$, there exists an input of length $n$ on which $M$ uses exactly $S(n)$
tape cells. If for each $n,M$ uses exactly $S(n)$ cells on any input of length $n$, then we
say that $S(n)$ is fully space constructible.
\\\\
A function $T(n)$ is time constructible if there is a TM $M$ of time complexity $T(n)$, such
that for each $n$, there exista an input of length $n$, on which $M$ makes exactly $T(n)$
moves. If for all $n,M$ makes exactly $T(n)$ moves on any input of length $n$, then we say
that $T(n)$ is fully time constructible.
\\\\
{\footnotesize The sets of space and time constructible functions are very rich and include all common
functions. Moreover, most common functions are also fully space and fully time constructible.}

\subsection{The classes P, NP, PSPACE, NPSPACE}
The requirements of a computation for a computational resource (time, space)
are considered to be reasonable if they are bounded by some polynomial. 
\subsubsection{P, NP, PSPACE, NPSPACE}
Define the complexity classes P, NP, PSPACE and NPSPACE as:
\begin{itemize}
    \item P$=\bigcup_{i \geq 1}$DTIME($n^i$)\\
        {\footnotesize is the class of all decision problems deterministically solvable in polynomial time}
    \item NP$=\bigcup_{i \geq 1}$NTIME($n^i$)\\
        {\footnotesize is the class of all decision problems nondeterministically solvable in polynomial time}
    \item PSPACE$=\bigcup_{i \geq 1}$DSPACE($n^i$)\\
        {\footnotesize is the class of all decision problems deterministically solvable on polynomial space}
    \item NPSPACE$=\bigcup_{i \geq 1}$NSPACE($n^i$)\\
        {\footnotesize is the class of all decision problems nondeterministically solvable on polynomial space}
\end{itemize}

\subsubsection{The basic relations (between P, NP, PSPACE, NPSPACE)}
The following inclusions hold: P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ NPSPACE
\begin{itemize}
    \item (P $\subseteq$ NP) {\footnotesize Every deterministic TM of polynomial time
    complexity can be viewed as a (trivial) nondeterministic TM of the same time complexity.}
    \item (NP $\subseteq$ PSPACE) {\footnotesize If $L\in$NP then $\exists k$ such that
    $L\in$NTIME($n^k$). \\So $L\in$ NSPACE($n^k$), and hence (by Savitch) $L\in$DSPACE($n^{2k}$).
    Therefore $L \in$PSPACE.}
    \item (PSPACE = NPSPACE) {\footnotesize Trivially, PSPACE $\subseteq$ NPSPACE. The
    opposite direction: \\NPSPACE = $\bigcup$ NSPACE($n^i$) $\subseteq$ (by Savitch)
    $\subseteq$ DSPACE($n^j$) $\subseteq$ PSPACE.}
\end{itemize}

\subsection{The question P $=^?$ NP}
We have just proved PSPACE = NPSPACE\\
$\Rightarrow$ When space complexity is polynomial, nondeterminism adds nothing to the
computational power.
\\\\
We know P$\subseteq$NP, but is P=NP?\\
$\Rightarrow$ Is it true that when time complexity is polynomial,
nondeterminism adds nothing to the computational power?
\\\\
We try to prove that P$\subseteq$NP\\
using ''the most difficult'' problem in NP.

\subsubsection{Problem reductions}
Suppose that there existed a $D^* \in$ NP, such that we could ``easily'' reduce every
$D\in$ NP to $D^*$ in the following sense:
\begin{itemize}
    \item there would exist a function $r:D\rightarrow D^*$
    \item that could ``easily'' transform any instance $d\in D$ into an instance $r(d)\in D^*$
    \item such that the solution $s$ to $r(d)$ could be ``easily'' transformed into the solution ``?'' to $d$.
    \item[] Then, for every problem $D$, solving could be ``easily'' replaced by solving of $D^*$
\end{itemize}
If this were possible, then every $D$ could be viewed as ``at most as difficult as'' $D^*$
In other words, $D^*$ could be viewed as the ``most difficult'' problem in NP.

\subsubsection{Polynomial-time reductions}
First we define ``easily’’ = ``in deterministic polynomial time’’
\\\\
A problem $D \in$NP is polynomial-time reducible to a problem $D'$, i.e. $D \leq^p D'$,
if there is a deterministic TM $M$ of polynomial time complexity that, for any $d\in D$,
returns a $d'\in D'$, such that $d$ is positive $\Leftrightarrow$ $d'$ is positive.\\
The relation $\leq^p$ is called polynomial-time reduction.\\
{\footnotesize \emph{Intuitivelly:} $M$ replaces, in polynomial time, $d\in D$ with $d'\in D'$
that has the same answer as $d$. ($M$ takes $\langle d \rangle$ and in poly. time
returns a word $M(\langle d \rangle)$, where
$\langle d \rangle \in L(D) \Leftrightarrow M(\langle d \rangle)\in L(D')$)}

\subsection{NP-complete and NP-hard problems}
We have seen that the ``most difficult’’ problem in NP could be defined as the
problem $D^*$ that has the following property: 
\begin{itemize}
    \item $D^* \in$ NP
    \item $D\leq^p D^*$, for $D \in$ NP
\end{itemize}
A problem $D^*$ is said to be NP-hard if
\begin{itemize}
    \item $D \leq^p D^*$, for every $D\in$ NP.
\end{itemize}
 A problem $D^*$ is said to be NP-complete if
\begin{itemize}
    \item $D^* \in$ NP and
    \item $D \leq^p D^*$, for every $D \in$ NP
\end{itemize}
Hence, $D^*$ is NP-complete if $D^*$ is in NP and $D^*$ is NP-hard.

\subsubsection{An NP-complete problem: SAT}
A Boolean expression is inductively defined as follows:
\begin{itemize}
    \item Boolean variables $x_1,x_2,\dots$ are Boolean expressions
    \item If $E,F$ are Boolean expressions then so are $\neg E$, $E\vee F$, and $E \wedge F$.
\end{itemize}
A Boolean expression E is satisfiable if the variables of E can be
consistently replaced with values TRUE/FALSE so that E evaluates to TRUE.
\\\\
The problem SAT = ``Is a Boolean expression $E$ satisfiable?’’ (the Satisfiability Problem)
\\\\
SAT is NP-complete

\subsubsection{Proving NP-completeness of problems}
Let $D\leq^p D'$. Then
\begin{itemize}
    \item $D' \in P \Rightarrow D\in P$
    \item $D' \in$ NP $\Rightarrow D\in$ NP
\end{itemize}
{\footnotesize So any problem $D$ that can be $\leq^p$-reduced to a problem in P (or in NP),
is also in P (or NP).}
\\\\
The relation $\leq^p$ is transitive. $D\leq^p D' \wedge D' \leq^p D'' \Rightarrow D \leq^p D''$
\\\\
The following holds:
\begin{itemize}
    \item $D^*$ is NP-hard $\wedge$ $D^* \leq^p D^\star \Rightarrow D^\star$ is NP-hard
    \item $D^*$ is NP-complete $\wedge$ $D^* \leq^p D^\star \wedge D^\star \in$
    NP $\Rightarrow D^\star$ is NP-complete
\end{itemize}

\subsubsection{Summary}
If P $\neq$ NP, then NP contains:
\begin{itemize}
    \item NPC - the class of all NP-complete problems
    \item NPI - the class of all NP-intermediate problems\\
        {\footnotesize (Ladner): if P $\neq$ NP, then there exists a problem in NP that is neither in P
        nor in NPC}
    \item P
\end{itemize}
If P $\neq$ NP, then no problem in NPC or NPI has polynomial time complexity.
\end{document}