Difference between revisions of "Computer science"

From HaskellWiki
Jump to: navigation, search
m (Adding link to Algorithmic information theory with small text explaining motivation)
(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]]
 

Revision as of 11:59, 6 February 2021