Computation| 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; 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. complexity; 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 qp/04-PhD
[quantum]; Biamonte a0907 [using
special-relativistic effects]; news livesci(09)oct
[speed of quantum evolution]; > 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-in
[at the Planck scale]; Paterek et al a0811 [and
quantum randomness]; Gambini & Pullin IJMPD(08)-a0903 [and
quantum gravity]; Aaronson a0910 [BQP and PH].
@ Thermodynamic view: Bennett IJTP(82);
Landauer PT(91)may;
Bub SHPMP(01)qp/02 [Maxwell's
demon].
Specific Concepts and Applications > s.a. 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]; > s.a. Cellular
Automaton.
@ 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.
> In mathematics: see 2D and 3D
manifolds; Extremal Surfaces; geometry; knots and knot
invariants; partial
differential equations.
> In physics: see causality; computational
physics.
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 10120 operations, and it can store 1090 bits
of information, or 10120 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 information, 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]; Lloyd pw(08)nov;
Vaas a0910 [Cosmological Artificial Selection].
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 CPC(07)cs.SC/06 [for
field theory]; Martín-García et al CPC(07)-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
29 oct 2009