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

  • 1
    $\begingroup$ Try something similar to the proof of the halting problem. $\endgroup$ – dkaeae Jan 17 '19 at 16:37
  • $\begingroup$ @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? $\endgroup$ – Yamahari Jan 17 '19 at 16:40
  • $\begingroup$ 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. $\endgroup$ – dkaeae Jan 18 '19 at 7:21
  • $\begingroup$ 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 $\endgroup$ – Yamahari Jan 18 '19 at 7:43
  • $\begingroup$ @Yamahari write an answer? $\endgroup$ – John L. Jan 28 '19 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.