This question already has an answer here:

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 Mathieson Dec 14 '14 at 2:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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.