Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

13. Computability and Decidability

Author: Gerard O’Regan

Publisher: Springer International Publishing

Published in: Guide to Discrete Mathematics

» Get access to the full version

Abstract

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:

Computer Science Explorer

Purchase now

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.

Cornerstones of Undecideability. Grzegorz Rozenberg and Arto Salomaa. Prentice Hall. 1994.

Title

Computability and Decidability

Book

Guide to Discrete Mathematics

Print ISBN: 978-3-319-44560-1

Electronic ISBN: 978-3-319-44561-8

https://doi.org/10.1007/978-3-319-44561-8

DOI

https://doi.org/10.1007/978-3-319-44561-8_13

Author:

Gerard O’Regan

Publisher

Springer International Publishing

Sequence number

Chapter number

Chapter 13