\documentclass{scrartcl}
\usepackage[margin=1in, left=0.7in, right=0.7in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{subcaption}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD11} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{11 janvier 2018}
\newcommand{\DP}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\coNP}{\mbox{co-}\mathcal{NP}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\tr}[1]{\xrightarrow{#1}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\newcommand{\code}[1]{{\langle}{#1}{\rangle}}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\newcommand*\xor{\mathbin{\oplus}}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
  question/type = exam,
  %  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
solution/print = true
}
\newtheorem{defi}{Definition}
\newtheorem{lem}{Lemme}
\newcommand\myeq{\stackrel{\mathclap{\codealfont\mbox{def}}}{=}}
\setlength{\parindent}{0em}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD11 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{A BPP problem}

\subsection{Definitions}

\begin{defi}
  We recall that the BPP class can be defined as the class of
  languages such that there exists a polynomial $P$ and a language $A$
  recognized in polynomial time by a Turing Machine such that:
  \[
  x \in L \Rightarrow \underset{\varepsilon\in \{0,1\}^{p(|x|)}}{\mathbb{P}}\bigg((x,\varepsilon)\in A\bigg) \ge \frac{2}{3}
  \hspace{10em}
 x \notin L \Rightarrow \underset{\varepsilon\in \{0,1\}^{p(|x|)}}{\mathbb{P}}\bigg((x,\varepsilon)\in A\bigg) \le \frac{1}{3} 
  \]  
\end{defi}

\begin{defi}
We recall that the \emph{degree of a monomial} $X_1^{d_1} \dots
X_n^{d_n}$ is $\sum_j d_j$ and that the \emph{degree of a polynomial}
is the maximum of the degree of the monomial composing the
polynomial. For instance $XXXXY + XYZ + Z + ZY $ has degree 5 (since
$XXXXY$ has degree 5).
\end{defi}

\subsection{Polynomial in general form}

\begin{defi}
  A polynomial can always be written as the sum of monomials. A
  polynomial is in \emph{general form} when it is given as a simple
  variable (i.e. $X_i$) or as sum, difference or product of
  polynomials in general form. For instance $((X_1+X_2)\times
  (X_1-X_2) + X_1)\times X_1$.
\end{defi}

We voluntarily ignore the details of the encoding of polynomials in
general form. We will simply suppose that it is non-ambiguous, that
the encoding size for the $n$-th variable on the input takes size
$O(ln(n))$ and that it takes $O(1)+n_1+n_2$ in size in the input for
the sum or product of two polynomials of size $n_1$ and $n_2$. It is
as if we use the string notation composed of (, ), +, -, *, X, and the
decimal digits to encode integers for the variables.

  
\begin{question}
Show that the function transforming a polynomial given in general form
into a polynomial as sum of monomials cannot be computed in polynomial
time.
\end{question}

\begin{question}
  What is the complexity of the function testing the equality of two
  polynomials given in general form by using the expansion into a sum
  of monomials?
\end{question}

\subsection{Schwartz-Zippel lemma}

\begin{lem}
  Let $P\in\mathbb{Z}[X_1,\dots, X_n]$ of degree $d$ and let $S$ be a
  finite subset of $\mathbb{Z}$. If $x_1, \dots, x_n$ are chosen
  uniformly from $S$ then $\mathbb{P}\Big(P(x_1,\dots,x_n)=0\Big)\leq
  \dfrac{d}{|S|}$
\end{lem}

\begin{question}
Demonstrate or admit this lemma.
\end{question}

\begin{question}
  Deduce a BPP algorithm for testing the equality of two polynomials
  in general form.
\end{question}

\section{Rice theorem}

\begin{defi}
  A \emph{useless} state of a Turing machine is a state that is never
  visited during a computation.
\end{defi}

\begin{question}
  Show that deciding whether a Turing machine has useless states is
  undecidable.
\end{question}

\begin{question}
  Why cannot you simply apply Rice's theorem?
\end{question}

\section{Busy beavers}

The \emph{busy beavers} problem was introduced by Radó with the goal
of defining a simple uncomputable function. The model of Turing
Machines is the following:
\begin{itemize}
\item the machine is deterministic;
\item the tape is infinite in both direction;
\item the tape alphabet is $\{0,1\}$;
\item the machine possesses a unique ``end'' state with no outgoing
  transitions;
\item the tape is initially filled with $0$ (we do not distinguish
  between $0$ and the initial tape symbol).
\end{itemize}

The busy beaver function $\Sigma(n)$ is defined as the maximum number
of $1$ written on the tape (not necessarily consecutively) by a
machine of $n+1$ states ($n$ states plus the final state) before the
machine enters into a final state (the machine has to halt)


\begin{question}
Justify the existence of $\Sigma(n)$ for all $n\in\mathbb{N}$.
\end{question}

\begin{question}
What are $\Sigma(0)$? $\Sigma(1)$? $\Sigma(2)$? (or just show that
$\Sigma(2)\geq 4$)
\end{question}

\begin{question}
Show that $\Sigma$ is strictly increasing.
\end{question}

We say that a function $f$ is computable when there exists a Turing
Machine $M$ such that $M$ prints $f(n)$ consecutive $1$ after reading
$n$ consecutive $1$ on the input.

\begin{question}
Show that the function $\Sigma$ increase is strictly faster that any
computable function $f$ (i.e. $f(n)=o(\Sigma(n))$).   
\end{question}

\end{document}


