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).
Notice that this is homework, so I would appreciate if you gave me hints, not complete solutions.
Thanks in advance!
