O'Reilly logo

Computation, Proof, Machine by Marion Roman, Pierre Guillot, Gilles Dowek

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter Five Church’s Thesis

THE ATTEMPT to address Hilbert’s decision problem and the negative result it achieved in Church’s theorem led mathematicians of the thirties to clarify what an algorithm is. They offered many definitions, among which were the Herbrand–Gödel equations, Church’s lambda calculus, Turing machines, Kleene’s recursive functions, and rewrite rules. Each of these puts forward a language in which to express algorithms – nowadays, we would say that each defines a “programming language.”

Time has shown these definitions to be equivalent: if an algorithm can be defined in one of these programming languages, that definition can be translated into any of the others. This equivalence of definitions ranks among the greatest successes ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required