\documentclass{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\e}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}
\newcommand{\yieldstar}{\stackrel{*}{\Rightarrow}}
\newcommand{\yields}{\Rightarrow}
\newcommand{\blank}{\text{\textvisiblespace}}
\newcommand{\rep}[1]{\langle #1 \rangle}
\newcommand{\TIME}{\text{\textsc{Time}}}
\newcommand{\Ozgur}{\text{\textsc{Ozgur}}}
\newcommand{\tab}{\hspace{30pt}}

\newtheorem{objective}{Objective}

\begin{document}
  
  \begin{minipage}{\textwidth}
    CSE3502 - Theory of Computation \hfill \today\\
    \textbf{Due: Before class on April 15, 2014}\\
    \\
    \centering{Homework 7} \hfill
  \end{minipage}

  \input{hw_survey}

  \section{Time Complexity Classes} % (fold)

    \question{1.1}
    The book asserts that every language that can be decided in time $o(n\log n)$ time is regular.
    Use this fact to prove that $\TIME(n\log(\log n))\setminus \TIME(n) = \emptyset$.
  
  % section time_complexity_classes (end)

  \section{The Ozgur Machine does not exist!} % (fold)

    We saw in class (\emph{and its also in the book}) that the acceptance problem for Turing machines is undecidable.
    That is, the language
    \[
      A_{TM} = \{\rep{M,w} \mid M\text{ is a TM and } w\in L(M)\}
    \]
    is undecidable.
    We will use this theorem to show that there cannot exist a Turing machine that can reliably decide whether or not you submitted correct answers to some of the problems from homework 5.
    Recall that the language $A$ was defined as
    \[
      A = \{(0\cup 1)^a(1\cup 2)^b(2\cup 3)^c \mid a\ge b\}.
    \]
    In homework 5, you were asked to give a Turing machine to recognize $A$.
    Consider the language of correct answers:
    \[
      Z = \{\rep{M} \mid M\text{ is a TM and } L(M) = A\}.
    \]
    We will show that $Z$ is undecidable.
    At least one answer $T_A$ was given in the solutions that decides $A$.
    
    Suppose for contradiction that there exists a Turing machine $\Ozgur$ that can decide $Z$.
    Then, we will create a new Turing machine $T$ that works as follows.
    
    \begin{align*}
      T = &\text{ On input $\rep{M,w}$}\\
      & \text{1. Write the description of a TM R that works as follows}\\
      & \tab R = \text{On input $x$}\\
      & \tab\tab \text{Run $T_A$ on $x$.}\\
      & \tab\tab \text{If $T_A$ accepts $x$ then accept.}\\
      & \tab\tab \text{If $T_A$ rejects $x$ then run $M$ on input $w$ and accept if $M$ does}\\
      & \text{2. Run $\Ozgur$ on input $\rep{R}$, accept if $\Ozgur$ rejects and reject if $\Ozgur$ accepts.}
    \end{align*}
  
    Note that the machine $R$ has the machine $M$ and the string $w$ ``hard-coded'' into it.
    These are not part of the input to $R$.
    
    \question{2.1}
    Is $R$ necessarily a decider?  Why or why not?  Recall that a decider always terminates.
    
    \question{2.2}
    Is $T$ a decider?  Why or why not?
    
    \question{2.3}
    What is $L(R)$ in terms of $w$, $A$, $\Sigma$, and $L(M)$?
    
    \question{2.4}
    Prove that $T$ decides $A_{TM}$.
    
    \vspace{10pt}
    Finally, after proving in $2.4$ that $T$ decides $A_{TM}$, we can conclude that $\Ozgur$ cannot exist, because there cannot be a TM that decides $A_{TM}$.
  
  % section the_ozgur_machine_does_not_exist_ (end)

  \section{Big-O and little-o} % (fold)

    Let $f$ and $g$ be functions such that $f(n) = O(n^2)$ and $g(n) = O(n)$.

    \question{3.1} Let $h_1(n) = f(n) + g(n)$.
    Is it necessarily true that $h_1(n) = O(n^2)$?  Give a proof.

    \question{3.2} Let $h_2(n) = f(n)g(n)$.
    Is it necessarily true that $h_2(n) = o(n^3\log n)$?  Give a proof.

    \question{3.3} Let $h_3(n) = \frac{f(n)}{g(n)}$.
    Is it necessarily true that $h_3(n) = O(n)$?  Give a proof.
  
    \question{3.4} Let $h_4(n) = 2^{O(\log(\log n))}$.
    Is it necessarily true that $h_4(n) = O(\log n)$?  Give a proof.
  
  % section big_o (end)

\end{document}