‎"CHURCH, ALONZO (+) ALAN TURING (+) EMIL POST.‎
‎[Church:] A note on the Entscheidungsproblem (+) Correction to A note on the Entscheidungsproblem (+) Review of ""A. M. Turing. On Computable numbers, with an application to the Entscheidungsproblem"" (+) [Post:] Finite combinatory processes-formulation... - [LANDMARK VOLUME IN THE HISTORY OF LOGIC]‎

‎[No place], The Association for Symbolic Logic, 1936 & 1937. Royal8vo. Bound in red half cloth with gilt lettering to spine. In ""Journal of Symbolic Logic"", Volume 1 & 2 bound together. Barcode label pasted on to back board. Small library stamp to lower part of 16 pages. A very fine copy. [Church:] Pp. 40-1" Pp. 101-2. [Post:] Pp. 103-5. [Turing:] Pp. 153-163" 164. [Entire volume: (4), 218, (2), IV, 188 pp.]‎

Reference : 48376

‎First edition of this collection of seminal papers within mathematical logic, all constituting some of the most important contributions mathematical logic and computional mathematics. A NOTE ON THE ENTSCHEIDUNGSPROBLEM (+) CORRECTION TO A NOTE ON THE ENTSCHEIDUNGSPROBLEM (+) REVIEW OF ""A. M. TURING. ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM"":First publication of Church's seminal paper in which he proved the solution to David Hilbert's ""Entscheidungsproblem"" from 1928, namely that it is impossible to decide algorithmically whether statements within arithmetic are true or false. In showing that there is no general algorithm for determining whether or not a given statement is true or false, he not only solved Hilbert's ""Entscheidungsproblem"" but also laid the foundation for modern computer logic. This conclusion is now known as Church's Theorem or the Church-Turing Theorem (not to be mistaken with the Church-Turing Thesis). The present paper anticipates Turing's famous ""On Computable Numbers"" by a few months. ""Church's paper, submitted on April 15, 1936, was the first to contain a demonstration that David Hilbert's 'Entscheidungsproblem' - i.e., the question as to whether there exists in mathematics a definite method of guaranteeing the truth or falsity of any mathematical statement - was unsolvable. Church did so by devising the 'lambda-calculus', [...] Church had earlier shown the existence of an unsolvable problem of elementary number theory, but his 1936 paper was the first to put his findings into the exact form of an answer to Hilbert's 'Entscheidungsproblem'. Church's paper bears on the question of what is computable, a problem addressed more directly by Alan Turing in his paper 'On computable numbers' published a few months later. The notion of an 'effective' or 'mechanical' computation in logic and mathematics became known as the Church-Turing thesis."" (Hook & Norman: Origins of Cyberspace, 250) Church coined in his review of Turing's paper the phrase 'Turing machine'.FINITE COMBINATORY PROCESSES-FORMULATION I: The Polish-American mathematician Emil Post made notable contributions to the theory of recursive functions. In the 1930s, independently of Turing, Post came up with the concept of a logic automaton similar to a Turing machine, which he described in the present paper (received on October 7, 1936). Post's paper was intended to fill a conceptual gap in Alonzo Church's paper on 'An unsolvable problem of elementary number theory'. Church had answered in the negative Hilbert's 'Entscheidungsproblem' but failed to provide the assertion that any such definitive method could be expressed as a formula in Church's lambda-calculus. Post proposed that a definite method would be one written in the form of instructions to mind-less worker operating on an infinite line of 'boxes' (equivalent to the Turing machines 'tape'). The range of instructions proposed by Post corresponds exactly to those performed by a Turing machine, and Church, who edited the Journal of Symbolic Logic, felt it necessary to insert an editorial note referring to Turing's ""shortly forthcoming"" paper on computable numbers, and asserting that ""the present article ... although bearing a later date, was written entirely independently of Turing's"". (Hook & Norman: Origins of Cyberspace, 356).COMPUTABILITY AND LAMBDA-DEFINABILITY (+) THE Ø-FUNCTION IN LAMBDA-K-CONVERSION: The volume also contains Turing's influential ""Computability and lambda-definability"" in which he proved that computable functions ""are identical with the lambda-definable functions of Church and the general recursive functions due to Herbrand and Gödel and developed by Kleene"". (Hook & Norman: Origins of Cyberspace, 395).‎