Turinga nad charakteryzowaniem efektywnej obliczalności za pomocą maszyn abstrakcyjnych (zwanych dziś &lt;name type="prod"&gt;maszynami Turinga&lt;/&gt;). 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 &lt;name type="prod"&gt;Turinga&lt;/&gt;. Powstała w ten sposób teoria funkcji rekurencyjnych jest dziś ważnym działem podstaw matematyki i jednym z ważniejszych narzędzi w badaniach metamatematycznych (por. na ten temat na przykład R. Murawskiego Funkcje rekurencyjne i elementy metamatematyki).<br>Pojęcie rekurencyjności wykorzystywane jest przez prądy konstruktywistyczne na różne sposoby. Powiemy tu