m (Creating new wikipage Recursive function theory by making this word a link to it)
m (Adding link to Algorithmic information theory with small text explaining motivation)
Latest revision as of 18:35, 5 August 2006
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
 1 Introduction
Wikipedia's Computer science.
Structure and Interpretation of Computer Programs (by Harold Abelson and Gerald Jay Sussman with Julie Sussman, foreword by Alan J. Perlis).
 2 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.
 3 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.
- 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