# Proving a function is uncomputable [duplicate]

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.

## marked as duplicate by D.W.♦, David Richerby, Juho, Rick Decker, Luke MathiesonDec 14 '14 at 2:01

• Is $T(n)$ well defined? Assume that $M_1$ is a TM that on input $x$ runs for $|x|$ and then halts. Then, for any $n\ge1$, $T(n)=\max\{1,2,3, ...,\}$ which is not well defined. Could you clarify? – Ran G. Dec 12 '14 at 18:22
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$.
• Let me see if I understand you correctly, or rather the function correctly. $n$ in this case is an upper bound. And $m$ is $k$ in this instance. So when we enter the $time$ function, we will be able to determine whether $M_m(x)$ halts or loops based on whether $time_m(x)$ returns a value or loops forever, which means we would be able to solve the halting problem. Am I on the right track? – tdark Dec 12 '14 at 7:48
• If I'm thinking about this correctly, then no, it would not be enough to run $M_k$ $T(n)$ steps in order to decide whether it halts on $x$ because we have no way of knowing whether $M_k$ halts on $x$ in $T(n)$ steps. – tdark Dec 12 '14 at 8:06
• Oh wait, since $T(n)$ explicitly states that $M_k(x)$ must halt, that means that we would only be using the first condition of the $time$ function, correct? Thus, it would be enough to run $M_k(x)$ $T(n)$ steps in order to decide whether it halts on $x$, otherwise $x$ would be rejected by $T(n)$. – tdark Dec 12 '14 at 8:20