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__: Landauer PT(70)jul;
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];
news Phy(18)dec [analog computing with wi-fi waves];
> s.a. voronoi diagrams [parallel computations].

**Fundamental and Mathematical Aspects**
> s.a. complexity [classes, including P and NP problems];
Domain; quantum computers.

* __Algorithmic decidability__: Any finite
set is algorithmically decidable, any uncountably infinite one is not; For countably
infinite sets, there are examples of both types; Quantum entanglement provides a way
to verify the solutions to a broad class of problems, including some that are
impossible to solve (MIP* = RE).

* __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;
Geroch & Hartle FP(86)-a1806;
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;
Ji et al a2001
+ news sn(20)jan [MIP* = RE];
> 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];
Philathong et al a1906
[algorithmic or computational phase transition in resources required];
> 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];
Pruneau 17 [analyzing large data sets].

@ __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 10^{120}
operations, and it can store 10^{90} bits of
information, or 10^{120} 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];
news Cosm(17)oct,
s.a. Cosm(17)oct [we're not living in a computer simulation];
Lévay & Holweck a1812 [spacetime as an error-correcting code];
Bibeau-Delisle & Brassard a2008 [on living inside a computer simulation].

@ __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];
Brewin a1912 [Cadabra, for tensor manipulation].

> __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 2 oct 2020