# Computer science

### From HaskellWiki

EndreyMark (Talk | contribs) m (Categorizing: Category:Theoretical foundations. Table of contents.) |
EndreyMark (Talk | contribs) m (Adding link to Algorithmic information theory with small text explaining motivation) |
||

(6 intermediate revisions by one user not shown) | |||

Line 1: | Line 1: | ||

+ | ''Computer Science is no more about computers than astronomy is about telescopes''. | ||

+ | |||

+ | -- E. W. Dijkstra | ||

+ | |||

__TOC__ | __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 11: | 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]] | [[Category:Theoretical foundations]] |

## Latest revision as of 18:35, 5 August 2006

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

-- E. W. Dijkstra

## Contents |

## [edit] 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).

## [edit] 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.

## [edit] 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

Algorithmic information theory may exemplify relatedness of computer science to philosophical and foundational questions of mathematics.