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 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].

@ __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 page – abbreviations – journals – comments – other
sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified
14 oct 2017