1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ oh, I think I see. something along the lines of $\neg WC ( WC (\omega))$? $\endgroup$ – user486635 Apr 25 '18 at 15:16
  • $\begingroup$ @4313 the idea is to play around with expressions like that, yes. However, what is $\omega$ here? I don’t even know how to give meaning to that sentence (formula?) $\endgroup$ – spaceisdarkgreen Apr 25 '18 at 15:19
  • $\begingroup$ $\omega$ is an expression -- is that what you are asking? (Sorry, I am in part very confused about my own original question, and I've posted here all the information I was given) $\endgroup$ – user486635 Apr 25 '18 at 15:19
  • 1
    $\begingroup$ @4313 what I’m saying is is that your attempt $\lnot WC(WC(\omega))$ is not a sentence we can interpret cause it contains an unspecified expression $\omega.$ I’ll give the intended answer: $\lnot WC(\lnot WC)$ is a true statement that the computer cannot write. $\endgroup$ – spaceisdarkgreen Apr 25 '18 at 15:27
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for the recommendation! $\endgroup$ – user486635 Apr 25 '18 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy