The Present State of Mechanized Deduction, and the Present Knowledge of its Limitations

• Authors: Murawski R.
• Languages of publication: EN

Abstracts

EN

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.

Keywords

EN

MECHANIZATION & AUTOMATIZATION OF REASONING; MECHANIZED DEDUCTION'S LIMITATIONS

Discipline

• OTHER_SOCIAL_SCIENCES: OTHER SOCIAL SCIENCES

• Publisher: Sciendo
• Journal: Studies in Logic, Grammar and Rhetoric
• Year: 2006
• Volume: 9
• Issue: 22
• Pages: 31-60
• Document type: ARTICLE

Contributors

author

Murawski R.

• R. Murawski, Uniwersytet im. Adama Mickiewicza, Wydzial Matematyki i Informatyki, ul. Umultowska 87, 61-614 Poznan, Poland

Identifiers

CEJSH db identifier

07PLAAAA02224687