Computer science
From HaskellWiki
m (Changing the order of the table-of-contents and the Dijkstra-motto) |
m (Adding link to Algorithmic information theory with small text explaining motivation) |
||
| (2 intermediate revisions not shown.) | |||
| Line 19: | Line 19: | ||
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 | ||
| + | |||
| + | [[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]] | ||
Current revision
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
Algorithmic information theory may exemplify relatedness of computer science to philosophical and foundational questions of mathematics.
