I am trying to solve the following problem:For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if $M_k(x)$$\downarrow$ (halts), and $\infty$ if $M_k(x)$$\uparrow$ (does not halt)$\}$Prove that the function $T$: $\mathbb{N}$ $\rightarrow$ $\mathbb{N}$ defined by$T(n)$ = max$\{$$time_k(x)$ | $0$ $\leq$ $k$ $\leq$ $n$, $x$ $\in$ $\{$0,1$\}$$^\ast$, and $M_k(x)$$\downarrow$ (halts)$\}$is uncomputable.So far, I have begun my proof by assuming that $T$ is computable. Thus, there exists a Turing machine $M$ such that for all $n$$\in$$\mathbb{N}$, $M$ produces $T(n)$ on its tape. Thus, we must show that we can decide the Halting Problem if $T$ is computable, which in turn lets us know that $T$ is uncomputable since the Halting Problem is uncomputable.I do not know where to go from there however. Any help would be greatly appreciated. Thanks in advance.
Proving a function is uncomputable
computability;reductions;undecidability;halting problem
Hint: Given $T(n)$, any $k \leq n$, and an input $x$, it is enough to run $M_k$ for $T(n)$ steps in order to decide whether it halts on $x$.