# Gödelian incompleteness; Smullyan's Puzzle

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.

-
Are there extra conditions that you're not reproducing? Otherwise I don't see what prevents $\neg pn(\neg pn)$ from being printable and false? –  Henning Makholm Dec 30 '12 at 16:53
Sorry, I forgot: the machine is assumed to never print false statements, i.e., the machine is sound. –  trin Dec 30 '12 at 16:54
I have the same homework and we got the hint / additional information (We are probably taking the same course? ^^): "You may use the assumption that printable strings cannot contain non-printable substrings." To me it seems that sentence opens a lot of possibilites of true and unprintable sentences. –  Meera Jan 3 '13 at 20:49
How about $G \wedge G?$ –  Ross Millikan Jan 3 '13 at 20:54
@Ross Millikan: what does $G \wedge G$ mean? –  miracle173 Oct 24 '13 at 5:58

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).
I think a string is S printable if there is an input for this Turing machine that generates the output S. Your machine will never be able to print a string $\neg p(w)$. –  miracle173 Oct 24 '13 at 6:53
@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$. –  Carl Mummert Dec 28 '13 at 12:33