

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/knownmath/index/68XX.html Computer science] page, being both detailed and comprehensive. The Dijkstraquotation cited above comes from this page.
 
− 
 
−  [http://mitpress.mit.edu/sicp/fulltext/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#Selfreplication.2C_quines.2C_reflective_programmingself replication programs or selfrepresenting 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]]
 