The Origins of Cyberspace collection described as lots 1-255 will first be offered as a single lot, subject to a reserve price. If this price is not reached, the collection will be immediately offered as individual lots as described in the catalogue as lots 1-255.
CHURCH, Alonzo (1903-1995). "A note on the Entscheidungsproblem." In Journal of Symbolic Logic 1 (1936): 40-41. [With:] "Correction to A note on the Entscheidungsproblem." In Journal of Symbolic Logic 1 (1936): 101-2.
Details
CHURCH, Alonzo (1903-1995). "A note on the Entscheidungsproblem." In Journal of Symbolic Logic 1 (1936): 40-41. [With:] "Correction to A note on the Entscheidungsproblem." In Journal of Symbolic Logic 1 (1936): 101-2.
4o. Whole volume, bound with Volume 2 in light blue cloth. Provenance: Richard Bevan Braithwaite (1900-90), with his pencil signature on the front free endpaper. Braithwaite, a British philosopher and logician, was the author of Theory of Games as a Tool for the Moral Philosopher (1955), and of an introduction to the first English translation of Gödel's proof (1962).
A landmark collection that contains papers of the greatest historical
interest by Church, Post, and Turing. 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" in a paper presented in April 1935 ("An unsolvable problem of elementary number theory," American Journal of Mathematics 58 [1936]: 345-63), 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. OOC 250.
[Bound with:] CHURCH. "[Review of] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem." In Journal of Symbolic Logic 2 (1937): 42-43.
Church coined the phrase "Turing machine" in this review of Turing's paper. With regard to Turing's proof of the unsolvability of Hilbert's Entscheidungsproblem, Church acknowledged that "computability by a Turing machine ... has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately-i.e. without the necessity of proving preliminary theorems" (p.43). Church, working independently of Turing, had arrived at his own answer to the Entscheidungsproblem a few months. From Gutenberg to the Internet 7.2; OOC 251.
[With:] POST, Emil Leon (1897-1954). "Finite combinatory processes-formulation 1." In Journal of Symbolic Logic 1 (1936): 103-5. Whole volume, bound with Volume 2 in light blue cloth.
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" (American Journal of Mathematics 58 [1936]: 345-63). Church's paper had answered in the negative Hilbert's question as to whether a definite method existed for proving the truth or falsity of any mathematical statement (the Entscheidungsproblem), but failed to provide the assertion that any such definite 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 a mindless worker operating on an infinite line of "boxes" (equivalent to the Turing machine's "tape"). The worker would be capable only of reading the instructions and performing the following tasks:
(a) Marking the box he is in (assumed empty),
(b) Erasing the mark in the box he is in (assumed marked),
(c) Moving to the box on his right,
(d) Moving to the box on his left,
(e) Determining whether the box he is in, is or is not marked (Hodges 1983, 125).
This range of tasks 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 (see no. 394), and asserting that "the present article ... although bearing a later date, was written entirely independently of Turing's" (p. 103). OOC 356.
[Includes:] TURING. "Computability and \Kl\k-definability." In Journal of Symbolic Logic 2 (1937): 153-63. "The purpose of the present paper is to show that the computable functions introduced by the author [in "On computable numbers"] are identical with the lambda-definable functions of Church and the general recursive functions due to Herbrand and Gödel and developed by Kleene" (p. 153). Turing wrote this paper while at Princeton studying with Church. OOC 395.
4
A landmark collection that contains papers of the greatest historical
interest by Church, Post, and Turing. 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" in a paper presented in April 1935 ("An unsolvable problem of elementary number theory," American Journal of Mathematics 58 [1936]: 345-63), 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. OOC 250.
[Bound with:] CHURCH. "[Review of] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem." In Journal of Symbolic Logic 2 (1937): 42-43.
Church coined the phrase "Turing machine" in this review of Turing's paper. With regard to Turing's proof of the unsolvability of Hilbert's Entscheidungsproblem, Church acknowledged that "computability by a Turing machine ... has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately-i.e. without the necessity of proving preliminary theorems" (p.43). Church, working independently of Turing, had arrived at his own answer to the Entscheidungsproblem a few months. From Gutenberg to the Internet 7.2; OOC 251.
[With:] POST, Emil Leon (1897-1954). "Finite combinatory processes-formulation 1." In Journal of Symbolic Logic 1 (1936): 103-5. Whole volume, bound with Volume 2 in light blue cloth.
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" (American Journal of Mathematics 58 [1936]: 345-63). Church's paper had answered in the negative Hilbert's question as to whether a definite method existed for proving the truth or falsity of any mathematical statement (the Entscheidungsproblem), but failed to provide the assertion that any such definite 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 a mindless worker operating on an infinite line of "boxes" (equivalent to the Turing machine's "tape"). The worker would be capable only of reading the instructions and performing the following tasks:
(a) Marking the box he is in (assumed empty),
(b) Erasing the mark in the box he is in (assumed marked),
(c) Moving to the box on his right,
(d) Moving to the box on his left,
(e) Determining whether the box he is in, is or is not marked (Hodges 1983, 125).
This range of tasks 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 (see no. 394), and asserting that "the present article ... although bearing a later date, was written entirely independently of Turing's" (p. 103). OOC 356.
[Includes:] TURING. "Computability and \Kl\k-definability." In Journal of Symbolic Logic 2 (1937): 153-63. "The purpose of the present paper is to show that the computable functions introduced by the author [in "On computable numbers"] are identical with the lambda-definable functions of Church and the general recursive functions due to Herbrand and Gödel and developed by Kleene" (p. 153). Turing wrote this paper while at Princeton studying with Church. OOC 395.
Further details
For further information about The Origins of Cyberspace Library and to view the reference catalogue, please visit https://www.historyofscience.com.