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.

  • 2
    $\begingroup$ Homework/class questions are unfortunately off-topic on this site. $\endgroup$ – Lev Reyzin Sep 4 '14 at 17:30
  • 1
    $\begingroup$ Being in P is a property of the language. $\endgroup$ – Sasho Nikolov Sep 4 '14 at 21:28
  • $\begingroup$ We don't auto-migrate, but only when the poster asks. $\endgroup$ – Lev Reyzin Sep 5 '14 at 21:43
  • $\begingroup$ OK, sorry about this. I wasn't aware of this policy. How can I migrate to the CS stackexchange? $\endgroup$ – YetAnotherMathStudent Sep 5 '14 at 23:05

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, privacy policy and cookie policy

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