Suppose there is a machine
which
prints out various expressions
built from the following five symbols:
By an expression we mean any finite non-empty string built
from these five symbols. (So PPPPPPMM((
is an expression, as is
.)
An expression is called printable
if the machine can print it. We assume that
is programmed so that
any expression it can print will be printed sooner
or later.
The mirror of an expression
is the expression
--
e.g.,
the mirror of
is
. A sentence is an
expression having one of the following four forms:
P stands for ``printable;" M stands for ``the mirror of" and
stands (as it often does in logic) for ``not." Hence we define
to be true iff
is printable. We define
to be true if the mirror of
is printable. We call
true iff
is not printable, and
is defined to be true iff the mirror of
is
not printable.
We are given that the machine
is accurate in that all sentences
printed by the machine are true. So, for example, if the machine
ever prints
, then
really is printable (i.e.,
will
be printed by
sooner or later). Also, if
is
printable, so is
.
Suppose
is printable. Do we then know that
is printable?
No; here's why. If
is printable then
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.