Create single$-$tape Turing machines $($draw the diagrams or write the transition functions$)$ that compute the following functions. The machines should always halt with the head position as specified. At the start of computation, the head is on the first symbol of the input string, and at the end, it should return to the first symbol of the output string $($the tape only contains the output, and the rest are blank$).$

$1.$ The Max$($x$,$ y$)$ function with x and y being binary numbers with no leading zeros, and the input string w$=$x#y$,$ where $|$x$|$ and $|$y$|>0.$

Example $1$:

Input: $1101$#$1010$

Output: $1101$

Example $2$:

Input: $1001$#$1111$

Output: $1111$

$2.$ The Fib$($n$)$ function with the input string w$=1^$n and the output $1^$Fib$($n$),$ where

Fib$(1)=1,$ Fib$(2)=2,$ and Fib$($n$)=$ Fib$($n$-1)+$ Fib$($n$-2)$ for n $>2.$

Example $1$:

Input: $111($which means n $=3)$

Output: $11111($which is $5,$ the $3$rd Fibonacci number$)$

Example $2$:

Input: $11111($which means n $=5)$

Output: $11111111111($which is $13,$ the $5$th Fibonacci number$)$