746
edits
add info
(Discoveries) |
(add info) |
||
| Line 360: | Line 360: | ||
==Discoveries== | ==Discoveries== | ||
The philosopher of computing [[William J. Rapaport|Bill Rapaport]] noted three ''Great Insights of Computer Science'':<ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/computation.html|title=What Is Computation?|publisher=State University of New York at Buffalo|last = Rapaport|first = William J.|date = 20 September 2013}}</ref> | The philosopher of computing [[William J. Rapaport|Bill Rapaport]] noted three ''Great Insights of Computer Science'':<ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/computation.html|title=What Is Computation?|publisher=State University of New York at Buffalo|last = Rapaport|first = William J.|date = 20 September 2013}}</ref> | ||
* [[Gottfried Wilhelm Leibniz]]'s, [[George Boole]]'s, [[Alan Turing]]'s, [[Claude Shannon]]'s, and [[Samuel Morse]]'s insight: there are only ''two objects'' that a computer has to deal with in order to represent "anything".{{refn |group="note"|The word "anything" is written in quotation marks because there are things that computers cannot do. One example is: to answer the question if an arbitrary given computer program will eventually finish or run forever (the [[Halting problem]]).}} | |||
:: All the information about any computable problem can be represented using only 0 and 1 (or any other bistable pair that can flip-flop between two easily distinguishable states, such as "on/off", "magnetized/de-magnetized", "high-voltage/low-voltage", etc.). | |||
{{see also|Digital physics}} | |||
* [[Alan Turing]]'s insight: there are only ''five actions'' that a computer has to perform in order to do "anything". | |||
:: Every algorithm can be expressed in a language for a computer consisting of only five basic instructions:<ref>B. Jack Copeland, 2012. Alan Turing's Electronic Brain: The Struggle to Build the ACE, the World's Fastest Computer. OUP Oxford. p. 107. {{ISBN|978-0-19-960915-4}}.</ref> | |||
::* move left one location; | |||
::* move right one location; | |||
::* read symbol at current location; | |||
::* print 0 at current location; | |||
::* print 1 at current location. | |||
{{see also|Turing machine}} | |||
* [[Corrado Böhm]] and [[Giuseppe Jacopini]]'s insight: there are only ''three ways of combining'' these actions (into more complex ones) that are needed in order for a computer to do "anything".<ref>Charles W. Herbert, 2010. An Introduction to Programming Using Alice 2.2. Cengage Learning. p. 122. {{ISBN|0-538-47866-7}}.</ref> | |||
:: Only three rules are needed to combine any set of basic instructions into more complex ones: | |||
::*''sequence'': first do this, then do that; | |||
::* '' selection'': IF such-and-such is the case, THEN do this, ELSE do that; | |||
::* ''repetition'': WHILE such-and-such is the case, DO this. | |||
:: Note that the three rules of Boehm's and Jacopini's insight can be further simplified with the use of [[goto]] (which means it is more elementary than [[structured programming]]). | |||
{{see also|Structured program theorem}} | |||
=== Answering the question === | === Answering the question === | ||