# Decidablity of time complexity

Let $$t:\mathbb{N}\rightarrow\mathbb{N}$$ be a time constructible function with $$t(n)\geq n + 100$$. Show that there is no TM $$T$$ that given the gödel number of another TM $$M$$, decides wether or not M is time bounded by $$t$$. Can someone help me with this? I have no clue

• Try something similar to the proof of the halting problem. – dkaeae Jan 17 '19 at 16:37
• @dkaeae Construct a TM $T'$ using the universal TM that works as follows: Given the gödel number $g$ of a TM $M$, $T'$ simulates $T$ on $g$. If $T$ returns "true" diverge, else do nothing. Now what happens if run $T'$ on it's own gödel number? does this work? – Yamahari Jan 17 '19 at 16:40
• Yes, but there are two details you must be careful about: 1. instead of "do nothing" you want the machine to actually halt; 2. you have to somehow argue that, if $T'$ halts, then it takes less than $t(n)$ steps to do so. – dkaeae Jan 18 '19 at 7:21
• Yes instead of simulating T on g entirely I simulate it for t(|g|) steps therefor if T doesn't halt during this time period, T' halts with t(|g|) steps another contradiction – Yamahari Jan 18 '19 at 7:43
• @Yamahari write an answer? – John L. Jan 28 '19 at 12:31