# Computer science

### From HaskellWiki

EndreyMark (Talk | contribs) (New section - →To do: : implementing the different approaches of concept of algorithm as programming languages, and using them in teaching foundations of mathematics and metaprogramming) |
EndreyMark (Talk | contribs) m (Creating new wikipage Recursive function theory by making this word a link to it) |
||

Line 27: | Line 27: | ||

* [http://en.wikipedia.org/wiki/Markov_algorithm Markov algorithm] | * [http://en.wikipedia.org/wiki/Markov_algorithm Markov algorithm] | ||

* [http://en.wikipedia.org/wiki/Post_system Post system] | * [http://en.wikipedia.org/wiki/Post_system Post system] | ||

− | * Recursive function theory | + | * [[Recursive function theory]] |

* ... | * ... | ||

Line 36: | Line 36: | ||

At least | At least | ||

* to write a combinatory logic expression which is equivalent to its own quotation (term representation) | * 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] | + | * 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 | Although there are many differences between [[Combinatory logic]] and recursive function theory, I suspect they have some important common features |

## Revision as of 09:23, 23 April 2006

*Computer Science is no more about computers than astronomy is about telescopes*.

-- E. W. Dijkstra

## Contents |

## 1 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).

## 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.

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