Philosophy Dictionary of ArgumentsHome
| |||
|
| |||
| Calculability: here, we are concerned with the question whether certain operations can be performed in principle by means of a procedure or whether questions can be answered by a method. In particular, we are concerned with the calculation of mathematical functions in finite time. The question of whether a problem can be calculated is only useful relative to a model. See also complex/complexity, Turing machine, decidability, decision theory, decision problem, holding problem, models, algorithms, completeness, incompleteness, Church-Turing Thesis, Turing-Machine._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. | |||
| Author | Concept | Summary/Quotes | Sources |
|---|---|---|---|
|
Alonzo Church on Calculability - Dictionary of Arguments
Thiel I 249 Calculability/Church/Thiel: how close did one get to a concept of "general calculability"? There is the concept of "Turing calculability" of "l-definability in Church, the "canonical systems" in Post. Each function, which is in one of these classes, is also demonstrable in the others. Church: Church has then assumed the presumption that an adequate specification of the general concept of calculability is achieved. ("Church thesis"). >"Church-Thesis". But it means that this is an "non-mathematical" presumption, and is not capable of any mathematical proof. An intuitive term. Whether such a specification is "adequate" cannot be answered by mathematical means. >Adequacy. I 250 Apart from finiteness and constructivity, there remain other questions: none of the definitions for the offered functional classes is finite: (e.g. μ-recursive functions). >Recursion, >Finiteness, >Definitions, >Definability. The attempt to describe effective executability with classical means remains questionable, but if we interpret the existence quantifier constructively, we have already presupposed the concept of constructivity. >Existential quantification, >Quantifiers, >Effectiveness. Thiel I 251 Calculability/Herbrand/Thiel: Due to Herbrand's demands, some of the classical laws of logic lose their validity. >J. Herbrand. For example, the end of ~ (x) A (x) to (Ex) ~ A (x) is not permissible: For example, that not all real numbers are algebraic, does not yet help us to a transfinite real number. For example, from the fact that the statements: "The decimal fraction development of pi contains an uninterrupted sequence of 1000 ones" and "The decimal fraction development of pi does not contain an uninterrupted sequence of 100 ones" both cannot be true (since the second statement follows from the first statement), one cannot conclude that the negation of the first statement or the last statement in the parenthesis is true. I 252 This counter-example, however, shows that the classic conclusion of ~ (a u b) to ~ a v ~ b is not permissible if the adjunction sign is to be used for the expression of a decidable alternative. In particular, as can be seen in the substitution of b by ~ a, we cannot conclude from ~ (a u ~ a) to ~ a v ~~ a, although this is a special case of the classical unrestrictedly valid tertium non datur. >Law of the excluded middle, >Logical constants, >Substitutability._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Chur I A. Church The Calculi of Lambda Conversion. (Am-6)(Annals of Mathematics Studies) Princeton 1985 T I Chr. Thiel Philosophie und Mathematik Darmstadt 1995 |
||
> Counter arguments against Church
> Counter arguments in relation to Calculability
Ed. Martin Schulz, access date 2024-04-19