×

zbMATH — the first resource for mathematics

Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics. (English) Zbl 1192.68268
Summary: We turn the physical Church-Turing Hypothesis from an ambiguous source of sensational speculations into a (collection of) sound and well-defined scientific problem(s):
Examining recent controversies and causes for misunderstanding concerning the state of the Church-Turing Hypothesis (CTH), it is suggested to study the CTH ‘sharpened’ relative to an arbitrary but specific physical theory – rather than vaguely referring to “nature” in general. For this purpose we apply, and emphasize the utility of, concepts from philosophy: physical structuralism, ontological commitment, and constructivism. This general approach is then illustrated with some exemplary results on computability and complexity theory in computational physics.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atallah, M.J.; Callahan, P.; Goodrich, M.T., \(\mathcal{P}\)-complete geometric problems, Int. J. comput. geom. appl., 3, 4, 443-462, (1993) · Zbl 0803.68046
[2] V.A. Adamyan, C.S. Calude, B.S. Pavlov, Transcending the limits of Turing computability, in: T. Hida, K. Saito, S. Si (Eds.), Quantum Information Complexity. Proc. Meijo Winter School 2003, World Scientific, Singapore, 2004, pp. 119-137.
[3] R. Batterman, Intertheory Relations in Physics, Stanford Encyclopedia of Philosophy, 2007. <http://plato.stanford.edu/entries/physics-interrelate>.
[4] Beame, P.; Cook, S.; Hoover, H., Log depth circuits for division and related problems, SIAM J. comput., 15, 994-1003, (1986) · Zbl 0619.68047
[5] Beggs, E.J.; Costa, J.F.; Loff, B.; Tucker, J.V., Computational complexity with experiments as oracles, Proc. roy. soc. ser. A, 464, 2777-2801, (2008) · Zbl 1152.68444
[6] Bennett, C.H.; Landauer, R., The fundamental physical limits of computation, Sci. am., 253, 1, 48-56, (1985)
[7] Bennet, C.H., Universal computation and physical dynamics, Physica D, 86, 268-273, (1995) · Zbl 0885.68056
[8] Beran, L., Orthomodular lattices, (1985), Springer · Zbl 0558.06008
[9] E.J. Beggs, J.V. Tucker, Computations via experiments with kinematic systems, Technical Report 5, Department of Computer Science, University of Wales Swansea, 2004. · Zbl 1400.70002
[10] Beggs, E.J.; Tucker, J.V., Embedding infinitely parallel computation in Newtonian kinematics, Appl. math. comput., 178, 25-43, (2006) · Zbl 1101.68573
[11] Beggs, E.J.; Tucker, J.V., Can Newtonian systems, bounded in space, time, mass and energy compute all functions, Theoret. comput. sci., 371, 4-19, (2007) · Zbl 1108.68050
[12] Beggs, E.J.; Tucker, J.V., Experimental computation of real numbers by Newtonian machines, Proc. roy. soc., 463, 1541-1561, (2007) · Zbl 1130.68051
[13] Baker, T.; Gill, J.; Solovay, R., Relativizations of the \(\mathcal{P} = ? \mathcal{NP}\) question, SIAM J. comput., 4, 4, 431-442, (1975) · Zbl 0323.68033
[14] Bishop, E.; Bridges, D.S., Constructive analysis, (1985), Springer · Zbl 0656.03042
[15] G. Birkhoff, Lattice Theory, Amer. Math. Soc., vol. XXV, Colloq. Publ., Providence, 1967.
[16] A. Bokulich, Reexamining the Quantum-Classical Relation, Cambridge, 2008. · Zbl 1225.00034
[17] T. Breuer, Quantenmechanik: Ein Fall für Gödel? Spektrum, 2002.
[18] Breu, H.; Kirkpatrick, D.G., Unit disk graph recognition is \(\mathcal{NP}\)-hard, Comput. geom. theory appl., 9, 3-24, (1998) · Zbl 0894.68099
[19] Bridges, D.; Svozil, K., Constructive mathematics and quantum physics, Int. J. theoret. phys., 39, 3, 503-515, (2000) · Zbl 0985.81007
[20] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and real computation, (1998), Springer
[21] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: \(\mathcal{NP}\)-completeness, recursive functions, and universal machines, Bull. am. math. soc. (AMS bull.), 21, 1-46, (1989) · Zbl 0681.03020
[22] Chang, E.-C.; Choi, S.W.; Kwon, D.Y.; Park, H.J.; Yap, C.K., Shortest path amidst disc obstacles is computable, Int. J. comput. geom. appl., 16, 567-590, (2006) · Zbl 1114.65016
[23] S.W. Choi, S.I. Pae, H.J. Park, C.K. Yap, Decidability of collision between a helical motion and an algebraic motion, in: G. Hanrot, P. Zimmermann (Eds.), Proc. 7th Conference on Real Numbers and Computers (RNC7), LORIA, Nancy, France, 2006, pp. 69-82.
[24] Chiu, A.; Davida, G.I.; Litow, B.E., Division in logspace-uniform \(\mathcal{NC}^1\), Inform. théor. appl., 35, 3, 259-275, (2001) · Zbl 1014.68062
[25] Calude, C.S.; Dinneen, M.J.; Svozil, K., Reflections on quantum computing, Complexity, 6, 1, 35-37, (2000)
[26] G. Cattaneo, M.L. Dalla Chiara, R. Giuntini, Constructivism and Operationalism in the Foundations of Quantum Mechanics, pp. 21-31 in [30]. · Zbl 1057.81502
[27] A.C. Clarke, 2001: A Space Odyssey, 1968.
[28] Copeland, J., Hypercomputation, (2002), Kluwer, pp. 461-502 · Zbl 1036.68058
[29] Cucker, F.; Grogoriev, D., On the power of real Turing machines over binary inputs, SIAM J. comput., 26, 1, 243-254, (1997) · Zbl 0874.68110
[30] ()
[31] P. Duhem, Le système dy monde, Histoire des doctrines cosmologiques de Platon á Copernic, Paris (1913); partial English translation by R. Ariew, Medieval Cosmology: Theories of Infinity, Place, Time, Voide, and the Plurality of Worlds, University of Chicago Press, 1985.
[32] P. Duhem, La théorie physique, son objet, sa structure, Paris: Cevalier & Rivière (1906); English translation by P.P. Wiener, The Aim and Structure of Physical Theory, Princeton University Press, 1954.
[33] Dunn, J.M.; Hagge, T.J.; Moss, L.S.; Wang, Z., Quantum logic as motivated by quantum computing, J. symb. logic, 70, 2, 353-359, (2005) · Zbl 1093.03036
[34] Edwards, R.E., A formal background to mathematics, vols. Ia and Ib, (1979), Springer · Zbl 0413.03001
[35] Etesi, G.; Németi, I., Non-Turing computations via malament – hogarth space – times, Int. J. theoret. phys., 41, 2, 341-370, (2002) · Zbl 0991.83030
[36] Fletcher, P., A constructivist perspective on physics, Phil. math., 10, 26-42, (2002) · Zbl 1009.03030
[37] Feynman, R.P.; Leighton, R.B.; Sands, M., The Feynman lectures on computation including feynman’s tips on physics, (2005), Addison Wesley
[38] E. Fredkin, R. Landauer, T. Toffoli (Eds.), Proc. Conf. Physics of Computation: Part I: Physics of Computation, Int. J. Theoret. Phys. 21 (3-4) (1982).; E. Fredkin, R. Landauer, T. Toffoli (Eds.), Proc. Conf. Physics of Computation: Part II: Computational Models of Physics, Int. J. Theoret. Phys. 21 (6-7) (1982).; E. Fredkin, R. Landauer, T. Toffoli (Eds.), Proc. Conf. Physics of Computation: Part III: Physical Models of Computation, Int. J. Theoret. Phys. 21 (12) (1982).
[39] Frank, M.P., The physical limits of computing, IEEE comput. sci. eng., 4, 3, 16-26, (2002)
[40] Friedman, H., The computational complexity of maximization and integration, Adv. math., 53, 80-98, (1984) · Zbl 0563.03023
[41] Fredkin, E.; Toffoli, T., Conservative logic, Int. J. theoret. phys., 21, 219-253, (1982) · Zbl 0496.94015
[42] Galton, A., The church – turing thesis: still valid after all these years?, Appl. math. comput., 178, 93-102, (2006) · Zbl 1110.68042
[43] Gandy, R., Church’s thesis and principles for mechanisms, (), 123-148
[44] Gajentaan, A.; Overmars, M.H., On a class of \(\mathcal{O}(n^2)\) problems in computational geometry, Comput. geom., 5, 165-185, (1995) · Zbl 0839.68105
[45] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of \(\mathcal{NP}\)-completeness, (1979), Freeman · Zbl 0411.68039
[46] Geroch, R.; Hartle, J.B., Computability and physical theories, Found. phys., 16, 6, 533-550, (1986)
[47] Greenslaw, R.; Hoover, H.J.; Ruzzo, W.L., Limits to parallel computation, (1995), Oxford University Press
[48] Goldin, D.; Wegner, P., The interactive nature of computing, Minds Mach., 18, 1, 17-38, (2008)
[49] Grzegorczyk, A., On the definitions of computable real continuous functions, Fund. math., 44, 61-77, (1957) · Zbl 0079.24801
[50] Hawking, S.W.; Hartle, J.B., The wave function of the universe, Phys. rev. D, 28, 2960-2975, (1983) · Zbl 1370.83118
[51] F. Hättich, Zur Axiomatik der Quantenmechanik, Master’s Thesis, University of Paderborn, Dept. of Theoretical Physics, 1996. <http://www.upb.de/cs/ag-madh/WWW/ziegler/frank.diplom.pdf>.
[52] Hager, N., Modelle in der physik, Wissenschaftliche taschenbücher, vol. 278, (1982), Akademie-Verlag Berlin
[53] Hellman, G., Mathematical constructivism in spacetime, Brit. J. phil. sci., 49, 425-450, (1998) · Zbl 0948.03055
[54] A. Hodges, Did Church and Turing have a thesis about machines? in: A. Olszewski, J. Wolenski, R. Janusz (Eds.), Church’s Thesis after 70 Years, Ontos Verlag, 2006, pp. 242-252. · Zbl 1106.03038
[55] Holland, P.R., Is quantum mechanics universal?, (), 99-110
[56] Kieu, T., Quantum algorithm for hilbert’s tenth problem, Int. J. theoret. phys., 42, 1461-1478, (2003) · Zbl 1037.81016
[57] Kieu, T.D., Computing the non-computable, Contem. phys., 44, 1, 51-71, (2003)
[58] Kleene, S., Introduction to metamathematics, (1952), Van Nostrand · Zbl 0047.00703
[59] K.-I. Ko, Computational Complexity of Real Functions, Birkhäuser, 1991.
[60] Kreisel, G., Church’s thesis and the ideal of informal rigour, Notre dame J. formal logic, 28, 4, 499-519, (1987) · Zbl 0646.03001
[61] Kuhn, T.S., The structure of scientific revolutions, (1962), University of Chicago Press
[62] B.A. Kushner, Lectures on constructive mathematical analysis, in: E. Mendelson, L.J. Leifman (Eds.), Translations of Mathematical Monographs, vol. 60, AMS (1984), translated from Russian (Moscow 1973). · Zbl 0547.03040
[63] Lloyd, S., Ultimate physical limits to computation, Nature, 406, 1047-1054, (2000)
[64] Lloyd, S., Programming the universe, (2006), Random House
[65] Loff, B.; Costa, J.F., Five views of hypercomputation, Int. J. unconvent. comput., 5, 3-4, 193-207, (2009)
[66] B. Loff, Physics, Computation and Definability, Master’s Thesis, Mathematics Department of the Instituto Superior Técnico, Lisbon, Portugal, November 2007.
[67] Ludwig, G., An axiomatic basis for quantum mechanics, (1985), Springer
[68] Ludwig, G., Die grundstrukturen einer physikalischen theorie, (1990), Springer · Zbl 0387.00010
[69] B.S. Majewski, G. Havas, The complexity of greatest common divisor computations, in: Proc. 1st International Symposium on Algorithmic Number Theory, vol. 877, Springer LNCS, 1994, pp. 184-193. · Zbl 0834.68050
[70] D. Matzke (Chairman), IEEE Proc. Workshop on Physics and Computation, Texas, 1992. <http://ieeexplore.ieee.org/xpl/RecentCon.jsp?punumber=4863>; see also <http://ieeexplore.ieee.org/xpl/RecentCon.jsp?punumber=2948>, 1994.
[71] R. Meister, A Structural Analysis of the Ehlers-Pirani-Schild Space-Time Theory, Master’s Thesis, University of Paderborn, Dept. of Theoretical Physics, 1990.
[72] Meer, K.; Michaux, C., A survey on real structural complexity theory, Bull. belg. math. soc., 4, 113-148, (1997) · Zbl 0934.68046
[73] K. Meer, M. Ziegler, Uncomputability below the real halting problem, in: Proc. 2nd Conference on Computability in Europe (CiE’06), vol. 3988, Springer LNCS, pp. 368-377. · Zbl 1145.68417
[74] Milnor, J., Topology from the differentiable viewpoint, (1997), Princeton University Press
[75] Minsky, M., Matter, mind and models, semantic information processing, (1968), MIT Press, pp. 425-432
[76] P. Mittelstaedt, Die Sprache der Physik, B.I. Wissenschaftsverlag, 1972.
[77] Moore, C., Unpredictability and undecidability in dynamical systems, Phys. rev. lett., 64, 2354-2357, (1990) · Zbl 1050.37510
[78] Marronetti, P.; Tichy, W.; Brügmann, B.; Gonzalez, J.A.; Hannam, M.; Husa, S.; Sperhake, U., Binary black holes on a budget: simulations using workstations, Class. quant. grav., 24, 43-58, (2007)
[79] W.C. Myrvold, Computability in Quantum Mechanics, pp. 33-46 in [30]. · Zbl 1057.81511
[80] T. Ord, Hypercomputation: computing more than the Turing machine, Honour’s Thesis, University of Melbourne, 2002. <http://arxiv.org/math.LO/0209332>.
[81] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley · Zbl 0557.68033
[82] Pour-El, M.B.; Richards, J.I., The wave equation with computable initial data such that its unique solution is not computable, Adv. math., 39, 4, 215-239, (1981) · Zbl 0465.35054
[83] Pour-El, M.B.; Richards, J.I., Computability in analysis and physics, (1989), Springer · Zbl 0678.03027
[84] Percus, A.; Istrate, G.; Moore, C., Computational complexity and statistical physics, (2006), Oxford University Press
[85] J. Pontin, A Giant Leap Forward in Computing? Maybe Not, The New York Times, April 8, 2007.
[86] Preparata, F.P.; Shamos, M.I., Computational geometry: an introduction, (1985), Springer Monographs in Computer Science · Zbl 0759.68037
[87] J. Reif, S.R. Tate, The complexity of N-body simulations, in Proc. 20th International Conference on Automata, Languages, and Programming (ICALP’93), vol. 700, Springer LNCS, pp. 162-176. · Zbl 1422.68139
[88] Reif, J.H.; Tygar, J.D.; Yoshida, A., Computability and complexity of ray tracing, Discrete comput. geom., 11, 265-276, (1994) · Zbl 0807.68096
[89] U. Schelb, Zur physikalischen Begründung der Raum-Zeit-Geometrie, Habilitation thesis, University of Paderborn, 1997. <http://www.upb.de/cs/ag-madh/WWW/ziegler/SCHELB/hab1.ps.gz>.
[90] Scheibe, E., Die reduktion physikalischer theorien, (1997), Springer
[91] H.-J. Schmidt, Structuralism in Physics, in Stanford Encyclopedia of Philosophy, 2008. <http://plato.stanford.edu/entries/physics-structuralism/>.
[92] Schröter, J., Classical mechanics as a limit of quantum mechanics, Annalen der physik series 7, 23, 1-2, 15-27, (1969) · Zbl 0181.52001
[93] J. Schröter, Zur Meta-Theorie der Physik, de Gruyter, 1996.
[94] Schröter, J., Das naturwissenschaftliche weltbild: wahrheit oder fiktion?, Zeitschrift für semiotik, 24, 4, 431-447, (2002)
[95] Schröter, J.; Schelb, U., A space – time theory with rigorous axiomatics, (), 203-215
[96] J. Shipman, Aspects of computability in physics, in: Workshop on Physics and Computation, IEEE Computer Society, Los Alamitos, NM, 1993, pp. 299-314.
[97] W. Sieg, Calculations by Man and Machine, 2000.
[98] W.D. Smith, Church’s Thesis meets Quantum Mechanics, pre-print, 1999. <http://www.math.temple.edu/wds/homepage/churchq.ps>.
[99] W.D. Smith, History of “Church’s Theses” and a Manifesto on Converting Physics into a Rigorous Algorithmic Discipline, pre-print, 1999. <http://www.math.temple.edu/wds/homepage/churchhist.ps>.
[100] Smith, W.D., Church’s thesis meets the N-body problem, Appl. math. comput., 178, 154-183, (2006) · Zbl 1101.70010
[101] Smith, W.D., Three counterexamples refuting kieu’s plan for “quantum adiabatic hypercomputation” and some uncomputable quantum mechanical tasks, J. appl. math. comput., 178, 184-193, (2006) · Zbl 1101.68591
[102] Sneed, J.D., The logical structure of mathematical physics, (1971), Reidel Dordrecht · Zbl 0324.02001
[103] Stegmüller, W., The structuralist view of theories, (1979), Springer · Zbl 0411.03002
[104] W. Stegmüller, Theorie und Erfahrung, Probleme und Resultate der Wissenschaftstheorie und Analytischen Philosophie, vol.II part. F , Springer Studienausgabe, 1986.
[105] M. Stölzner, Levels of Physical Theories, pp. 47-64 in [30].
[106] A. Strugatsky, B. Strugatsky, Roadside Picnic, 1971.
[107] Suppe, F., The structure of scientific theories, (1977), University of Illinois Press
[108] Svozil, K., Randomness and undecidability in physics, (1993), World Scientific · Zbl 0791.68084
[109] K. Svozil, A Constructivist Manifesto for the Physical Sciences - Constructive Re-Interpretation of Physical Undecidability, pp. 65-88 in [30]. · Zbl 0989.81509
[110] Svozil, K., Linear chaos via paradoxical set decompositions, Chaos solitons fract., 7, 5, 785-793, (1996) · Zbl 1080.37546
[111] Svozil, K., Quantum logic, (1998), Springer · Zbl 0989.81521
[112] Svozil, K., Computational universes, Chaos solitons fract., 25, 4, 845-859, (2005) · Zbl 1071.00501
[113] K. Svozil, Physics and metaphysics look at computation, in: A. Olszewski, J. Wolenski, R. Janusz (Eds.), Church’s Thesis after 70 Years, Ontos, 2006, pp. 491-517. · Zbl 1105.03014
[114] Svozil, K., Omega and the time evolution of the n-body problem, (), 231-236 · Zbl 1135.68446
[115] Turing, A.M., On computable numbers, with an application to the entscheidungsproblem, Proc. London math. soc., 42, 2, 230-265, (1936) · Zbl 0016.09701
[116] Tucker, J.V.; Zucker, J.I., Computable functions and semicomputable sets on many-sorted algebras, (), 317-523
[117] Yao, A.C.-C., Classical physics and the church – turing thesis, J. assoc. comput. Mach., 50, 1, 100-105, (2003) · Zbl 1326.68136
[118] S. Weinberg, Dreams of a Final Theory: The Scientist’s Search for the Ultimate Laws of Nature, Vintage, 1994.
[119] C.F. von Weizsäcker, Das Gefüge der Theorien, Kapitel 6 in Aufbau der Physik, Carl Hanser, 1985.
[120] K. Weihrauch, N. Zhong, The wave propagator is turing computable, in: Proc. 26th International Colloquium on Automata, Languages and Programming (ICALP 1999), vol. 1644, Springer LNCS, pp. 697-707. · Zbl 0945.03092
[121] Weihrauch, K.; Zhong, N., Is wave propagation computable or can wave computers beat the Turing machine?, Proc. London math. soc., 85, 2, 312-332, (2002) · Zbl 1011.03035
[122] Weihrauch, K.; Zhong, N., Computing Schrödinger propagators on type-2 Turing machines, J. comp., 22, 6, 918-935, (2006) · Zbl 1119.03063
[123] J. Wiedermann, J. van Leeuwen, Relativistic computers and non-uniform complexity theory, in: Proc. 3rd Int. Conf. on Unconvential Models of Computation (UMC’02), vol. 2509, Springer LNCS, pp. 287-299. · Zbl 1029.68066
[124] Wolfram, S., Undecidability and intractability in theoretical physics, Phys. rev. lett., 54, 8, 735-738, (1985)
[125] Xia, Z., The existence of noncollision singularities in the n-body problem, Ann. math., 135, 3, 411-468, (1992) · Zbl 0764.70006
[126] Ying, M., A theory of computation based on quantum logic (I), Theoret. comput. sci., 344, 134-207, (2005) · Zbl 1079.68035
[127] Ziegler, M., Computational power of infinite quantum parallelism, Int. J. theoret. phys., 44, 11, 2057-2071, (2005) · Zbl 1101.81040
[128] Ziegler, M., Effectively open real functions, J. comp., 22, 827-849, (2006) · Zbl 1126.03042
[129] M. Ziegler, A meta-theory of physics and computation, in: Verhandlungen der Deutschen Physikalischen Gesellschaft (DPG), February 2008, p. 145.
[130] Is the Universe a Computer? From Konrad Zuse’s Invention of the Computer to his “Calculating Space” to Quantum Computing, Symposium under the patronage of Dr. Annette Schavan, Federal Minister of Education and Research November 2006. <http://www.gi-ev.de/regionalgruppen/berlin/download/veranstaltungen/ist_das_universum_flyer.pdf>.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.