Partea III („Automate infinite. Calculabilitate”) introduce modelul de mașină Turing ca formalizare a procedurii efective și discută limitele calculabilității (în special problema opririi), apoi prezintă teoria funcțiilor recursive și relația ei cu calculabilitatea în sens Turing.
În mod excepțional, public aici textul original al Părții III în două pagini corespunzătoare celor două capitole.
