Dva logické stroje

První stroj lze nalézt ve Smullyanově knize Navěky nerozhodnuto. Stroj používá pouze těchto šest symbolů: P, → ⊥, (, ) a R. Stroj tiskne věty složené z těchto znaků. Věta a pravdivá věta je definována pomocí těchto pravidel:

(1) ⊥ je věta. Tato věta je nepravdivá.

(2) Jestliže je X a Y věta, pak je (X → Y) také věta. Tato věta je pravdivá, jestliže je pravdivá Y nebo není nepravdivá X.

(3) Pro každou větu X je věta i PX. Tato věta je pravdivá, jestliže stroj může vytisknout X.

(4) Kro každé dvě věty X a Y je (X R Y) také věta. Tato věta je pravdivá, jestliže stroj může vytisknout ((X R X) → Y).

Axiómy stroje jsou tyto:

(I) Všechny tautologie.

(II) Všechny věty ve tvaru P(X → Y) → (PX → Y).

(III) Všechny věty ve tvaru PX → PPX.

(IV) Všechny věty ve tvaru (X R Y) ↔ P((X R X) → Y).

Použitá spojka A ↔ B je zkratka za (((A → B) → ((B → A) → ⊥)) → ⊥).

Operační pravidla tohoto stroje jsou:

(A) Může být vytištěn jakýkoli axióm.

(B) Jestliže byla vytištěna věta X a věta (X → Y), pak stroj může vytisknout větu Y.

(C) Jestliže byla vytištěna věta X, stroj může vytisknout PX.

Všechny axiómy jsou pravdivé. Lze se snadno přesvědčit, že stroj může vytisknout jen pravdivé věty. Stroj je tedy bezesporný. Zkoumejme dále tento stroj. Pro libovolné dvě věty X a Y podle (IV) platí, že věta

(X R Y) ↔ P((X R X) → Y)

může být vytištěna. Platí to tedy i pro X = Y. Stroj tedy může vytisknout

(X R X) ↔ P((X R X) → X).

Tudíž podle (4) stroj může vytisknout i větu

(X R X → X) ↔ (P((X R X) → X) → X)

Zvolme nyní za X větu ⊥. Zkrátím-li (A → ⊥) jako, ¬A a větu (⊥ R ⊥ → ⊥) na G, pak lze napsat, že stroj může vytisknout

G ↔ (¬PG).

Tato věta je pravdivá, jestliže stroj nikdy větu G nevytiskne. A protože stroj tiskne jen pravdivé věty, stroj nikdy větu G nevytiskne. Přitom věta G je pravdivá. Smullyan větě G říká z pochopitelného důvodu věta Gödelova.

Jiný a jednodušší stroj lze nalézt ve Smullyanově knize Gödel’s Incompleteness Theorems. Stroj používá pět znaků: P, N, ~, ( a ). Závorky nemusí párovat. Řetězec P(x) znamená, že x je tisknutelný. Řetězec ~P(x) znamená, že x je netisknutelný. Norma řetězce x je řetězec x(x). Řetězec PN(x) znamená, že norma řetězce x je tisknutelná, a ~PN(x) znamená, že norma x je netisknutelná. Předpokládejme, že stroj tiskne jen pravdivé řetězce. Mějme řetězec ~PN(~PN). Tato věta znamená, že norma ~PN je netisknutelná. Norma ~PN je řetězec ~PN(~PN). Věta tedy sama o sobě říká, že je netisknutelná. Ale ani řetězec PN(~PN) není tisknutelný, protože pak by byl tisknutelný i ~PN(~PN) a stroj by se dostal do sporu sám se sebou. Řetězec ~PN(~PN) ani PN(~PN) stroj nevytiskne, ať už ho naprogramujeme jakkoli. Máme tu jasný příklad nerozhodnutelného tvrzení. Podívejme se ještě na větu ~P(~PN(~PN)). Tento řetězec už stroj vytisknout může. Stejně tak řetězec ~P(PN(~PN)). Tedy stroj, stejně jako v předchozím případě, věty o tom, že existuje nerozhodnutelný problém, stroj rozhodnout může.

Popisy těchto strojů nejsou ekvivalentní první Gödelově větě o neúplnosti, ale mají některé společné prvky.