Problem 1: \\

Explain why the following is not a description of a legitimate Turing Machine.

$ M_{bad} = $ ``The input is a polynomial $p$ over variables $x_1,...,x_k$.
\begin{enumerate}[leftmargin=2cm,topsep=0pt]
    \item Try all possible settings of $x_1,...,x_k$ to integer values
    \item Evaluate $p$ on all of these settings.
    \item If any of these settings evaluates to 0, accept; otherwise reject.''
\end{enumerate} 

Problem 2: \\

\begin{enumerate}
\item Consider a variant Turing machine in which the head of the reader can either stay put or move to the right.
\begin{enumerate}
    \item Describe why this is not equivalent to a normal Turing machine.
    \item What class of languages does this machine recognize? Briefly describe why.
\end{enumerate}
    \item Consider a variant Turing machine that has three independent heads. At each step, the Turing machine can choose which of the three heads to move. Only one head can move in each step. Each head is still not allowed to move left. Prove that such a machine can simulate a normal Turing machine.
\end{enumerate}

Problem 3: \\

Given an arbitrary Turing decidable language $L'$, consider the following language
$$
L = \{w | \exists w' \in L' \textrm{ such that $w$ is a substring of } w'\}
$$
\begin{enumerate}
    \item Prove that $L$ is Turing recognizable.
    \item Without providing rigorous proof, give an intuitive argument for whether you believe $L$ to be decidable.
    \item Suggest a property that, if $L'$ were to have it, would guarantee $L$ to be decidable. Motivate your answer.
\end{enumerate}