Show Less
Restricted access

Lógos and Máthēma 2

Studies in the Philosophy of Logic and Mathematics

Series:

Roman Murawski

The volume consists of thirteen papers devoted to various problems of the philosophy of logic and mathematics. They can be divided into two groups. The first group contains papers devoted to some general problems of the philosophy of mathematics whereas the second group – papers devoted to the history of logic in Poland and to the work of Polish logicians and math-ematicians in the philosophy of mathematics and logic. Among considered problems are: meaning of reverse mathematics, proof in mathematics, the status of Church’s Thesis, phenomenology in the philosophy of mathematics, mathematics vs. theology, the problem of truth, philosophy of logic and mathematics in the interwar Poland.
Show Summary Details
Restricted access

The Status of Church’s Thesis (co-author: Jan Woleński)

The Status of Church’s Thesis

Extract

Co-authored by Jan Woleński

Thus (CT) identifies the class of effectively computable or calculable (we will treat these two categories as equivalent) functions with the class of partially recursive functions. This means that every element belonging to the former class is also a member of the latter class and reversely. Clearly, (CT) generates an extensional co-extensiveness of effective computability and partial recursivity. Since we have no mathematical tasks, the exact definition of recursive functions and their properties is not relevant here. On the other hand, we want to stress the property of being effective computable, which plays a basic role in philosophical thinking about (CT).31

A useful notion in providing intuitions concerning effectiveness is that of an algorithm. It refers to a completely specified procedure for solving problems of a given type. Important here is that an algorithm does not require creativity, ingenuity or intuition (only the ability to recognize symbols is assumed) and that its application is prescribed in advance and does not depend upon any empirical or random factors. Moreover, this procedure is performable in a finite number of steps. Thus a function f ∶ Nn → N is said to be effectively computable (briefly: computable) if and only if its values can be computed by an algorithm. Putting this in other words: a function f ∶Nn →N is computable if and only if there exists a mechanical method by which for any n-tuple (a1, . . . , an) of arguments, the value f (a1, . . . , an) can...

You are not authenticated to view the full text of this chapter or article.

This site requires a subscription or purchase to access the full text of books or journals.

Do you have any questions? Contact us.

Or login to access all content.