# How is Rice's theorem applicable to this decision problem?

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.

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?

## Background

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

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

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)$.