Jump to content

Norman Shapiro

From Wikipedia, the free encyclopedia
Norman Shapiro
Born(1932-01-28)January 28, 1932
DiedOctober 14, 2021(2021-10-14) (aged 89)
Alma mater
Known for
SpouseNaomi Shapiro
Scientific career
InstitutionsRAND Corporation
Thesis Degrees of Computability  (1958)
Doctoral advisorAlonzo Church

Norman Zalmon Shapiro was an American mathematician, who was the co-author of the Rice–Shapiro theorem.



Shapiro obtained a BS in mathematics at University of Illinois in 1952.

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 his Ph.D. from Princeton University in 1955 under the advisership 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. In the early 1980s, he was the software architect for large and complex game-structured simulation (the RAND Strategy Assessment System) at the RAND Corporation. That represented regional or global crisis and war with agents optionally substituting for human teams in making high-level decisions. These decisions then directed actions represented in a large global combat model. Different versions of the agents could be substituted (e.g., to reflect a change in government). Agents could run the simulation within itself to test potential strategies with "lookahead." The system was successfully implemented [5] and was used in the late 1980s before the end of the Cold War. As part of the subsequent development, Shapiro co-invented (with H. Edward Hall) a new programming language called Abel (later called RAND-ABEL). This was not the first A.I. style simulation language to look and read like English, but it was clearer and more readable by non-programmers than its predecessors. The main innovation of ABEL 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 wrote 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. https://www.rand.org/pubs/notes/N3017. 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. https://www.rand.org/pubs/reports/R3283. Also available in print form.
  5. ^ Davis, Paul K. and H. Edward Hall, "Overview of RSAS System Software." Santa Monica, CA: RAND Corporation, 1988. https://www.rand.org/content/dam/rand/pubs/notes/2009/N2755.pdf.