Personal tools

Computer science

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Changing the order of the table-of-contents and the Dijkstra-motto)
(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)
Line 20: Line 20:
 
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.
 
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
 
[[Category:Theoretical foundations]]
 
[[Category:Theoretical foundations]]

Revision as of 19:44, 22 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

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