I don't know exactly how to solve the exercise below.
Show that the multiplication lies in $\text{FL}$.
Hint: A useful approach to a solution is to split the exercise into two parts and to explain that each function lies in $\text{FL}$. The standard multiplication scheme can be used as an intermediate step. Example:
$\begin{align} 1001 \cdot{} 1100 & = \\ 1001000\\ + \ \ \ 100100\\ + \ \ \ \ \ \ \ \ \ \ \ \ 0\\ + \ \ \ \ \ \ \ \ \ \ \ \ 0\\ \end{align}$
Other useful approaches are certainly also accepted.
Useful definitions from our lecture notes:
Let $f : \Sigma^* \to \Sigma^*$ be a function, let $t : \mathbb N \to \mathbb N$ be a time bound and let $s : \mathbb N \to \mathbb N$ be a memory space bound.
$\bullet$ It is $f \in \text{FDTIME}(t),$ if there exists a DTM $M$ with an output tape, calculating $f$ and for which $T_M \in O(t)$ holds.
$\bullet$ It is $A \in \text{FDSPACE}(s),$ if there exists an offline DTM $M$, calculating $f$ and for which $S_M \in O(s)$ holds. The fields being written on the output band are not considered for the amount of memory space.
$\text{FP}=\bigcup_{k \in \mathbb N} \text{FDTIME}(n^k), \text{FL}=\text{FDSPACE}(\log n)$
I think the hint wants me to find two functions (one for the multiplication and one for the addition), but I don't see how to find two functions that do the calculation of the example in the appropriate way. Can somebody help me, please?
