o niezupełności arytmetyki i systemów bogatszych), dalej o Alonzo Churchu i jego m-rachunku, o logice kombinatorycznej Curry'ego (równoważnej m-rachunkowi) czy w końcu o badaniach Alana M. Turinga nad charakteryzowaniem efektywnej obliczalności za pomocą maszyn abstrakcyjnych (zwanych dziś <name type="prod">maszynami Turinga</>). Wszystkie te badania, prowadzone przy odwołaniu się do różnych motywacji i założeń, przyczyniły się do wyjaśnienia intuicyjnego pojęcia efektywności i obliczalności. Pokazano, że klasa funkcji rekurencyjnych pokrywa się z klasą funkcji m-definiowalnych i z klasą funkcji obliczalnych za pomocą maszyn <name type="prod">Turinga</>. Powstała w ten sposób teoria funkcji rekurencyjnych jest dziś ważnym działem podstaw matematyki i jednym z ważniejszych narzędzi