Computation: Finite and Infinite Machines

by Marvin Minsky

Man has within a single generation found himself sharing the world with a strange new the computers and computer-like machines. Neither history, nor philosophy, nor common sense will tell us how these machines will affect us, for they do not do "work" as did machines of the Industrial Revolution. Instead of dealing with materials or energy, we are told that they handle "control" and "information" and even "intellectual processes." There are very few individuals today who doubt that the computer and its relatives are developing rapidly in capability and complexity, and that these machines are destined to play important (though not as yet fully understood) roles in society's future. Though only some of us deal directly with computers, all of us are falling under the shadow of their ever-growing sphere of influence, and thus we all need to understand their capabilities and their limitations. It would indeed be reassuring to have a book that categorically and systematically described what all these machines can do and what they cannot do, giving sound theoretical or practical grounds for each judgment. However, although some books have purported to do this, it cannot be done for the following a) Computer-like devices are utterly unlike anything which science has ever considered---we still lack the tools necessary to fully analyze, synthesize, or even think about them; and b) The methods discovered so far are effective in certain areas, but are developing much too rapidly to allow a useful interpretation and interpolation of results. The abstract theory---as described in this book---tells us in no uncertain terms that the machines' potential range is enormous, and that its theoretical limitations are of the subtlest and most elusive sort. There is no reason to suppose machines have any limitations not shared by man.

Genres: Computer Science, Computers, Philosophy, Science, Technology, Artificial Intelligence, Programming

317 pages, Hardcover

First published June 1, 1967

About the author

Marvin Lee Minsky (born August 9, 1927) was an American cognitive scientist in the field of artificial intelligence (AI), co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy. Marvin Lee Minsky was born in New York City to an eye surgeon and a Jewish activist, where he attended The Fieldston School and the Bronx High School of Science. He later attended Phillips Academy in Andover, Massachusetts. He served in the US Navy from 1944 to 1945. He holds a BA in Mathematics from Harvard (1950) and a PhD in mathematics from Princeton (1954). He has been on the MIT faculty since 1958. In 1959 he and John McCarthy founded what is now known as the MIT Computer Science and Artificial Intelligence Laboratory. He is currently the Toshiba Professor of Media Arts and Sciences, and Professor of electrical engineering and computer science.

Reviews

[David · Rating 4 out of 5]

This took a while to complete! Minsky's writing is very clear and conversational, but the material is extremely dense. Both the breadth and depth of the material covered is pretty incredible: from defining what a "machine" is in the sense of computer science (and the general idea of computability a la Turing) and simple finite state machines, to symbolic generation of sequences (Emil Post and Kleene).

Most of the content revolves around mathematical representations using the Latin and Greek alphabets. However, Minsky defines all terms and the material builds upon itself so that you can work out every single problem yourself with this book and pencil and paper (and a whole lot of quiet time). No other reference is needed. It reminds me of Knuth's The Art of Computer Programming in this regard.

This book will not teach you how to program computers, but it is certainly possible to make connections between the extremely abstract and fundamental subjects in this book and certain areas of practical computing, such as compiler development.

Probably the most valuable thing a modern reader will get out of this book is an understanding of the fundamentals of computer science which were largely fleshed out in the early 1900s. Multiple overlapping ideas and approaches (Turing, Post, Kleene) are all woven into a single narrative so that you end up approaching ideas like recursion in several different ways. You have to admire the work that went into this book!

I think it's worth thinking about computability at least once. For a much easier introduction, I recommend "The Annotated Turing" by Charles Petzold (yes, the same Petzold who authored the colossal tome "Programming Windows"!)