next up previous
Next: Questions Up: Two Gödelian Puzzles Previous: Two Gödelian Puzzles

The First Puzzle

Suppose there is a machine tex2html_wrap_inline56 tex2html_wrap_inline58 which prints out various expressions built from the following five symbols:

displaymath60

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

The mirror of an expression tex2html_wrap_inline70 is the expression tex2html_wrap_inline72 -- e.g., the mirror of tex2html_wrap_inline74 is tex2html_wrap_inline76 . A sentence is an expression having one of the following four forms:

  1. tex2html_wrap_inline78
  2. tex2html_wrap_inline80
  3. tex2html_wrap_inline82
  4. tex2html_wrap_inline84

P stands for ``printable;" M stands for ``the mirror of" and tex2html_wrap_inline90 stands (as it often does in logic) for ``not." Hence we define tex2html_wrap_inline78 to be true iff tex2html_wrap_inline70 is printable. We define tex2html_wrap_inline80 to be true if the mirror of tex2html_wrap_inline70 is printable. We call tex2html_wrap_inline82 true iff tex2html_wrap_inline70 is not printable, and tex2html_wrap_inline84 is defined to be true iff the mirror of tex2html_wrap_inline70 is not printable.

We are given that the machine tex2html_wrap_inline56 tex2html_wrap_inline58 is accurate in that all sentences printed by the machine are true. So, for example, if the machine ever prints tex2html_wrap_inline78 , then tex2html_wrap_inline70 really is printable (i.e., tex2html_wrap_inline70 will be printed by tex2html_wrap_inline56 tex2html_wrap_inline58 sooner or later). Also, if tex2html_wrap_inline80 is printable, so is tex2html_wrap_inline124 .

Suppose tex2html_wrap_inline70 is printable. Do we then know that tex2html_wrap_inline78 is printable? No; here's why. If tex2html_wrap_inline70 is printable then tex2html_wrap_inline78 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.



Selmer Bringsjord
Tue Jan 20 11:43:03 EST 1998