Problem Detail: 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.
Asked By : tdark
Answered By : Yuval Filmus
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35183 Ask a Question Download Related Notes/Documents
