\begin{frame}{Kleene Start} \begin{goal}{Theorem} If $L$ is a recursively enumerable language, then so is \begin{talign} L^* \end{talign} \end{goal} \pause \begin{block}{} Let $M$ be a Turing machine such that $L(M) = L$. \pause\medskip A partitioning of a word $w \ne \lambda$ are non-empty words $(w_1,\ldots,w_n)$ for some $n \le |w|$ such that $w = w_1 w_2 \cdots w_n$. \pause\medskip The partitioning is good if $M$ accepts all words $w_1,\ldots,w_n$. \pause\medskip Create a Turing machine $N$ that \begin{itemize} \item computes all partitionings of the input word $w \ne \lambda$ \item checks \emph{all partitionings in parallel} whether they are good \item accepts the input $w$ as soon as a good partitioning is found \end{itemize} Then $L(N) = L^*$. \end{block} \end{frame}