Topics:
Here is a list (probably too large) of things we may cover:
- Church's thesis:
My proof
(an auxiliary figure)
Church's (weak) thesis is false for N Newtonian point masses
but becomes (strongly) true for relativistic non-point masses
- Information and entropy :
- E.T. Jaynes.
Information theory and statistical mechanics,
Physical Review, 106,4 (May 1957) 620-630.
- limits on bit rate and bit density from thermodynamics and
other arguments
- N.H.Margolus & L.B.Levitin:
The maximum speed of dynamical evolution,
(T. Toffoli, M. Biafore, and J. Leao, eds.) PhysComp96, pages 208-211.
- J.D. Bekenstein:
Energy cost of information transfer,
Physical Review Letters}, 46:623--626, 1981.
- J.D. Bekenstein:
Universal upper bound on entropy-to-energy ratio for bounded systems,
Physical Review D, 23(2) (January 1981) 287-298.
- J.D. Bekenstein:
Entropy content and information flow in systems with limited energy,
Physical Review D, 30,8 (1984) 1669-1679.
- W.D. Smith:
Fundamental physical limits on information storage
- W.D. Smith:
Fundamental physical limits on information flux
- reversible computing - no power needed (?)
- C.H.Bennett: Time/space trade-offs for reversible computation, SIAM J. Computing, 18,4 (1989) 766-776.
- R.Y.Levine & A.T. Sherman:
A Note on Bennett's Time-Space Tradeoff for Reversible Computation,
SIAM J. on Computing 19,4 (1990) 673-677.
- C.H.Bennett: Demons, engines, and the second law,
Scientific American (1987) 108-116.
- C.H.Bennett & Rolf Landauer: The Fundamental Limits of Computation, Scientific American(July 1985) 48-56 (38-53 in some versions).
- C.H.Bennett: Notes on the History of Reversible Computation, IBM J. Research and Development 32,1 (1988) 16-23.
- C.H.Bennett: The logical reversibility of computation, IBM J. Res. Devel. 6 (1979) 525-532. IBM JR&D 17 (1973) 525-532.
- C.H.Bennett: Thermodynamics of computation, a review, Int.J.Theor.Phys. 21 (1982) 905-940. (Special issue on computation.)
- E.Fredkin & T.Toffoli: Conservative logic, Int.J.Theor.Phys. 21 (1982) 219-253.
- T.Toffoli: Bicontinuous extensions of invertible combinatorial functrions,
Math.Systems Theory 14 (1981) 13-23.
- L.Priese: On a simple combinatorial structure sufficient for
studying nontrvial self reproduction, J.Cybernetics 6 (1976) 101-137.
- Knight's reversible CMOS logic papers here e.g.
Younis, S.G. and Knight, Jr., T.F.:
Asymptotically Zero Energy Split-Level Charge Recovery Logic,
International Workshop on Low Power Design (1994) 177-182.
- Knight's ideas date to "Hot clock nMOS" by C.L.Seitz et al Chapel hill conference on VLSI 1 (1985), and discussed in Feynman's book.
- P.Benioff: Quantum mechanical models of Turing machines that dissipate no energy, Phys.Rev.Lett. 48 (1982) 1581-1585.
- error correcting codes - Spielman's computationally efficient codes
- reliable computing with unreliable computational elements
- Spielman: Highly Fault-Tolerant Parallel Computation
- Spielman & Sipser: expander codes
- Spielman: Linear-time encodable and decodable ECCs
- R.L. Dobrushin and S.I. Ortyukov:
Upper bound for the redundancy of self-correcting arrangements of
unreliable functional elements,
Prob. Info. Transmission 13 (1977) 203-218.
- Toom and Gacs ??
- P.Gacs:
Reliable computation with cellular automata,
J. Computer Systems Sci., 32(32) (1986) 15-78.
- P.Gacs & J.Reif.
A simple 3d real-time reliable cellular array,
J. Computer Systems Sci. 36 (1986) 125-147.
- N.Pippenger:
Developments in the synthesis of reliable organisms from unreliable
components,
In J.Glimm, J.Impagliazzo, and I.Singer, editors: The legacy
of John von Neumann, volume 50 of Proc. symp. pure math., AMS, 1990.
- N.Pippenger:
On networks of noisy gates,
Proc. IEEE Symp. Foundations of Computer Sci., 26 (1985) 30-38.
- N.Pippenger:
Reliable computation by formulas in the presence of noise,
IEEE Trans. Info. Theory, IT-34,2 (1988) 194-197.
- Cellular Automata
- Tommaso Toffoli: Computation and Construction Universality of Reversible Cellular Automata, JCSS 15,2 (1977) 213-231.
- VLSI theory
- B.M. Chazelle and L.Monier.
A model of computation for VLSI with related complexity results,
Journal of the ACM, 32,3 (1985) 573-588.
- G.Bilardi, M.Pracchi, F.P.Preparata:
A critqiue of network speed in VLSI models of computation,
IEEE J. solid state circuits SC-17 (Aug. 1982) 696-702.
- Henessy & Paterson: computer arithmetic appendix???
- Thomas Lengauer: VLSI theory,
836-868 in J.van Leeuwen, editor: Handbook of theoretical computer
science volume A, MIT Press, 1990.
- J.Vuillemin:
A combinatorial limit to the computing power of VLSI circuits,
IEEE Trans. Computers C-32, 3 (March 1983) 294-300.
- mechanical systems made of rigid parts - their computational power
- quantum computers:
- Quantum error correcting codes;
- Quantum "purification" and "teleportation";
- C.H. Bennett, G. Brassard, C. Cripeau, R. Jozsa, A. Peres, and W. Wootters:
Teleporting an unkown quantum state by dual classical and EPR channels.
Physical Review Letter , 70:1895-1898, 1993.
- decoherence
- E.Joos & H.D.Zeh:
The emergence of classical properties through interaction with the environment,
Zeitschr. Phys. B 59 (1985) 223-243.
- K.Hepp & E.H.Lieb:
Phase transitions in reservoir driven open systems with applications to
lasers and superconductors,
Helvetica Physica Acta 46 (1973) 573-603
- W.Unruh & W.H.Zurek: ??
- A.O.Caldiera and A.J.Leggett:
Path integral approach to quantum brownian motion,
Physica A 121 (1983) 587-616
- R.P.Feynman & F.L.Vernon Jr.: Ann. Phys. (NY) 24 (1963) 118-
- W.H.Zurek: Decoherence and the transition from quantum to classical,
Physics Today 44 (1991) 36-44.
- W.H.Zurek: Phys. Review D 26 (1982) 1862-
- classical information theory
- C.E. Shannon.
Probability of error for optimal codes in a gaussian channel,
Bell Syst. Tech. J. 38,3 (May 1959) 611-656.
-
C.E. Shannon & W.Weaver.
The mathematical theory of communication,
Univ. Illinois Press, Urbana, 1949.
- quantum information theory
-
Quantum cryptography
- Stephen Wiesner: "Conjugate Coding," SIGACT News 15 (1983), p. 77
- Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., "Experimental quantum
cryptography", J. Cryptology 5,1 (1992) 3-28.
- Bennett, C. H., Brassard, G. and Ekert, A. K., "Quantum cryptography", Scientific American,
(October 1992) 50-57.
- Kilian, J., "Founding cryptography on oblivious transfer", Proceedings of the 20th Annual
ACM Symposium on Theory of Computing, May 1988, pp. 20 - 31.
- Mayers, D., "Unconditionally secure quantum bit committment is impossible",
Physical Review Letters 78 (1997) 3414-3417.
- Quantum crypto bibliography
- offbeat ways to view quantum and classical mechanics (path integrals,
Wigner picture, Nelson picture, Hamilton-Jacobi equation)
- E.Nelson:
Derivation of the Schrodinger equation from newtonian mechanics,
Physical Review 150,4 (1966) 1079-1085.
- Lecture notes by me
- Josephson junctions