Item #28971 Computability by Probabilistic Machines - Cases 22108 & 20878 [reproduced typescript]. K. de Leeuw, E. F. Moore, C. E. Shannon, N. Shapiro, Karl, Edward, Claude Elwood.
Computability by Probabilistic Machines - Cases 22108 & 20878 [reproduced typescript]
Computability by Probabilistic Machines - Cases 22108 & 20878 [reproduced typescript]

Computability by Probabilistic Machines - Cases 22108 & 20878 [reproduced typescript]

[New York, NY]: Bell Telephone Laboratories, Incorporated October 21, 1954. [1], [1]-15, [1-bibliography] + [1]-23 (appendix) leaves. 10 7/8 x 8 3/8 inches (275 x 215 mm). Reproduced typescript. Minor edge staining, last few leaves with some dampstaining; four holes punched near the spine, and stapled upper left. Corner badly bumped lower left corner with textblock creased. Very Good. Wraps. [28971]


Abstract: "This memorandum studies the action of Turing-type computing machines whose operation can be made to depend on the output of a random device. Their ability to perform certain tasks is contrasted with the ability of deterministic machines to perform these tasks." The Introduction further notes: The following question will be answered in this paper: Is there anything that can be done by a machine with a random element but not by a deterministic machine?...the main body of the paper consists of definitions, examples, and statements of results. The proofs are deferred to the appendix since they consist in the most part of more or less elaborate constructions which are not absolutely essential for an understanding of the results."

Automata Studies (Vol. 34, Princeton University Press, 1956) first formally published the paper, one of four related to Turing machines in that issue. In their introduction, John McCarthy and Claude Shannon note this paper "investigate[s] whether machines with random elements can compute anything uncomputable by ordinary Turing machines."

Sloane and Wyner #94 references Memorandum MM-54-114-37. This example adds Memorandum MM-54-133-63. Thirty-three Bell Labs scientists were on the distribution list.

PROVENANCE: The personal files of Claude E. Shannon (unmarked). One of two examples of this item in Shannon's files.

REFERENCES:
Sloane and Wyner, "Claude Elwood Shannon Collected Papers," #94
Sloane and Wyner, "Claude Elwood Shannon Collected Papers," #91 (Automata Studies)

ITEM SOLD

Create a want for this item, and we will notify you via e-mail if another copy becomes available.