Difference between revisions of "Computer science"
Jump to navigation
Jump to search
EndreyMark (talk | contribs) m (Adding link to Algorithmic information theory with small text explaining motivation) |
Tomjaguarpaw (talk | contribs) (Deleting page that hasn't been edited for over 10 years) |
||
| Line 1: | Line 1: | ||
| − | ''Computer Science is no more about computers than astronomy is about telescopes''. |
||
| − | |||
| − | -- E. W. Dijkstra |
||
| − | |||
| − | __TOC__ |
||
| − | |||
| − | == Introduction == |
||
| − | |||
| − | Wikipedia's [http://en.wikipedia.org/wiki/Computer_science Computer science]. |
||
| − | |||
| − | [http://www.cs.bham.ac.uk/~mhe/ Martín Escardó] maintains a [http://www.math.niu.edu/~rusin/known-math/index/68-XX.html Computer science] page, being both detailed and comprehensive. The Dijkstra-quotation cited above comes from this page. |
||
| − | |||
| − | [http://mitpress.mit.edu/sicp/full-text/book/book.html Structure and Interpretation of Computer Programs] (by Harold Abelson and Gerald Jay Sussman |
||
| − | with Julie Sussman, foreword by Alan J. Perlis). |
||
| − | |||
| − | == Computability theory == |
||
| − | |||
| − | Wikipedia's [http://en.wikipedia.org/wiki/Computability_theory Computability theory]. |
||
| − | |||
| − | An interesting area related to computabilty theory: [[Exact real arithmetic]]. For me, it was surprising, how it connected problems in mathematical analysis, arithmetic and computability theory. |
||
| − | |||
| − | == To do == |
||
| − | |||
| − | There are several (equivalent) definitions to the concept of ''algorithm'': |
||
| − | * [[Turing machine]] |
||
| − | * [[Combinatory logic]] |
||
| − | * [http://en.wikipedia.org/wiki/Markov_algorithm Markov algorithm] |
||
| − | * [http://en.wikipedia.org/wiki/Post_system Post system] |
||
| − | * [[Recursive function theory]] |
||
| − | * ... |
||
| − | |||
| − | These can be conceived also as computer programming languages -- there should be implemented as many of them as possible. |
||
| − | And some of them can be very good for making such jokes as |
||
| − | * [[Combinatory logic#Self-replication.2C_quines.2C_reflective_programming|self replication programs or self-representing formulas]] |
||
| − | * metacircular interpreters. |
||
| − | At least |
||
| − | * to write a combinatory logic expression which is equivalent to its own quotation (term representation) |
||
| − | * to specify and implement a programming language, which could be seen as an experimentable, playable incarnation of [[recursive function theory]] -- it could yield a playground for learning concepts like [http://www.madore.org/~david/computers/quine.html iteration theorem, recursion theorem, fixed point theorem] |
||
| − | |||
| − | Although there are many differences between [[Combinatory logic]] and recursive function theory, I suspect they have some important common features |
||
| − | * both of them allow us to avoid the concept of variable |
||
| − | * both of them can be used well for metaprogramming |
||
| − | |||
| − | [[Algorithmic information theory]] may exemplify relatedness of computer science to [http://en.wikipedia.org/wiki/Philosophy_of_mathematics philosophical] and [http://en.wikipedia.org/wiki/Foundations_of_mathematics foundational] questions of [[mathematics]]. |
||
| − | |||
| − | [[Category:Theoretical foundations]] |
||