|
CHURCH, ALONZO; TURING, ALAN; POST, EMIL L. -CHURCH: A note on the Entscheidungsproblem; WITH: Correction to A note on the Entscheidungsproblem; WITH: [Review of] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem -POST: Finite combinatory processes-formulation 1 -TURING: Computability and \Kl\k-definability FIRST PRINTINGS by Alonzo Church, Alan Turing, and Emile Post that helped provide the theoretical foundation for the modern computer. The first two volumes of the influential Journal of Symbolic Logic, containing the first printings of four seminal papers in the history of computers and computer logic: 1) Alonzo Church's solution to the "Halting Problem", proving that an algorithm could not be created to solve every mathematical problem; 2) Church's acknowledgement and analysis of Alan Turing's solution to the same problem; 3) Alan Turing's synthesis of the two methods; 4) Emil Post's conceptual creation of what would become known as "Post's machine", a powerful model for the computer considered to be equal to that of Turing's. In 1936, working independently, Alan Turing in his landmark "On Computable Numbers", and Alonzo Church in "A Note on the Entscheidungsproblem", offered solutions to the famous "Halting Problem" (or "Entscheidungsproblem"), the much debated challenge to symbolic logic to discover whether or not any mathematical problem could potentially be solved by an algorithm. Turing and Church both "showed that in general this problem has no solution, proving that no consistent formal system of arithmetic is decidable. This result and others—notably the mathematician-logician Kurt Gödel's incompleteness theorems—ended the dream of a system that could banish ignorance from mathematics forever... An important argument of Turing's and Church's was that the class of lambda-definable functions (functions on the positive integers whose values can be calculated by a process of repeated substitution) coincides with the class of all functions that are effectively calculable—or computable. This claim is now known as Church's thesis—or as the Church-Turing thesis when stated in the form that any effectively calculable function can be calculated by a universal Turing machine, a type of abstract computer that Turing had introduced in the course of his proof. (Turing showed in 1936 that the two formulations of the thesis are equivalent by proving that the lambda-definable functions and the functions that can be calculated by a universal Turing machine are identical.)" Although Church published his findings first, "in a review of Turing's work [included in this collection], Church acknowledged the superiority of Turing's formulation of the thesis over his own, saying that the concept of computability by a Turing machine 'has the advantage of making the identification with effectiveness…evident immediately.'" (Britannica). Emil L. Post, in "Finite combinatory processes-formulation 1," created a conceptual machine model called "Formulation 1" equal in power to that of Turing's. Both Post (whose paper preceded Turing's by two months) and Turing "conceived of a what is now called an automaton and described it in similar, mechanistic terms. The men worked independently and in ignorance of each other... The work of Post and Turing made it very clear that from the point of view of formal logics there was no problem to devise codes which were 'in abstracto adequate to control and cause the execution of any sequence of operations which are individually available in the machine and which are, in their entirety, conceiveable by the problem planner.' The problem is of a practical nature and is closely allied to that connected with the choice of the elementary operations in the arithmetic organ. The code for a machine is in reality the vocabulary or totality of words or orders that a machine can 'understand' and 'obey.' The designer needs to compromise between his desire for simplicity of the equipment required by the code and the applicability and speed with which the really important problems can be solved. These things are still true today" (Goldstine, The Computer from Pascal to Von Neumann, 174, 258). CHURCH, Alonzo. A note on the Entscheidungsproblem, in Journal of Symbolic Logic, Vol 1 (1936) pp. 40-41. WITH: Correction to A note on the Entscheidungsproblem, ibid., pp. 101-2. WITH: [Review of] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem, ibid. Vol 2 (1937) pp. 42-43. WITH: POST, Emil L. Finite combinatory processes-formulation 1, ibid., Vol 1 (1936) pp. 103-5. WITH: TURING, Alan M. Computability and \Kl\k-definability, ibid., Vol 2 (1937) pp. 153-63. [np]: The Association for Symbolic Logic, Inc., 1936-37. Quarto, green library cloth. Two volumes bound together; includes rare front wrapper to first issue. Fine condition. $5000. |
