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; Wong 97 [methods]; 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. 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.
* Computational complexity:
The study of how the computation time scales with the size of the input; There
are different classes, including BQP and NP.
* NP problems: There
is no known algorithm that will solve them in polynomial time; Non-deterministic
methods (evolutionary search and quantum
computers)
have been proposed.
* 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 qp/99-in;
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].
@ 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].
@ NP completeness: Garey & Johnson 79; Greenwood qp/00-in
[methods]; Nussinov & Nussinov cm/02 [approach
to graph problems]; Mao PRA(05)qp/04 [polynomial t in
quantum computers]; Aaronson qp/05 [and
physical reality]; Zak & Fijany PLA(05)
[using quantum resonances]; Rojas qp/06 [interpolating
problem with BQP]; > s.a.
statistical mechanics.
@ Thermodynamic view: Bennett IJTP(82);
Landauer PT(91)may;
Bub SHPMP(01)qp/02 [Maxwell's
demon]; > s.a. complexity.
Specific Concepts > s.a. Lambda
Calculus; quantum
technology; technology [information technology].
@ 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.
Applications > s.a. causality; computational
physics.
* 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.
> In mathematics: see 2D and 3D
manifolds; Extremal Surfaces; geometry; knots and knot
invariants; partial
differential equations.
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 info, 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].
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 cs.SC/06 [for
field theory]; Martín-García et al 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
5 jul 2008