Jakie są formalne zasady wyciągania ważnych wniosków? Co można obliczyć? Jak uzasadniamy niepewne informacje? Filozofowie wytyczyli niektóre z podstawowych idei sztucznej inteligencji, ale przejście do nauki formalnej wymagało matematyzacji logiki i prawdopodobieństwa oraz wprowadzenia nowej gałęzi matematyki: obliczeń. Idea logiki formalnej wywodzi się z filozofów starożytnej Grecji, Indii i Chin, ale jej rozwój matematyczny tak naprawdę rozpoczął się w pracy George’a Boole’a (1815–1864), który opracował szczegóły teorii zdaniowej, czyli logicznej, logika. W 1879 roku Gottlob Frege (1848–1925) rozszerzył logikę Boole’a o obiekty i relacje, tworząc logikę pierwszego rzędu, która jest używana dzisiaj. Oprócz swojej centralnej roli we wczesnym okresie badań nad sztuczną inteligencją, logika pierwszego rzędu motywowała prace Gödla i Turinga, które leżały u podstaw samych obliczeń, jak wyjaśnimy poniżej. Teorię prawdopodobieństwa można postrzegać jako uogólniającą logikę na sytuacje z niepewnymi informacjami, co ma ogromne znaczenie dla sztucznej inteligencji. Gerolamo Cardano (1501–1576) najpierw sformułował pojęcie prawdopodobieństwa, opisując je w kategoriach możliwych skutków wydarzeń hazardowych. W 1654 r. Blaise Pascal (1623–1662) w liście do Pierre’a Fermata (1601–1665) pokazał, jak przewidzieć przyszłość niedokończonej gry hazardowej i przypisać graczom średnie wygrane. Prawdopodobieństwo szybko stało się nieocenioną częścią nauk ilościowych, pomagając radzić sobie z niepewnymi pomiarami i niekompletnymi teoriami. Jacob Bernoulli (1654–1705, wujek Daniela), Pierre Laplace (1749–1827) i inni rozwinęli teorię i wprowadzili nowe metody statystyczne. Thomas Bayes (1702–1761) zaproponował regułę aktualizowania prawdopodobieństw w świetle nowych dowodów; Reguła Bayesa jest kluczowym narzędziem dla systemów sztucznej inteligencji. Formalizacja prawdopodobieństwa w połączeniu z dostępnością danych doprowadziła do pojawienia się statystyki jako dziedziny. Jednym z pierwszych zastosowań była analiza danych spisowych Londynu przeprowadzona przez Johna Graunta w 1662 roku. Ronald Fisher jest uważany za pierwszego współczesnego statystykę. Połączył idee prawdopodobieństwa, projektu eksperymentu, analizy danych i obliczeń – w 1919 r. Twierdził, że nie może wykonywać swojej pracy bez mechanicznego kalkulatora o nazwie MILLIONAIRE (pierwszy kalkulator, który potrafi pomnożyć), mimo że koszt kalkulatora przewyższał jego roczną pensję. Historia obliczeń jest tak stara jak historia liczb, ale uważa się, że pierwszym nietrywialnym algorytmem jest algorytm Euklidesa służący do obliczania największych wspólnych dzielników. Algorytm słów pochodzi od Muhammada ibn Musa al-Khwarizmi, matematyka z IX wieku, którego pisma wprowadziły także cyfry arabskie i algebrę do Europy. Boole i inni omawiali algorytmy dedukcji logicznej, a pod koniec XIX wieku podejmowano próby sformalizowania ogólnego rozumowania matematycznego jako dedukcji logicznej. Kurt Gödel (1906–1978) wykazał, że istnieje skuteczna procedura, aby udowodnić jakiekolwiek prawdziwe stwierdzenie w logice pierwszego rzędu Fregego i Russella, ale ta logika pierwszego rzędu nie może uchwycić zasady indukcji matematycznej potrzebnej do scharakteryzowania liczb naturalnych . W 1931 roku Gödel wykazał, że istnieją ograniczenia dedukcji. Jego twierdzenie o niezupełności wykazało, że w każdej formalnej teorii tak silnej jak arytmetyka Peano (elementarna teoria liczb naturalnych) z konieczności istnieją prawdziwe twierdzenia, które nie mają dowodu w teorii. Ten podstawowy wynik można również zinterpretować jako wskazujący, że niektóre funkcje na liczbach całkowitych nie mogą być reprezentowane przez algorytm – to znaczy, że nie można ich obliczyć. To zmotywowało Alana Turinga (1912–1954) do podjęcia próby dokładnego scharakteryzowania funkcji, które można obliczyć za pomocą skutecznej procedury. Teza Church-Turinga proponuje utożsamianie ogólnego pojęcia obliczalności z funkcjami obliczanymi przez maszynę Turinga (Turing, 1936). Turing pokazał również, że istnieją pewne funkcje, których żadna maszyna Turinga nie może obliczyć. Na przykład żadna maszyna nie jest w stanie ogólnie stwierdzić, czy dany program zwróci odpowiedź na dane wejście, czy będzie działał w nieskończoność. Chociaż obliczalność jest ważna dla zrozumienia obliczeń, pojęcie wykonalności miało jeszcze większy wpływ na sztuczną inteligencję. Z grubsza mówiąc, problem nazywany jest nie do rozwiązania, jeśli czas potrzebny do rozwiązania wystąpienia problemu rośnie wykładniczo wraz z rozmiarem wystąpienia. Rozróżnienie między wielomianem a wykładniczym wzrostem złożoności zostało po raz pierwszy podkreślone w połowie lat sześćdziesiątych XX wieku. Jest to ważne, ponieważ wykładniczy wzrost oznacza, że nawet umiarkowanie duże przypadki nie mogą być rozwiązane w rozsądnym czasie. Teoria NP-zupełności, zapoczątkowana przez Cooka (1971) i Karpa (1972), stanowi podstawę do analizy wykonalności problemów: każda klasa problemów, do której można zredukować klasę NPkompletnych problemów, jest prawdopodobnie nie do rozwiązania. (Chociaż nie zostało udowodnione, że problemy NP-zupełne są z konieczności nie do rozwiązania, większość teoretyków w to wierzy). Wyniki te kontrastują z optymizmem, z jakim popularna prasa witała pierwsze komputery – „Elektroniczne super-mózgi”, które były „szybsze niż Einstein ! ” Pomimo rosnącej szybkości komputerów inteligentne systemy będą charakteryzować się ostrożnym wykorzystaniem zasobów i niezbędną niedoskonałością. Mówiąc prymitywnie, świat jest wyjątkowo dużym problemem!