Computation  

In General > s.a. information; Turing Machine.
* History: The number of applications and people working on them has rapidly increased since around 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; Traub PT(99)may [continuous model]; Foster PT(02)feb, Anderson & Kubiatowicz SA(02)mar, Foster SA(03)apr [grid]; Geroch 09; Moore & Mertens 11 [nature of computation]; Davis 11 [history, logicians from Leibniz to Turing]; Elizalde a1701-ch [theoretical physics and cyberspace].
@ Artificial intelligence: in Sloman 78; Mechner ThSc(98)jan.
@ Future: Gibbs SA(97)jul; Birnbaum & Williams PT(00)jan; Patel qp/05-conf; Post & Votta PT(05)jan.
@ DNA-based computing: Deaton et al PRL(98); Adleman SA(98)aug; Shu et al PRL(11).
@ High-performance computing: Fosdick et al 96; Almeida IJMPA(13)-ln [intro].
@ Related topics: Sinha & Ditto PRL(98) [chaos-based]; Heudin 00 [virtual worlds]; Sterling SA(01)jul [supercomputers]; Hargrove et al SA(01)aug [clusters]; Chatelin 12 [qualitative computing]; > s.a. voronoi diagrams [parallel computations].

Fundamental and Mathematical Aspects > s.a. complexity [classes, including P and NP problems]; 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.
* 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 in(97)qp/99; 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 PhD(04)qp [quantum]; Biamonte JPCS(10)-a0907 [using special-relativistic effects]; news livesci(09)oct, PT(10)apr [speed of quantum evolution]; Markov Nat(14)aug-a1408; Sinitsyn a1701 [speed limit?]; > s.a. quantum effects.
@ 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-conf [at the Planck scale]; Paterek et al NJP(10)-a0811 [and quantum randomness]; Gambini & Pullin IJMPD(08)-a0903 [and quantum gravity]; Aaronson a0910 [BQP and PH]; Moore & Mertens 11; > s.a. Determinism.
@ Thermodynamic view: Bennett IJTP(82); Landauer PT(91)may; Bub SHPMP(01)qp/02 [Maxwell's demon]; Sagawa JSM(14)-a1311-proc [work and heat considerations]; > s.a. Landauer's Principle.

Specific Concepts and Applications > s.a. Algorithms; Lambda Calculus; quantum technology; technology [information technology].
* 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]; Cem Say & Yakaryilmaz a1406 [quantum finite automata]; > s.a. cellular automata.
@ Data management: Nicastro & Calderone ap/07-proc [relational databases in astronomy].
@ Computer graphics: Banchoff 90 [higher dimensions]; > s.a. languages [Mathematica].
> In mathematics: see 2D and 3D manifolds; Extremal Surfaces; geometry; integration; knots and knot invariants; partial differential equations.
> In physics: see causality; computational physics.

The Universe as a Computer > s.a. anthropic principle; 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 the 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 10120 operations, and it can store 1090 bits of information, or 10120 counting gravitational degrees of freedom.
@ General references: Zuse IJTP(82); Fredkin (see Wright 88); Penrose 89; in SA(90)jan; J Brown, NS(90)jul; Lloyd PRL(02); Schmidhuber in(02)qp/00; Cahill GRG(02)gq/01-conf [and information, process physics]; Wolfram 02; Hayes IJTP(03) [implementation challenges]; Coule GRG(04)gq/03 [critical view]; McCabe SGPMP(05) [epistemology and metaphysics]; Svozil CSF(05); Lloyd pw(08)nov; Vaas a0910 [Cosmological Artificial Selection]; Zenil ed-12, a1206 [the Computable Universe]; Beane a1210 + blog tr(12)oct [observable consequences]; Wharton a1211-FQXi [the Universe is not a computer]; Gibbs a1304-FQXi [the Acataleptic Universe]; Horsman et al PRS(14)-a1309 [conditions for computation to be occurring].
@ Quantum computer: Lloyd Compl(97)qp/99; Lloyd 06; D'Ariano a1110-conf, PLA(12) [quantum fields as quantum computers]; Finkelstein a1201-in; Markopoulou LCS(12)-a1201 [and quantum gravity, quantum graphity]; Lloyd ch-a1312; Gudder a1405 [sequential growth model]; Leifer a1405-FQXi ["It from Bit" and the quantum probability rule].

Algebraic / Symbolic 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; Vulcanov gq/00-talk [rev]; Heinicke & Hehl in(02)gq/01 [rev]; d'Inverno GRG(06); Peeters CPC(07)cs.SC/06 [for field theory]; Martín-García et al CPC(07)-a0704 [Invar tensor package]; Anderson & Torre JMP(12)-a1103 [DifferentialGeometry package for Maple]; Bolotin & Poslavsky a1302 [Redberry, a computer algebra system for tensor manipulation].
> Online resources: FORM, http://www.nikhef.nl/~form/ [program for large-scale symbolic manipulation].


main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 19 jan 2017