1991 | OriginalPaper | Chapter
Computability — Logical and Recursive Complexity
Author : Stanley S. Wainer
Published in: Logic, Algebra, and Computation
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The basis of this short course is the strong analogy between programs and proofs (of their specifications). The main theme is the classification of computable number-theoretic functions according to the logical complexity of their formal specification or termination proofs. A significant sub-branch of mathematical logic has grown around this theme since the 1950’s and new ideas are presently giving rise to further developments. The methods employed are chiefly those from proof theory, particularly “normalization” as presented in the accompanying lectures of Helmut Schwichtenberg, and “ordinal assignments”. Since program-termination corresponds to well-foundedness of computation trees, it is hardly surprising that transfinite ordinals and their constructive representations play a crucial role, measuring the logical complexity of programs and of the functions which they compute.