Difference between revisions of "Computer science"
EndreyMark (talk | contribs) (Filling with the most important links. Originally it was Martín Escardó's Computer Science page which made me to create a wikipage on this topic.) |
EndreyMark (talk | contribs) m (Adding link to Algorithmic information theory with small text explaining motivation) |
||
| (7 intermediate revisions by the same user not shown) | |||
| 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]. |
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. |
+ | [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 |
[http://mitpress.mit.edu/sicp/full-text/book/book.html Structure and Interpretation of Computer Programs] (by Harold Abelson and Gerald Jay Sussman |
||
| Line 9: | Line 17: | ||
Wikipedia's [http://en.wikipedia.org/wiki/Computability_theory 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]] |
||
Revision as of 18:35, 5 August 2006
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
Introduction
Wikipedia's Computer science.
Martín Escardó maintains a Computer science page, being both detailed and comprehensive. The Dijkstra-quotation cited above comes from this page.
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 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:
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
- 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 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 philosophical and foundational questions of mathematics.