Ένας Γκεντελιανός Γρίφος.

Υποθέτουμε ότι υπάρχει μια μηχανή η οποία τυπωνει καποιες εκφρασεις οι οποιες αποτελουνται απο τα παρακατω συμβολα

Με τον ορο εκφραση εννοουμε καθε πεπερασμενη και μη κενη ακολουθια απο τα 5 συμβολα αυτα. Μια εκφραση ονομαζεται τυπώσιμη αν μπορει η μηχανη μας να την τυπωσει. Επισης υποθετουμε οτι αν μια εκφραση ειναι τυπώσιμητοτε η μηχανη θα την τυπωσει στο μελλον καποια στιγμη.Με τον όρο νόρμα μιας έκφρασης εννοούμε την έκφραση και την συμβολίζουμε με , με τον όρο πρόταση εννοούμε μια έκφραση της μορφής:

1. 
2. 
3. 
4. 

To νόημα που δίνουμε στις προτάσεις είναι το προφανές, το σημαίνει τυπώσιμη, το η νόρμα της και το για το όχι. Ορίζουμε:

• Η πρόταση είναι αληθής αν και μόνο αν η έκφραση είναι τυπώσιμη
• Η πρόταση είναι αληθής αν και μόνο αν η έκφραση είναι τυπώσιμη
• Η πρόταση είναι αληθής αν και μόνο αν η έκφραση δεν είναι τυπώσιμη
• Η πρόταση είναι αληθής αν και μόνο αν η έκφραση δεν είναι τυπώσιμη

Επίσης υποθέτουμε ότι η μηχανή δεν μας κοροϊδεύει. Δεν τυπώνει ψευδείς προτάσεις αλλά μόνο αληθείς, δηλαδή αν η μηχανή τυπώσει την πρόταση τότε η έκφραση κάποια στιγμή θα τυπωθεί από την μηχανή. Ορίσαμε καλά το πότε μια πρόταση είναι αληθής και πότε ψευδής. Το παράδοξο είναι ότι η μηχανή μας είναι μια αυτοαναφορική μηχανή, μπορεί να μιλάει για τον εαυτό της π.χ. οι εκφράσεις .

Ερώτηση: Μπορείτε να βρείτε μια πρόταση η οποία είναι αληθής άλλα δεν μπορεί να τυπωθεί;