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.

  • $\begingroup$ See our reference questions. $\endgroup$ – Raphael Dec 12 '14 at 8:02
  • $\begingroup$ 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? $\endgroup$ – 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$.

  • $\begingroup$ 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? $\endgroup$ – tdark Dec 12 '14 at 7:48
  • $\begingroup$ @tdark Thanks, my answer indeed didn't make sense. Hopefully now it should be clearer. $\endgroup$ – Yuval Filmus Dec 12 '14 at 7:51
  • $\begingroup$ 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. $\endgroup$ – tdark Dec 12 '14 at 8:06
  • $\begingroup$ Keep thinking, then. $\endgroup$ – Yuval Filmus Dec 12 '14 at 8:09
  • $\begingroup$ 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)$. $\endgroup$ – tdark Dec 12 '14 at 8:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.