Information Technology Reference
In-Depth Information
The Lambda Calculus
Also in 1936, Alonzo Church formally described algorithms using a theory of functions
called the lambda calculus . This study motivated the development of the LISP program
ming language, now used extensively in the field of artificial intelligence. Remarkably,
the lambda calculus also has the same power as Turing Machines.
All of these comments lead to the same basic conclusion that al
though computers may have various forms and descriptions, they all
have the same basic computational power. This circumstance is
sometimes described as the universality of computers . Each type of
machine is universal, in that any computer can perform any compu
tational task. The Computer Science and Telecommunications
Board of the National Research Council notes that this notion of
universality has several important implications:
No computational task is so complex that it cannot be de
composed into instructions suitable for the most basic
computer.
The instruction repertoire of a computer is largely unimpor
tant in terms of giving it power since any missing instruction
types can be programmed using the instructions the machine
does have.
Computers differ by how quickly they solve a problem, not
whether they can solve the problem.
Programs, which direct the instructionfollowing components
of a computer to realize a computation, are the key.
(From Being Fluent with Information Technology , National
Academy Press, 1999, pp. 31-32.)
If all computers are universal, how do they differ?
As we have discussed, the principle of universality means that all
basic modern computers can solve the same problems and run the
same algorithms. We cannot distinguish among machines on the ba
sis of their fundamental capabilities. Does this mean you might as
well return your new Macintosh PowerBook computer and bring
 
Search WWH ::




Custom Search