Norman Shapiro
Encyclopedia
Norman Z. Shapiro 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 method
s
might have led one to think otherwise,
but the result was negative.
Stated precisely:
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.
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"
to describe a concept of computability theory currently called the Many-one reduction
.
His thesis was titled Degrees of Computability
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
(think Google Earth).
In the 1970s Shapiro co-designed the MH Message Handling System
.
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.
See Netiquette
.
His work may be the first substantial writing about Netiquette.
The primary essay was "Toward an Ethics and Etiquette for Electronic Mail".
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 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.
See misc research in References below.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
,
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
Karel de Leeuw
Karel deLeeuw, or de Leeuw , was a mathematician at Stanford University, specializing in harmonic analysis and functional analysis. He received his doctorate at Princeton in 1954 under Emil Artin...
,
Ed Moore
Edward F. Moore
Edward Forrest Moore was an American professor of mathematics and computer science, the inventor of the Moore finite state machine, and an early pioneer of artificial life....
, and
Claude Shannon,
he investigated the question of whether providing a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
augmented with an oracle machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
producing an infinite sequence of random events
(like the tosses of a fair coin
Fair coin
In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin. One for which the probability is not 1/2 is called a biased or unfair coin...
)
would enable the machine to output a non-computable sequence.
The well-known efficacy of Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
s
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 machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
augmented by an oracle machineOracle machineIn complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
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.
Shapiro obtained a BS in Mathematics at University of Illinois in 1952.
Shapiro obtained his Ph.D from Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
in 1955 under the advisorship of Alonzo Church
Alonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
.
In 1955, as a Princeton PhD student, Shapiro coined the phrase "strong reducibility"
to describe a concept of computability theory currently called the Many-one reduction
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
.
His thesis was titled Degrees of Computability
and was published in 1958.
Shapiro was a leading mathematician and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
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
(think Google Earth).
In the 1970s Shapiro co-designed the MH Message Handling System
MH Message Handling System
The MH Message Handling System is a free, open source e-mail client. It is different from almost all other mail reading systems in that, instead of a single program, it is made from several different programs which are designed to work from the command line provided by the shell on Unix-like...
.
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.
See Netiquette
Netiquette
Netiquette is a set of social conventions that facilitate interaction over networks, ranging from Usenet and mailing lists to blogs and forums. These rules were described in IETF RFC 1855. However, like many Internet phenomena, the concept and its application remain in a state of flux, and vary...
.
His work may be the first substantial writing about Netiquette.
The primary essay was "Toward an Ethics and Etiquette for Electronic Mail".
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 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
Privacy
Privacy is the ability of an individual or group to seclude themselves or information about themselves and thereby reveal themselves selectively...
,
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.
See misc research in References below.