Computation

In General > s.a. information; Turing Machine.
* History: The number of applications and people working on them has rapidly increased since ca. 1986.
* Remark: For some problems, the connection machine is 100–1000 times faster than a Cray machine.
* Applications: Fluid dynamics; artificial vision; weather; astrophysics; chemistry.
@ General references: Hopcroft & Ullman 79; Dreitlein FP(93); Eck 95 [survey]; Feynman 96; Wong 97 [methods]; Traub PT(99)may [continuous model]; Foster PT(02)feb, Anderson & Kubiatowicz SA(02)mar, Foster SA(03)apr [grid].
@ Artificial intelligence: in Sloman 78; Mechner ThSc(98)jan.
@ Future: Gibbs SA(97)jul; Birnbaum & Williams PT(00)jan; Patel qp/05-in; Post & Votta PT(05)jan.
@ Related topics: Fosdick et al 96 [high-performance]; Deaton et al PRL(98), Adleman SA(98)aug [DNA-based]; Sinha & Ditto PRL(98) [chaos-based]; Sterling SA(01)jul [supercomputers]; Hargrove et al SA(01)aug [clusters]; Heudin 04 [virtual worlds].

Fundamental and Mathematical Aspects > s.a. Domain; quantum computers.
* Decidability: Any finite set is algorithmically decidable, any uncountably infinite one is not; For countably infinite sets, there are examples of both types.
* Computational complexity: The study of how the computation time scales with the size of the input; There are different classes, including BQP and NP.
* NP problems: There is no known algorithm that will solve them in polynomial time; Non-deterministic methods (evolutionary search and quantum computers) have been proposed.
* Thermodynamic view: It appears in explaining why Maxwell's demon doesn't violate the second law; There is no unavoidable energy consumption, if we use a reversible computer and go slowly enough.
@ Physical limitations: Feynman FP(86); Schmidhuber qp/99-in; Lloyd Nat(00)qp/99; Deutsch et al m.HO/99 [proofs]; Ng PRL(01)gq/00; Ozhigov qp/03; Krauss & Starkman ap/04/PRL [and cosmology]; Aaronson qp/04-PhD [quantum].
@ Computability, undecidability: Pour-El & Richards IJTP(82) [in physical phenomena], 89; Kanter PRL(90); Moore PRL(90); Bennett Nat(90)aug; Svozil PLA(90); Kieu CP(03)qp/02, qp/02-in [quantum]; Zizzi gq/04-in [at the Planck scale].
@ NP completeness: Garey & Johnson 79; Greenwood qp/00-in [methods]; Nussinov & Nussinov cm/02 [approach to graph problems]; Mao PRA(05)qp/04 [polynomial t in quantum computers]; Aaronson qp/05 [and physical reality]; Zak & Fijany PLA(05) [using quantum resonances]; Rojas qp/06 [interpolating problem with BQP]; > s.a. statistical mechanics.
@ Thermodynamic view: Bennett IJTP(82); Landauer PT(91)may; Bub SHPMP(01)qp/02 [Maxwell's demon]; > s.a. complexity.

Specific Concepts > s.a. Lambda Calculus; quantum technology; technology [information technology].
@ Data management: Nicastro & Calderone ap/07-in [relational databases in astronomy].
@ Computer graphics: Banchoff 90 [higher dimensions]; > s.a. languages [Mathematica].
@ Randomized algorithms, probabilistic methods: Mitzenmacher & Upfal 05.

Applications > s.a. causality; computational physics.
* In mathematics: Some proofs are too long to be done by hand and computers can help, but many mathematicians don't find proofs by computer to be satisfactory (> see Four-Color Problem, spheres); Other mathematicians argue for an even more extensive use, and "automated reasoning" computer programs, because of they can spare humans vast amounts of tedious work, and they can follow paths that are totally counterintuitive to humans.
@ Automata: Peres PLA(84) [and quantum mechanics]; Svozil & Zapatrin IJTP(96)qp/95 [logic]; > s.a. Cellular Automaton.
> In mathematics: see 2D and 3D manifolds; Extremal Surfaces; geometry; knots and knot invariants; partial differential equations.

The Universe as a Computer > s.a. black holes; information; physics; standard model.
* Idea: Every process, every change that takes place in the Universe, is a kind of computation.
* Proponents: In the 1940s, computer pioneer Konrad Zuse began to speculate that the universe might be nothing but a giant computer continually executing formal rules to compute its own evolution; J A Wheeler ("It from Bit"), S Lloyd, S Wolfram.
* Objections: (1) Computers are too limited – not true, see Turing machine; (2) Computations are irreversible – not really, reversible ones are theoretically possible; (3) Computers cannot simulate consciousness – can't they?
* Estimates: Since time began, the Universe can have performed up to 10¹²⁰ operations, and it can store 10⁹⁰ bits of information, or 10¹²⁰ counting gravitational degrees of freedom.
@ References: Zuse IJTP(82); Fredkin (see Wright 88); Penrose 89; in SA(90)jan; J Brown, NS(90)jul; Lloyd Compl(97)qp/99 [quantum], PRL(02); Schmidhuber qp/00-in; Cahill GRG(02)gq/01-in [and info, process physics]; Wolfram 02; Hayes IJTP(03) [implementation challenges]; Coule gq/03 [critical view]; McCabe SGPMP(05) [epistemology and metaphysics]; Svozil CSF(05); Lloyd 06 [quantum computer].

Algebraic Computing (especially in general relativity) > s.a. numerical relativity.
* Relationships: Algebraic computing is different from numerical work in storage needs, intermediate expression swell, simplification, control substitution.
@ General references: d'Inverno GRG(75); Harper et al 91; Fitch PW(93)jun; Stauffer et al 93; MacCallum et al 95; Hereman PW(96); Socorro et al CPC(98)gq; McCrea; Vulcanov gq/00-in [rev]; Heinicke & Hehl in(02)gq/01 [rev]; d'Inverno GRG(06); Peeters cs.SC/06 [for field theory]; Martín-García et al a0704 [Invar tensor package].
> Online resources: FORM, http://www.nikhef.nl/~form/ [program for large scale symbolic manipulation].

Main page – Abbreviations – Journals – Comments – Other sites – Acknowledgements
Send feedback and suggestions to bombelli at olemiss.edu – Modified 5 jul 2008