Computation| 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 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];
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