I recently had a test in introduction to computability and I got the following question wrong.

The question

Input: A classical Turing machine $M$ with a 2-dimensional tape.

output: Does there exists a Turing machine $H$ that runs in polynomial time such that for any input $x$, if $M$ halts then $M(x)=H(x)$

Which of the following is correct?

(a) This decision problem is trivial.

(b) This decision problem is decidable, but not trivial.

(c) This problem is undecidable, according to Rice's theorem.

(d) This problem is undecidable, but Rice's theorem is not applicable.

My answer

I chose option (d) because the polynomial time requirement is not semantic, but the professor marked option (c) as the correct answer. Could anyone explain this?


Rice's theorem and the terms "trivial" and "semantic" are explained here.

  • 1
    $\begingroup$ Being in P is a property of the language. $\endgroup$ Sep 4, 2014 at 21:28

1 Answer 1


As you correctly mention, polynomial running time is not a semantic property.

However, the property required here is not polynomial running time (of $M$), but functional equivalence to a TM with polynomial running time (on those inputs where $M$ halts). It is of no importance, how long $M$ runs on those inputs. This is a semantic property, since every other TM $M'$, that computes the same function as $M$ will have the property as well: $M'$ halts on exactly the same inputs $x$ as $M$ and on these inputs $M'(x) = M(x) = H(x)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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