Swipe to navigate through the chapters of this book
A function f is computable if there exist an algorithm that produces the value of f correctly for each possible argument of f. The computation of f for a particular argument x just involves following the instructions in the algorithm, and it produces the result f(x) in a finite number of steps if x is in the domain of f. If x is not in the domain of f then the algorithm may produce an answer saying so or it might run forever never halting. The concept of computability may be made precise in several equivalent ways such as Church’s lambda calculus, recursive function theory or by the theoretical Turing machines. Church and Turing independently showed in 1936 that mathematics is not decidable: i.e. there is no mechanical procedure (i.e. algorithm) to determine whether an arbitrary mathematical proposition is true or false, and so the only way is to determine the truth or falsity of a statement is, try to solve the problem.
Please log in to get access to this content
To get access to this content you need the following product:
The Church-Turing Thesis states that anything that is computable is computable by a Turing Machine.
Russell’s paradox (discussed in Chap. 2) considers the question as to whether the set of all sets that contain themselves as members is a set. In either case there is a contradiction.
The Church Turing Thesis states that anytime that is computable is computable by Lambda Calculus or equivalently by a Turing Machine.
A well-formed formula is valid if it follows from the axioms of first-order logic. A formula is valid if and only if it is true in every interpretation of the formula in the model.
Alonzo Church was a famous American mathematician and logician who developed the lambda calculus. He also showed that Peano arithmetic and first order logic were undecidable. Lambda calculus is equivalent to Turing machines and whatever may be computed is computable by Lambda calculus or a Turing machine.
This is similar to Cantor’s diagonalization argument that shows that the Real numbers are uncountable. This argument assumes that it is possible to enumerate all real numbers between 0 and 1, and it then constructs a number whose nth decimal differs from the nth decimal position in the nth number in the enumeration. If this holds for all n then the newly defined number is not among the enumerated numbers.
go back to reference Cornerstones of Undecideability. Grzegorz Rozenberg and Arto Salomaa. Prentice Hall. 1994. Cornerstones of Undecideability. Grzegorz Rozenberg and Arto Salomaa. Prentice Hall. 1994.
- Computability and Decidability
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 13