Ask HN: Which of our ideas about computation could survive a thousand years?

8 points

6 years ago

A passage in the preface to SICP [1] on the real meaning of computer science has captured my imagination ever since I’ve read it:

    The computer revolution is a revolution in the way we think 
    and in the way we express what we think. 
    The essence of this change is the emergence of what 
    might best be called procedural epistemology -- the 
    study of the structure of knowledge from an imperative 
    point of view, as opposed to the more declarative point 
    of view taken by classical mathematical subjects. 
    Mathematics provides a framework for dealing precisely 
    with notions of ``what is.'' Computation provides a 
    framework for dealing precisely with notions of ``how to.''

In this spirit, I’ve compiled a list of ideas about computation that I think could remain relevant in a thousand years. I’ve written a short justification for each item and I’m wondering what HN would add to or remove from this list.

1. Entscheidungsproblem, Halting problem, Gödel's incompleteness theorems: Fundamental limitations of formal knowledge.

2. P != NP: A contradictory proof is unlikely and the distinction remains relevant for quantum computing.

3. Lambda calculus and combinatory logic: Richest model of computation available today.

4. First-class continuations: Every stateful program must have continuations. First-class continuations let programs write themselves.

5. Fixed points: Find equilibrium in complex systems.

6. Random variable: Universal abstraction to represent input to a procedure.

7. Interventional distributions: Capture causality under uncertainty.

8. Distributed representations: Versatile representations of patterns.

9. Church encoding: The purity of a system where everything is represented in terms of procedures is intriguing.

10. Principle of computational equivalence: We can represent everything as a computation. (Big if true!)

[1] Source: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-7.html

4 comments

The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology -- the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of ``what is.'' Computation provides a framework for dealing precisely with notions of ``how to.''