I recently had a test in introduction to computability and I got the following question wrong.
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?
Rice's theorem and the terms "trivial" and "semantic" are explained here.