Turing (1936) i Gödel (1931) dowiedli, że na niektóre pytania matematyczne w zasadzie nie dają odpowiedzi poszczególne systemy formalne. Twierdzenie o niezupełności Gödela jest najbardziej znanym tego przykładem. Krótko mówiąc, dla dowolnego formalnego szkieletu aksjomatycznego F wystarczająco silnego do wykonywania arytmetyki, możliwe jest skonstruowanie tak zwanego zdania Gödla G(F) o następujących własnościach:
- G(F) jest zdaniem F, ale nie może być udowodnione w ramach F.
- Jeśli F jest niesprzeczne, to G(F) jest prawdziwe.
Filozofowie tacy jak J.R. Lucas (1961) twierdzili, że twierdzenie to pokazuje, że maszyny są mentalnie gorsze od ludzi, ponieważ maszyny są formalnymi systemami, które są ograniczone przez twierdzenie o niezupełności – nie mogą ustalić prawdziwości własnego zdania Gödel – podczas gdy ludzie brak takiego ograniczenia. Wywołało to wiele kontrowersji, tworząc ogromną literaturę, w tym dwie książki matematyka/fizyka Sir Rogera Penrose’a (1989, 1994). Penrose powtarza twierdzenie Lucasa z kilkoma nowymi zwrotami akcji, takimi jak hipoteza, że ludzie są inni, ponieważ ich mózgi działają na zasadzie grawitacji kwantowej – teoria, która zawiera wiele fałszywych prognoz dotyczących fizjologii mózgu. Zbadamy trzy problemy związane z twierdzeniem Lucasa. Po pierwsze, agent nie powinien się wstydzić, że nie może ustalić prawdziwości jakiegoś zdania, podczas gdy inni agenci mogą. Rozważ następujące zdanie: Lucas nie może konsekwentnie twierdzić, że to zdanie jest prawdziwe. Gdyby Lucas stwierdził to zdanie, to sam by sobie zaprzeczał, więc Lucas nie może go konsekwentnie wypowiadać, a więc jest prawdziwe. W ten sposób wykazaliśmy, że istnieje prawdziwe zdanie, którego Lucas nie może konsekwentnie twierdzić, podczas gdy inni ludzie (i maszyny) mogą. Ale to nie sprawia, że myślimy mniej o Lucasie. Po drugie, twierdzenie Gödela o niezupełności i związane z nim wyniki odnoszą się do matematyki, a nie do komputerów. Żadna istota — człowiek ani maszyna — nie może udowodnić rzeczy, których udowodnienie jest niemożliwe. Lucas i Penrose fałszywie zakładają, że ludzie mogą w jakiś sposób obejść te granice, jak wtedy, gdy Lucas (1976) mówi: „musimy założyć własną konsekwencję, jeśli myślenie ma być w ogóle możliwe”. Ale jest to nieuzasadnione założenie: ludzie są notorycznie niekonsekwentni. Jest to z pewnością prawdziwe w codziennym rozumowaniu, ale dotyczy to również uważnego myślenia matematycznego. Znanym przykładem jest problem mapy czterokolorowej. Alfred Kempe (1879) opublikował dowód, który był powszechnie akceptowany przez 11 lat, dopóki Percy Heawood (1890) nie wykazał błędu. Po trzecie, twierdzenie G¨odela o niezupełności technicznie stosuje się tylko do systemów formalnych, które są wystarczająco potężne, aby wykonywać arytmetykę. Obejmuje to maszyny Turinga, a twierdzenie Lucasa jest częściowo oparte na założeniu, że komputery są równoważne maszynom Turinga. To nie do końca prawda. Maszyny Turinga są nieskończone, podczas gdy komputery (i mózgi) są skończone, a zatem każdy komputer można opisać jako (bardzo duży) system w logice zdań, który nie podlega twierdzeniu G¨odela o niezupełności. Lucas zakłada, że ludzie mogą „zmienić zdanie”, podczas gdy komputery nie, ale jest to również fałszywe — komputer może wycofać wniosek po nowych dowodach lub dalszych rozważaniach; może uaktualnić swój sprzęt; i może zmienić swoje procesy decyzyjne dzięki uczeniu maszynowemu lub przepisaniu oprogramowania.