References

[1] For a more informal exposition see: S. Wolfram, Sci. Am. 251, 188 (1984). A fuller treatment will be given elsewhere.

[2] E.g., The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, edited by M. Davis (Raven, New York, 1965), or J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computations (Addison-Wesley, Reading, Mass., 1979).

[3] This is a physical form of the Church-Turing hypothesis. Mathematically conceivable systems of greater power can be obtained by including tables of answers to questions insoluble for these universal computers.

[4] Real-number parameters in classical physics allow infinite information density. Nevertheless, even in classical physics, the finiteness of experimental arrangements and measurements, implemented as coarse graining in statistical mechanics, implies finite information input and output. In relativistic quantum field theory, finite density of information (or quantum states) is evident for free fields bounded in phase space [e.g., J. Bekenstein, Phys. Rev. D 30, 1669 (1984)]. It is less clear for interacting fields, except if space-time is ultimately discrete [but cf. B. Simon, Functional Integration and Quantum Physics (Academic, New York, 1979), Sec. III.9]. A finite information transmission rate is implied by relativistic causality and the manifold structure of space-time.

[5] It is just possible, however, that the parallelism of the path integral may allow quantum mechanical systems to solve any NP problem in polynomial time.

[6] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

[7] See S. Wolfram, Nature 311, 419 (1984); Cellular Automata, edited by D. Farmer, T. Toffoli, and S. Wolfram, Physica 10D, Nos. 1 and 2 (1984), and references therein.

[8] A. R. Smith, J. Assoc. Comput. Mach. 18, 331 (1971).

[9] E. R. Banks, Massachusetts Institute of Technology Report No. TR-81, 1971 (unpublished). The ``Game of Life,'' discussed in E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays (Academic, New York, 1982), is an example with , . N. Margolus, Physica (Utrecht) 10D, 81 (1984), gives a reversible example.

[10] S. Wolfram, Physica (Utrecht) 10D, 1 (1984), and to be published.

[11] This is analogous to the problem of whether a computer run with particular input will ever reach a ``halt'' state.

[12] The number of steps to check (``busy-beaver function'') in general grows with the seed size faster than any finite formula can describe (Ref. 2).

[13] Cf. C. Bennett, to be published.

[14] Cf. B. Eckhardt, J. Ford, and F. Vivaldi, Physica (Utrecht) 13D, 339 (1984).

[15] The question is a generalization of whether there exists an assignment of values to sites such that the logical expression corresponding the -step CA mapping is true (cf. V. Sewelson, private communication).

[16] L. Hurd, to be published.

[17] S. Wolfram, Commun. Math. Phys. 96, 15 (1984).

[18] N. Packard and S. Wolfram, to be published. The equivalent problem of covering a plane with a given set of tiles is considered in R. Robinson, Invent. Math. 12, 177 (1971).

[19] E.g., C. Bennett, Int. J. Theor. Phys. 21, 905 (1982); E. Fredkin and T. Toffoli, Int. J. Theor. Phys. 21, 219 (1982); A. Vergis, K. Steiglitz, and B. Dickinson, ``The Complexity of Analog Computation'' (unpublished).

[20] Conventional computation theory primarily concerns possibilities, not probabilities. There are nevertheless some problems for which almost all instances are known to be of equivalent difficulty. But other problems are known to be much easier on average than in the worst case. In addition, for some NP-complete problems the density of candidate solutions close to the actual one is very large, so approximate solutions can easily be found [S. Kirkpatrick, C. Gelatt, and M. Vecchi, Science 220, 671 (1983)].

[21] Compare Time Warps, String Edites, and Macromolecules, edited by D. Sankoff and J. Kruskal (Addison-Wesley, Reading, Mass., 1983).

[22] F. Barahona, J. Phys. A 13, 3241 (1982).

[23] E. Domany and W. Kinzel, Phys. Rev. Lett. 53, 311 (1984).

[24] See W. Haken, in Word Problems, edited by W. W. Boone, F. B. Cannonito, and R. C. Lyndon (North-Holland, Amsterdam, 1973).

[25] G. Chaitin, Sci. Am. 232, 47 (1975), and IBM J. Res. Dev. 21, 350 (1977); R. Shaw, to be published.

previous