$($Encodings and Runtime$)$ The runtime of an algorithm $($Turing machine$)$ is always measured as

a function if its input length. The goal of this problem is to help you understand what that means

and why it can be subtle.

$($a$)$ Prove that there is no polynomial$-$time algorithm that takes as input a natural number $k$

$($written in binary$)$ and outputs $($i$.$e$.,$ writes to its tape$)$ the number $k!($again$,$ written in

binary$).$

Hint: Show that the expected output for this problem is so long that it is impossible for a

poly$-$time algorithm to even write it down.

$($b$)$ Give a high$-$level description of a polynomial$-$time algorithm that takes as input a natural

number $k($written in unary, i$.$e$.,$ the string ubrace$(11$dots$11$ubrace${)}_{k\text{t}\text{i}\text{m}\text{e}\text{s}})$ and outputs the number $k!($written in

binary$).$ Explain why your algorithm is correct and why it runs in polynomial time.

Hint: You can use without proof the fact that Turing machines can perform basic arithmetic

operations on binary numbers, like addition and multiplication, in polynomial time.