Open main menu

Wikipedia β

Norman Shapiro

Norman Zalmon Shapiro (born 1932) is an American mathematician, who is the co-author of the Rice–Shapiro theorem.


Shapiro spent the summer of 1954 at Bell Laboratories in Murray Hill, New Jersey where, in collaboration with Karel de Leeuw, Ed Moore, and Claude Shannon, he investigated the question of whether providing a Turing machine augmented with an oracle machine producing an infinite sequence of random events (like the tosses of a fair coin) would enable the machine to output a non-computable sequence. The well-known efficacy of Monte Carlo methods might have led one to think otherwise, but the result was negative. Stated precisely:

An infinite string, S, on a finite alphabet is computable if it can be output with probability one by a Turing machine augmented by an oracle machine giving an infinite sequence of equal-probability zeroes and ones.

Moreover, the result continues to hold if the output probability is any positive number, and the probability of an oracle machine inquiry yielding 1 is any computable real number.[1]

Shapiro obtained a BS in Mathematics at University of Illinois in 1952. Shapiro obtained his Ph.D from Princeton University in 1955 under the advisorship of Alonzo Church. In 1955, as a Princeton PhD student, Shapiro coined the phrase "strong reducibility" for a computability theory currently called the many-one reduction. His thesis was titled Degrees of Computability[2] and was published in 1958.

Shapiro was a leading mathematician and computer scientist at the RAND Corporation think tank from 1959 until 1999. In the late 1960s and early 1970s Shapiro was the lead designer of one of the first computer-based mapping and cartography systems.

In the 1970s Shapiro co-designed the MH Message Handling System.[3] MH was the first mail system to utilize Unix design principles by using shell commands to manipulate messages as individual files.

In 1972, Norman Z. Shapiro was a creative lead in his essays on e-mail etiquette, introducing concepts that were rarely considered until over 15 years later. His work may be the first substantial writing about netiquette. The primary essay was "Toward an Ethics and Etiquette for Electronic Mail".[4]

In the 1970s through 1990s Shapiro developed many new and unique contributions to computer science, mathematics, and modeling. One contribution was his co-invention of a new programming language called Abel (later called RAND-ABEL). This was certainly not the first A.I. style simulation language to look and read like English. It was more clear and readable by non-programmers than its predecessors, but the main innovation was the execution as code of tables that read to the human like any normal table one would find in a magazine article or essay. The ABEL compiler uses these "English" tables in multiple ways: as data values, as a decision tree, or as a complex conditional and value setting function. This was the first time natural language tables have been machine-executed in this manner.

Shapiro has written extensively on databases and privacy, the effects of automation on the court system, the future of automation, and on topics in mathematics, chemistry, and biology. Much of his work is available as full text PDFs at no charge from the publisher, RAND Corporation.


  1. ^ K. de Leeuw, E.F. Moore, C.E. Shannon, and N. Shapiro, "Computability by Probabilistic Machines." Automata Studies, Shannon, C. and J. McCarthy, eds., Princeton University Press 1956, pp. 183-212.
  2. ^ Norman Shapiro at the Mathematics Genealogy Project
  3. ^ Anderson, Robert H., Norman Shapiro, Tora K. Bikson and Phyllis Kantar. "The Design of the MH Mail System". Santa Monica, CA: RAND Corporation, 1989. Also available in print form.
  4. ^ Shapiro, Norman and Robert H. Anderson. "Toward an Ethics and Etiquette for Electronic Mail". Santa Monica, CA: RAND Corporation, 1985. Also available in print form.

External linksEdit