Abstract: Examined herein is the possible correspondence between computational complexity classes in computational graphs and higher homotopy classes between computability paths via the application of two methods. The first method is the use of category theory for formalizing a model of (categorified) graphical Turing machines with a forgetful functor to a “computability -group” (not a groupoid), which expresses computability in a manner that affords even greater abstraction than a Turing machine. The second method is the application of Homotopy Type Theory (HoTT) to the study of the properties of higher homotopy classes between machines (which are themselves simulations executed by higher machines), with the ultimate goal of calculating homotopy types that express invariances of computability (which is our abstract interpretation of the role of complexity classes). We conclude that such methods may make possible the formalization of ‘higher complexity classes’ and ‘higher -machines’ currently unrepresented in theoretical computer science and computational complexity theory. The possibility of formalization as such can be investigated understood through the development of more rigorous proofs regarding homotopy types and homotopy groups, as well as computational experiments that demonstrate correspondences between well-known problems and our theoretical model.
∞
n
Motivation and Central Questions
Motivation and Central Questions
Computational complexity classes offer theoretical computer scientists a means of classifying problems according to the runtime of the algorithms that solve them. Computational complexity theory presents open problems to contemporary researchers, such as the P = NP question, which ultimately pertains to the relationships between computations and complexity classes. The impetus for the research presented here is the suspicion that contemporary techniques and methods - namely, techniques in the Wolfram Language for representing computations, and mathematical methods in Homotopy Type Theory (HoTT) and category theory for capturing deeper relationships between computations - may render more tractable the problems and quandaries that attend contemporary computational complexity theory.
Such a suspicion prompts us to ask four basic questions:
Such a suspicion prompts us to ask four basic questions:
◼
Is it possible to develop an HoTT interpretation of computational complexity theory?
◼
What insights could we gain regarding computability via formalism by way of HoTT?
◼
Might such an approach reveal new complexity classes, or make apparent erstwhile unknown relations between classes?
◼
Could the study of higher homotopies suggest to us the formal possibility of higher computational machines not currently canonized in theoretical computer science?
Theoretical Developments
Theoretical Developments
The research presented herein is largely theoretical, complemented, when appropriate, by computational examples. The theoretical claims offered herein are far from complete, constituting a preliminary effort to build a different theoretical treatment of computation. Although the computational time complexities and complexity classes considered here do include lengthy computations, the visual examples presented are chosen by merit of their visual legibility (which in turn requires that the computations chosen be simple).
A Review of Graphical Computation
A Review of Graphical Computation
Consider the Turing machine rule presented below:
In[]:=
CloudGet["https://www.wolframcloud.com/obj/sw-blog/MultiwayTuringMachines/Programs-01.wl"];TuringMachinePlot[Flatten[{{{1,0}->{1,1,0}},{{1,1}->{2,1,0}},{{2,1}->{1,0,1}},{{2,0}->{1,0,1}},{{1,1}->{2,0,0}}}],2,2,"RulePlot"]
A Nondeterministic Turing Machine Rule
Out[]=
As one might glean from a glance at the above rule, it is inconsistent: after reading an orange cell with its head positioned upward, the Turing machine can perform two different executions. One can also conclude that the Turing machine will not halt, since there exists no possible configuration (subject to the constraint of 2 head positions and 2 colors) that does not correspond to an input in the rule. In order to better visualize the behavior of inconsistent rules, we can produce a graphical model, known as a multiway Turing machine:
In[]:=
CloudGet["https://www.wolframcloud.com/obj/sw-blog/MultiwayTuringMachines/Programs-01.wl"];With[{t=10},MultiwayTuringMachine[{{{1,0}->{1,1,0}},{{1,1}->{2,1,0}},{{2,1}->{1,0,1}},{{2,0}->{1,0,1}},{{1,1}->{2,0,0}}},{{1,t+1},Table[0,t+1]},t,"StatesGraph",VertexSize->.8{1,.2},GraphLayout->"LayeredDigraphEmbedding",PerformanceGoal->"Quality"]]
A Multiway Turing Machine Plot for a Nondeterministic Turing Machine Rule
Out[]=
The multiway Turing machine replicates the same rule indefinitely with regularity. Such behavior might not necessarily be obvious following a mere glance at the rule, even with other properties, such as non-halting and inconsistency, being immediately discernable.
The exercise presented above is intended to communicate the way in which graphical representations of computations can offer the computer scientist a new perspective. In what follows, we use graphical representations in order to present a different, more abstract, treatment of computational complexity classes.
The exercise presented above is intended to communicate the way in which graphical representations of computations can offer the computer scientist a new perspective. In what follows, we use graphical representations in order to present a different, more abstract, treatment of computational complexity classes.
A Conventional Introduction to Computational Complexity Classes
A Conventional Introduction to Computational Complexity Classes
In theoretical computer science and computational complexity theory, the time complexity of an algorithm is its asymptotic, worst-case runtime, often written in Big-O notation. For instance, we write polynomial time complexity as , for some input and some . We write exponential time complexity as . Computational complexity classes serve as a means of classifying problems according to the time complexity of the known algorithms that solve them. For instance, problems in the P complexity class are solvable by deterministic polynomial algorithms and problems in the NP complexity class are solvable by nondeterministic polynomial-time algorithms. Problems in EXPTIME are solvable by deterministic exponential-time algorithms and problems in in NEXPTIME are solvable by nondeterministic exponential-time algorithms.
A graphical Turing machine provides a visual means of thinking about time complexity. Intuitively, a multiway graph represents a nondeterministic computation, whereas a ‘single-way’ graph (a single, unramified path) represents a deterministic computation. For instance, consider the following rule:
O()
c
n
n
c
O()
n
c
A graphical Turing machine provides a visual means of thinking about time complexity. Intuitively, a multiway graph represents a nondeterministic computation, whereas a ‘single-way’ graph (a single, unramified path) represents a deterministic computation. For instance, consider the following rule:
In[]:=
CloudGet["https://www.wolframcloud.com/obj/sw-blog/MultiwayTuringMachines/Programs-01.wl"];TuringMachinePlot[Flatten[{{{2,1}->{1,1,-1}},{{2,0}->{1,1,1}},{{1,0}->{2,1,-1}},{{1,0}->{2,0,1}}}],2,2,"RulePlot"]
A Rule Plot a Nondeterministic Polynomial-Time Computation
Out[]=
Being inconsistent, the rule necessarily corresponds to a multiway graph (a nondeterministic Turing machine). However, such a rule does not exhaust the possible configurations. Plotting its multiway graph, we see that it halts in polynomial time (the worst case run-time being , taking into account its loops):
≥
2
4
In[]:=
ResourceFunction["MultiwayTuringMachine"][{{{2,1}->{1,1,-1}},{{2,0}->{1,1,1}},{{1,0}->{2,1,-1}},{{1,0}->{2,0,1}}},{{1,0,1},{0,0,0,0,0,0,0,0}},64,"StatesGraph",VertexSize->1.1,GraphLayout->"RadialDrawing"]
A Multiway Turing machine Plot for a Nondeterministic Polynomial-Time Computation
Out[]=
Here, the graph ‘nodes’ represent Turing machine configurations, where each arrow is a transition determined by the Turing machine rule. We could provide similar graphs for string-substitution systems or hypergraph-rewriting systems. What such systems share is a graphical interpretation, where the edges of the graph encode information about particular computations, and the nodes encode particular information about the states involved in the computations.
Completeness as Homotopy (and Homotopy as Higher Machine)
Completeness as Homotopy (and Homotopy as Higher Machine)
An important property of complexity classes is completeness, such as NP-completeness and P-completeness. For some complexity class, completeness describes the ease with which one problem in the class can be simulated by another. Regarding the NP class, Richard Karp is well-known for his discovery of 21 NP-complete problems (such as Boolean Satisfiability, Vertex Cover, and Graph Coloring) that can be simulated by one another. For instance, one can ‘re-write’ a Vertex Cover problem as a Boolean Satisfiability problem. Simulations as such are described in computational complexity theory as “reductions,” sometimes achieved through the design of “gadgets”.
Graphical exercises might afford a new view of “gadgets” as such. For instance, suppose that we have two algorithms, where each solves a P-complete problem. First, we have an algorithm for determining the partial order of nodes in a graph via depth-first search. Of course, any deterministic Turing machine program with graphical representation can be regarded as an algorithm for determining a partial order in a graph (the graph of its own computation!):
Graphical exercises might afford a new view of “gadgets” as such. For instance, suppose that we have two algorithms, where each solves a P-complete problem. First, we have an algorithm for determining the partial order of nodes in a graph via depth-first search. Of course, any deterministic Turing machine program with graphical representation can be regarded as an algorithm for determining a partial order in a graph (the graph of its own computation!):
In[]:=
ResourceFunction["MultiwayTuringMachine"][{{{4,1}->{3,1,-1}},{{2,1}->{4,1,1}},{{3,1}->{1,1,1}}},{{2,1,1},{1,1,0}},4,"StatesGraph",GraphLayout->"RadialDrawing",VertexSize->1]
An Algorithm that Solves a Depth-First Partial Ordering Problem
Out[]=
Let the second algorithm solve a Circuit Value Problem, which determines the output of some Boolean circuit given some input. Again, the graphical representation of any deterministic 2-color Turing machine constitutes an algorithm for yielding a Circuit Value Problem answer; simply by running an computation on some input, we obtain an output:
In[]:=
ResourceFunction["MultiwayTuringMachine"][{{{4,2}->{2,2,1}},{{3,2}->{1,2,-1}},{{1,2}->{4,2,1}}},{{3,1,1},{2,0,0,2}},4,"StatesGraph",GraphLayout->"RadialDrawing",VertexSize->1]
An Algorithm that Solves a Circuit Value Problem
Out[]=
Now, suppose we sought to ‘simulate’ one problem as the other via the design of some gadget. We introduce a rule below for doing so (where the Depth-First algorithm cells are still orange, the Circuit Value cells are now yellow, and the new gadget mediations assume the color red):
In[]:=
CloudGet["https://www.wolframcloud.com/obj/sw-blog/MultiwayTuringMachines/Programs-01.wl"];TuringMachinePlot[Flatten[{{{4,3}->{3,1,0}},{{4,2}->{2,2,1}},{{3,2}->{1,2,-1}},{{1,2}->{4,2,1}},{{4,1}->{3,1,-1}},{{2,1}->{4,1,1}},{{3,1}->{1,1,1}},{{4,2}->{1,3,0}},{{3,2}->{4,3,0}},{{1,2}->{2,3,0}},{{2,2}->{3,3,0}},{{3,3}->{1,1,0}},{{1,3}->{2,1,0}},{{2,3}->{4,1,0}},{{3,3}->{1,3,0}},{{1,3}->{4,3,0}},{{4,3}->{2,3,0}}}],4,4,"RulePlot"]
Rule for a Gadget
Out[]=
A graphical representation of the simulation reveals, after an arbitrary cutoff of 20 iterations, a number of paths with common points. We regard such paths to be homotopy-equivalent, such that they are inter-deformable via a 2-morphism. Thus, our gadget rule programs a “2-machine”:
Graphical Representation of a 2-Machine
Towards a Theory of Computational Complexity Classes and Homotopy Classes
Towards a Theory of Computational Complexity Classes and Homotopy Classes
Because the function type can also be written as an exponentiation, we can rewrite the above equation as follows:
Homotopy groups provide a new way of understanding computational complexity classes. Rather than think of such classes asymptotically, we might think of them as ‘invariants’ (possessing the same homotopy types, and therefore, the same algebraic invariants).
Relationship to Existent Literature
Relationship to Existent Literature
Graphical representations of computation have been studied for decades. For instance, Conway’s treatment of finite state machines in the 1970s is highly graphical. However, the multiway Turing machine is a recent innovation made by Wolfram. Automata have been studied categorically, due to the advances made by Eilenberg and Wright. Algebraic studies on the ability of automata to simulate one another have been conducted, notably by Krohn and Rhodes. Zimmer has applied the literature to the categorical formulation of simulations between automata. We continue to advance the general tradition sketched here (namely, the use of pure mathematics to yield abstract models of computation) further to HoTT.
Relevance to Physics
Relevance to Physics
Rulial Space and the Grothendieck Hypothesis
Rulial Space and the Grothendieck Hypothesis
The Deutsch-Church-Turing Thesis, Constructor Theory, and Observers
The Deutsch-Church-Turing Thesis, Constructor Theory, and Observers
The Deutsch-Church-Turing Thesis claims that all physical processes can be simulated by a universal quantum Turing machine. It could be the case that our recasting of the Grothendieck Hypothesis extends this thesis to rulial space (that is, to all physical processes in all universes obeying all possible rules). Of course, it will be difficult for human observers with bounded computational capabilities to subject such a thesis to any comprehensive empirical test. However, the use of what Putnam terms ‘quasi-empirical’ methods in mathematics, which involve mathematical proofs and mathematical (in our case, computational) experiments, may afford a view - albeit, a purely formal view - of machines that are mathematically possible. We might only come to understand such machines by simulating between contemporary computations, simulating between the simulations, and repeating ad infinitum.
Wolfram presents an argument with consequences broader that those of Putnam’s argument, and one that offers notable applicability to physics: mathematical experiments that employ models of computation can be used to probe physical systems, including those that we do not encounter via empirical observation. Such an approach is quite distinct from Constructor Theory, which adopts a Popperian view of computability: namely, the view that computable systems are also testable in that they reveal their nature in their prohibitions and permissions. However, it could well be the case that what we view as prohibitions imposed by a physical system owe to our computational boundedness as observers, such that attempts at falsification might constitute what Jaynes terms a ‘mind projection fallacy’. By subjecting the study of higher machines to mathematical and computational tests, we might not only gain formal traction over machines that may exceed our computational understanding, but, what is more, we might build an infinite tower of such machines, thereby satisfying (and even extending) what Quine terms ‘confirmation holism’, or the development of a theory that does not confine itself to isolated physical subsystems, but can speak to all (possible) physics. Put differently, although Constructor Theory is useful for constructing physics that we can observe, we might say that we should not hinder ourselves by making claims regarding possibility and impossibility, since we can also construct machines answerable to different kinds of physics.
Wolfram presents an argument with consequences broader that those of Putnam’s argument, and one that offers notable applicability to physics: mathematical experiments that employ models of computation can be used to probe physical systems, including those that we do not encounter via empirical observation. Such an approach is quite distinct from Constructor Theory, which adopts a Popperian view of computability: namely, the view that computable systems are also testable in that they reveal their nature in their prohibitions and permissions. However, it could well be the case that what we view as prohibitions imposed by a physical system owe to our computational boundedness as observers, such that attempts at falsification might constitute what Jaynes terms a ‘mind projection fallacy’. By subjecting the study of higher machines to mathematical and computational tests, we might not only gain formal traction over machines that may exceed our computational understanding, but, what is more, we might build an infinite tower of such machines, thereby satisfying (and even extending) what Quine terms ‘confirmation holism’, or the development of a theory that does not confine itself to isolated physical subsystems, but can speak to all (possible) physics. Put differently, although Constructor Theory is useful for constructing physics that we can observe, we might say that we should not hinder ourselves by making claims regarding possibility and impossibility, since we can also construct machines answerable to different kinds of physics.
Next Steps
Next Steps
The theoretical points made in this report must be made stronger and more concrete through the practice of a dual method. The method is to involve the performance of computational experiments using problems known to reside in canonical complexity classes. The method is also to involve the development of proofs regarding homotopy.
As the research for this report was conducted, numerous additional questions, many of which are not introduced here, arose, each of which warrants its own respective study.
As the research for this report was conducted, numerous additional questions, many of which are not introduced here, arose, each of which warrants its own respective study.
Keywords
Keywords
◼
Computational Complexity Theory
◼
Homotopy Type Theory
◼
Category Theory
Acknowledgment
Acknowledgment
I wish to extend a warm expression of gratitude to Hatem Elshatlawy for his frequent correspondence and enduring support, and for the numerous rich conversations that we had concerning the myriad theoretical questions germane to the topic at hand. I wish to thank Xerxes Arsiwalla for his agility during technical conversations, during which he identified numerous formal interpretations of my ideas (as well as further extensions), that I had not myself considered. I also wish to thank Jonathan Gorard for suggesting that I pursue the topic of this report after I communicated to him my interest. Lastly, I am grateful for Stephen Wolfram’s interest and advice, as well as the example that he sets for young researchers; it is rare for expeditions into new computational territory to be so readily encouraged.
References
References
◼
Awodey, Steve, Álvaro Pelayo, and Michael A. Warren. "Voevodsky's univalence axiom in homotopy type theory." Notices of the AMS 60, no. 9 (2013): 1164-1167.
◼
Babai, László, and Endre Szemerédi. “On the complexity of matrix group problems I.” In 25th Annual Symposium on Foundations of Computer Science, 1984., pp. 229-240. IEEE, 1984.
◼
Conway, John H. Regular Algebra and Finite Machines. New York: Dover, 1971.
◼
Deutsch, David. "Quantum theory, the Church-Turing principle and the universal quantum computer." Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400, no. 1818 (1985): 97-117.
◼
____. “Constructor theory.” Synthese 190, no. 18 (2013): 4331-4359.
◼
Grothendieck, Alexander. Pursuing Stacks. Unpublished manuscript, 1983.
◼
Jaynes, Edwin Thompson. “Probability theory as logic.” In Maximum entropy and Bayesian methods, pp. 1-16. Dordrecht: Springer, 1990.
◼
Karp, Richard M. "Reducibility among combinatorial problems." In Complexity of Computer Computations, edited by R. E. Miller, J. W. Thatcher and J.D. Bohlinger, pp. 85-103. Boston: Springer, 1972.
◼
Krohn, Kenneth, and John Rhodes. “Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines.” Transactions of the American Mathematical Society 116 (1965): 450-464.
◼
Lawvere, F. William, Christian Maurer, and Gavin C. Wraith, eds. Model theory and Topoi. Vol. 445. Springer, 2006.
◼
Mac Lane, Saunders. Categories for the working mathematician. New York: Springer, 1978.
◼
Martin-Löf, Per. Intuitionistic type theory. Naples: Bibliopolis, 1984.
◼
Papadimitriou, Christos. Computational Complexity. Boston: Addison Wesley, 1993.
◼
Postnikov, Mikhail M. “Determination of the homology groups of a space by means of the homotopy invariants.” In Doklady Akad. Nauk SSSR (NS), vol. 76, pp. 359-362. 1951.
◼
Putnam, Hilary. "What is mathematical truth?." Historia Mathematica 2, no. 4 (1975): 529-533.
◼
Quine, Willard Van Orman. “Two Dogmas of Empiricism”. The Philosophical Review 60, no 1 (1951): 20–43.
◼
The Univalent Foundations Program. Homotopy Type Theory: Univalent Foundations of Mathematics. Princeton: The Institute for Advanced Study, 2013.
◼
Shelah, Saharon. “Stable theories.” Israel journal of mathematics 7, no. 3 (1969): 187-202.
◼
____. "The number of non-isomorphic models of an unstable first-order theory." Israel Journal of Mathematics 9, no. 4 (1971): 473-487.
◼
Shulman, Michael. “Homotopy type theory: A synthetic approach to higher equalities.” In Categories for the working philosopher, edited by E. Landry, 36-57. Oxford: Oxford University Press: 2016).
◼
Wigderson, Avi. Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton: Princeton University Press, 2019.
◼
Wolfram, Stephen. “Computer software in science and mathematics.” Scientific American 251, no. 3 (1984): 188-203.
◼
____. A Project to Find the Fundamental Theory of Physics. Urbana: Wolfram Media, 2020.
◼
____. “Exploring Rulial Space: The Case of Turing Machines.” Wolfram Physics Project Bulletins. The Wolfram Physics Project, 2020, https://www.wolframphysics.org/bulletins/2020/06/exploring-rulial-space-the-case-of-turing-machines/#finite-tapes
◼
____. “Multiway Turing Machines.” Wolfram Physics Project Bulletins. The Wolfram Physics Project, 2021, https://www.wolframphysics.org/bulletins/2021/02/multiway-turing-machines/
◼
Zimmer, Robert M. “Representation engineering and category theory.” In Change of Representation and Inductive Bias, edited by D.P. Benjamin, 169-182. Boston: Springer, 1990.