$(1)$ Please design a Turing machine $($in the style in Section $9\mathrm{.}1).$ Specifi$-$

cally, you need to define the $$ function for your Turing machine. The input

is $n,$ which is represented by $n$ consecutive $1\text{'}$s$.$ The output should be fib$(n)$

and fib$(n+1)$ which are represented in unary notation.

Hint. The computation sequence should be $0=>{?}^{**}101=>{?}^{**}102=>{?}^{**}203=>{?}^{**}$

$305=>{?}^{**}508=>{?}^{**}8013$dots. Note that we will use unary representations for

natual numbers.