The Present State of Mechanized Deduction, and the Present Knowledge of its Limitations
Wybrane pełne teksty z tego czasopisma
The aim of the paper is to present the history of researches devoted to the mechanization of reasoning. We start by describing the early attempts of applying computers to prove theorems, in particular the results of Davis, Newell-Shaw-Simon, Gilmore, Gelentner et al., Hao Wang and Davis-Putnam are considered. Further the method of resolution and unification as well as their modifications are discussed. They turned out to be crucial for further development of researches towards mechanization and automatization of reasonings - the latter are skechted in next sections. The last section of the paper is devoted to limitations of mechanized deduction and automated theorem proving. Effective and feasible computability/decidability/deducibility are distinguished and some examples of the complexity of decision procedures for certain theories are provided. The role of the speed-up phenomenon is considered and Boolos' example indicating the strength of the second order logic is discussed.
CEJSH db identifier