?

Log in

No account? Create an account

Previous Entry | Next Entry

I really like Michael Mahoney's papers on the history of computing. I wish I'd had access to this kind of information when I was an undergraduate. It would have cleared up a lot of confusion.

The most recent paper I've read explores the history of the mathematics of computer science, or how computer science theory came to be. It reveals a lot about why I struggled with some concepts. For example, a quote from John von Neumann on the theory of automata:

"There exists today a very elaborate system of formal logic, and, specifically, of logic as applied to mathematics. This is a discipline with many good sides, but also with certain serious weaknesses. This is not the occasion to enlarge upon the good sides, which I certainly have no intention to belittle. About the inadequacies, however, this may be said: Everybody who has worked in formal logic will confirm that it is one of the technically most refractory parts of mathematics. The reason for this is that it deals with rigid, all-or-none concepts, and has very little contact with the continuous concept of the real or of the complex number, that is, with mathematical analysis. Yet analysis is the technically most successful and best-elaborated part of mathematics. Thus formal logic is, by the nature of its approach, cut off from the best cultivated portions of mathematics, and forced onto the most difficult part of the mathematical terrain, into combinatorics."

"The theory of automata, of the digital, all-or-none type, as discussed up to now, is certainly a chapter in formal logic. It will have to be, from the mathematical point of view, combinatory rather than analytical".


The all-or-nothing, non-analytical nature of the theory of computation has always been troubling to me. Also, if you recall, I had an exchange with nsingman last year about his experiences in CS theory, in which he said that he found it algebraic in nature. He is correct. The things I had more success in, such as Euclidean and affine geometry, are analytical in nature.

Von Neumann notes the combinatory nature of automata theory as well. As you might guess, combinatorics gives me problems for similar reasons. I even bought a combinatorics book for CS theory problem solving practice during my first year of grad school. It didn't help as much as I'd hoped it would (although it probably kept me from failing).

On a somewhat related note, I am starting to wonder if the theory of computation is a useful subject for software engineers to study (although I think it is essential for computer scientists). At least in the contemporary concept of what a software engineer is, there is far less need for the ability to do things like prove problems NP-complete, or undecidable, or not recognizable by a regular expression. Also, the ability to do these things does not lend itself to a broader acquisition of the detailed knowledge a software engineer must know (at least at an interview). Just because one can prove some language is not regular does not reveal the algorithm recognizing it. Knowing the algorithm is of far more value today, at least on interviews.

(I hope that I am not burned someday by failing to answer a theory of computation question because I was spending more time on algorithms.)

Tags:

Latest Month

December 2017
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      
Powered by LiveJournal.com
Designed by Tiffany Chow