expression that cannot be "written down" re: incompleteness, logic

92 Views Asked by At

I apologize for the poor title.

We are given a computer that writes down only expressions that are true. Let $\omega$ be an expression. Define the composition C of $\omega$ as $\omega(\omega)$. We have the following rules:

$W(\omega)$ is true iff $\omega$ is write-able.

$WC(\omega)$ is true iff the composition of $\omega$ is write-able.

$\neg W(\omega)$ is true iff $\omega$ is not write-able.

$\neg WC(\omega)$ is true iff the composition of $\omega$ is not write-able.

An expression is called write-able if the computer can write it down. Can the computer write down all true expressions?

More context: If the computer writes down $WC(\omega)$, we can assume it writes down $\omega(\omega)$. However, if the machine writes down $\omega$, will it write down $W(\omega)$, which is true by Rule 1?

My thinking is that there is definitely some expression the computer cannot write down, but I'm having trouble coming up with it. Something to do with the Godel sentence? But I don't know how to apply it to this question.

2

There are 2 best solutions below

4
On BEST ANSWER

Hint

This is an exercise in coming up with a version of the Goedel sentence in a simplified context. Try using composition to come up with a sentence that says of itself that it is not writable.

1
On

You might very well enjoy/profit from taking a look at the opening chapter or so of Raymond Smullyan's famous text Godel's Incompleteness Theorems (OUP, Oxford Logic Guides) -- it will be in the library!

This book deals beautifully with similar/related issues, exceptionally clearly.