The First Puzzle

Suppose there is a machine $\cal M$₀ which prints out various expressions built from the following five symbols:

$$\sim \: P \: M \: ( \: )$$

By an expression we mean any finite non-empty string built from these five symbols. (So PPPPPPMM(( is an expression, as is $\sim P(P)$.) An expression is called printable if the machine can print it. We assume that $\cal M$₀ is programmed so that any expression it can print will be printed sooner or later.

The mirror of an expression $\phi$ is the expression $\phi (\phi)$ -- e.g., the mirror of $P \sim$ is $P \sim (P \sim)$. A sentence is an expression having one of the following four forms:

1.

$P(\phi)$

2.

$P M(\phi)$

3.

$\sim P(\phi)$

4.

$\sim P M(\phi)$

P stands for ``printable;" M stands for ``the mirror of" and $\sim$ stands (as it often does in logic) for ``not." Hence we define $P(\phi)$ to be true iff $\phi$ is printable. We define $P M(\phi)$ to be true if the mirror of $\phi$ is printable. We call $\sim P(\phi)$ true iff $\phi$ is not printable, and $\sim P M(\phi)$ is defined to be true iff the mirror of $\phi$ is not printable.

We are given that the machine $\cal M$₀ is accurate in that all sentences printed by the machine are true. So, for example, if the machine ever prints $P(\phi)$, then $\phi$ really is printable (i.e., $\phi$ will be printed by $\cal M$₀ sooner or later). Also, if $P M(\phi)$ is printable, so is $M(\phi)$.

Suppose $\phi$ is printable. Do we then know that $P(\phi)$ is printable? No; here's why. If $\phi$ is printable then $P(\phi)$ is certainly true, but we are not given that the machine is capable of printing all true sentences -- only that the machine never prints any false ones.