1
$\begingroup$

Suppose $P_1$ and $P_2$ are nontrivial semantic properties of Turing Machines, and suppose that $P_1\wedge P_2$ is nontrivial given $P_1$. Can one claim that $P_1\wedge P_2$ is undecidable given an oracle for $P_1$?

A specific example: Let $P_2$ be a nontrivial property of total functions. Is it undecidable when inputs are restricted to machines which are known to compute total functions?

The usual proof of Rice Theorem, via reduction from the Halting Problem, does not seem to work in this case.

$\endgroup$
1
$\begingroup$

You can prove your idea via the usual recursion theorem proof of Rice's theorem.

proof:

Suppose that $M_{yes}$ is a machine with both property $P_1$ and $P_2$ and that $M_{no}$ is a machine with property $P_1$ but without property $P_2$. Such machines must exist by the nontrivial assumption.

Then suppose there exists a decider $D$ which accepts any input $<X>$ such that machine $X$ satisfies both property $P_1$ and $P_2$, rejects any input $<X>$ such that machine $X$ satisfies property $P_1$ but not $P_2$, and has any behavior on all other inputs.

Consider the following machine:

$M =$ on input $w$:

  1. Obtain the description $<M>$ via the recursion theorem.
  2. Run $D$ on $<M>$
  3. If $D$ accepts $<M>$, simulate $M_{no}$ on $w$ and output the same answer
  4. If $D$ rejects $<M>$, simulate $M_{yes}$ on $w$ and output the same answer

This language $L(M)$ of this machine is either $L(M_{yes})$ or $L(M_{no})$ depending on whether $D$ rejects or accepts $<M>$. Notice that since $P_1$ is a semantic property shared by both $M_{yes}$ and $M_{no}$, we know that in either case, $M$ has property $P_1$. Then by definition of $D$, $D$ accepts $<M>$ if and only if $M$ has property $P_2$. Thus, we have that $L(M) = L(M_{no})$ if $M$ has property $P_2$ (i.e., $D$ accepts $<M>$) and $L(M) = L(M_{yes})$ if $M$ does not have property $P_2$ (i.e., $D$ rejects $<M>$). This, however, contradicts the fact that $M_{yes}$ has property $P_2$, $M_{no}$ does not have property $P_2$, and $P_2$ is semantic.

By contradiction, we can conclude that decider $D$ as described cannot exist. In other words, $P_2$ given $P_1$ is undecidable.

$\endgroup$

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.