8
$\begingroup$

I am currently doing exercises on the Gödelian theorems; and we are confronted with the introductory puzzle of R. Smullyan's book, which is as follows:

Suppose we have a machine which prints strings over the alphabet $p, n, (, ), \neg$. The norm of a string $e$ is defined to be the string $e(e)$. Some strings are sentences, which have a truth value. Sentences are of the form $p(w), \neg p(w), \neg pn(w), pn(w)$, where $w$ is an arbitrary string. Truth values are assigned to sentences as follows:

  • $p(w)$ is true exactly if $w$ is printable,
  • $\neg p(w)$ is true exactly if $w$ is not printable,
  • $pn(w)$ is true exactly if $w(w)$ (i.e., the norm of $w$) is printable,
  • $\neg pn(w)$ is true exactly if $w(w)$ is not printable.

Smullyan concludes that the sentence $G = \neg pn(\neg pn)$ is true but not printable. Our task is now to find another sentence which is true but surely not printable. However, I don't figure out how to construct such another sentence. It is clear that such a sentence needs some kind of self-reference like the sentence $G$ above; however it seems to me that one cannot find a string $s$ different from $\neg pn$ such that the norm of $\neg pn(s)$ is exactly $\neg pn(s)$ (which would establish the self-reference).

The machine is sound. That means, it never prints false statements.

Notice that this is homework, so I would appreciate if you gave me hints, not complete solutions.

Thanks in advance!

  • 0
    How about $\lnot \lnot \lnot pn(\lnot \lnot \lnot pn)$?2013-12-28

1 Answers 1

2

Well, because $\lnot pn(\lnot pn)$ is not printable, $\lnot p(\lnot pn(\lnot pn))$ is true. But it is not printable, because if it was then $\lnot pn(\lnot pn)$, a substring, would be printable (when you print a string, you also print each of its substrings).

  • 0
    @Ross Millikan: please feel free to edit this community wiki answer, which also took.from comments. My worry with your string is that the description of sentences in the question seems to limit them to one leading $\lnot$.2013-12-28