Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
In looking for texts that would address the question “What is computation?” and arrive at an answer vaguely akin to path lifting/transport, I found (and have now added pointer to) this text:
which gets pretty close, in particular in and around their Figure 1.
added pointer also to these two items:
Jan van Leeuwen, Jiří Wiedermann: What is Computation – An Epistemic Approach, p. 1-13 in Proceedings of SOFSEM 2015: Theory and Practice of Computer Science, Lecture Notes in Computer Science 8939, Springer (2015) [pdf:10.1007/978-3-662-46078-8, talk slides: pdf]
Jan van Leeuwen, Jiří Wiedermann, Understanding Computation – A General Theory of Computational Processes, Technical Report UU-CS-2019-012, Utrecht University (2019) [dspace:1874/390075, pdf, pdf]
added pointer also to
and added (now here) the version of the graphics of their picture of computation found in there
Finally, I gave this list of references a brief lead-in paragraph, which currently reads as follows:
A conceptualization of computation as something at least close to path-lifting and/or as functors between path groupoids of topological spaces (from an “action space” parameterizing the possible computing instructions to a “knowledge space” expressing their executions):
In those references, van Leeuwen &Wiedermann tried to find a conceptualization of “computation” that subsumed continuous (as opposed to discrete, step-wise) processes, which they tried to model by continuous paths in an “action space”.
This idea must have occurred to others, too.
Question: Is there an established term for “computation where programs may be continuous as opposed to just step-wise paths”?
I am asking because when I search for “continuous computation” I get lots of hits, but nothing quite along the lines of van Leeuwen & Wiedermann. So maybe it goes by other terminology?
Just as a brief foray into understanding for myself what van Leeuwen & Wiedermann are trying to do:
From Understanding Computation: A General Theory of Computational Processes
A good impression of the many different approaches to the notion of computation as found today, is given in the contributions to the Ubiquity Symposium in 2010, see Denning [15]. These witness the gradual transition in thinking about the notion, from ‘computation by machines’ to ‘computation by processes’, allowing for a much greater flexibility in matching it to our newer understandings of it. In our present analysis, this still lacks uniformity and focus on the core notion of computation.
So people are considering even biological processes as computational, but no general approach yet. Frailey quotation (p.5) extends out to general processes
natural or artificial; mechanical, electrical or biological; described by a formal model or simply occurring naturally and in need of a formal description; processes should be the focus of our attention when we try to understand computation
But something more needed for L&W: the epistemic view of computation, processes relative to an epistemic observer’s understanding.
the epistemic theory of computation holds that an observed ‘action’ is a computation precisely when the action is productive, seen from the perspective of the (knowledge-)theory of the spectator, i.e. when its result is both ‘explainable’ and ‘provable’ as an outcome from the premises used by the actor [48–50]
“computation is an observer-dependent notion”.
So I guess this is what’s unusual in their thinking. Start from specific technical artefacts that we take to be performing computations. Then wonder why these particular processes are computational and not others, such as the operation of a cell or a star. But then rather than take any process as computational, require there to be a spectator that sees the process in a certain why, so that the dynamics of the process tallies with the rule-boundness of knowledge production.
Even without precise definitions, one can immediately infer that dynamical systems are computational from the perspective of our framework only if the motions determined by them can be viewed as ‘allowable’, i.e. if there is some knowledge domain in which all motions can be viewed as generating knowledge (by the criteria of a spectator). If this condition is not satisfied for a given dynamical system, then it is not computational. However, if the condition is satisfied, then it is computational, as we do not concern ourselves with the way a system actually generates its curves.
I guess the idea of computation as including continuous processes goes right back to the idea of an analog computer. Then we’re right back to those astronomical aids, such as the 2000 year old Antikythera mechanism.
As a guess, perhaps it goes from simply not needing to be said when analog computers are widely used, before the emphasis on digital computing leads to an underplaying of the underlying physical processes with the logical treatment of computing.
Here’s Leo Corry suggesting the history of analog computing has been adversely affected, Turing’s Pre-War Analog Computers: The Fatherhood of the Modern Computer Revisited:
In fact, the tremendous success of modern digital computers has negatively affected the way the history of analog computers in general has been told. The case of Turing’s 1939 project is just one example of such retrospective misreading, though one seldom mentioned in this context. Analog computers were not only a natural choice in many situations before the war but even after the emergence of digital computing in the post-war period were not immediately displaced. A most remarkable example of this is precisely the Liverpool tide-predicting machine, which remained in use until the 1960s, before being superseded by electronic computers.
As the digital era progresses, presumably the more remarkable thing is that the computer scientists can forget the underlying physical processes and employ the tools of logic. Who would need to remind people that there’s still physics going on? The hardware engineers?
Sorry if I am being unclear. What I am asking in #4 is for citable (quasi-)mathematical definitions of “computation” along the lines of what van Leeuwen & Wiederman tried to offer.
So when I come out and define (reversible) programmable computation to be nothing but type transport in dependent type families in (cohesive) HoTT (whose base is interpreted as the “gate names”, paths in which are the admissible “programs”) – thus subsuming the example of TQC (where the type family in question is the bundle of conformal blocks over a configuration space of points, as discussed here), then:
On the one hand, it seems completely obvious to me, and I’ll be happy to give credit to whoever said this first.
On the other hand, I have trouble finding almost any references really saying this. The closest so far is van Leeuwen & Wiedermanm, though it still requires some good-will to recognize the simple idea in what they write.
I’m still not really sure what the “big idea” you are trying to get at. The idea of mapping a syntactic category to the category of Sets is just what we would call a (set-theoretic) denotational semantics. If that category of sets is “computable” instead then this would be some kind of computable semantics. Then you’re just taking the category of elements of that?
The semantic functor itself is not a computation yet: a computation is path lifting (Cartesian lift, transport, …) in the fibration it classifies.
It’s not a big idea, it’s a triviality. But maybe one without a good citation. Yet. :-)
More broadly for this page, it seems to me that the interesting thing happening is that quantum computing is forcing a reappraisal of what counts as computation. One could have wondered this anyway. Some have speculated that any physical process is computation (such as Frailey in #5). vL&W agree to the broadening from merely symbolic computation on a digital computer, but still want restrictions on the kinds of process that count. So they propose the need for an epistemic agent or spectator who imbues a physical process with meaning. Since we take it that to think is to think conceptually, and so to construe in terms of types = concepts, it must be that they’re taking the type of states of a physical system to stand for the types they wish to reason about, and then processes of the physical system to stand for knowledge generation in the conceptual type that wish to reason about.
the interesting thing happening is that quantum computing is forcing a reappraisal of what counts as computation.
Absolutely, whence my quest in #1 above.
In particular, in topological quantum computation, we see that:
a program is a continuous path in a configuration space of points
its execution is a lift of that path through the bundle of conformal blocks over the configuration space.
In other words, there is a linear dependent type family (naturally constructed in HoTT, as discussed here) such that topological quantum computation in the sense of Kitaev et al. is precisely its associated transport operation.
So it’s the notion of transport along paths in dependent (homotopy) type theory which unifies the notions of classical with topological quantum computation.
In the References-subsection on computation as path-lifting, I have added (here) pointer to:
Michael A. Nielsen, Mark R. Dowling, Mile Gu, Andrew C. Doherty, Quantum Computation as Geometry, Science, 311 5764 (2006) 1133-1135 [doi:10.1126/science.1121541, arXiv:quant-ph/0603161]
Mark R. Dowling, Michael A. Nielsen, The geometry of quantum computation, Quantum Information & Computation 8 10 (2008) 861–899 [doi:10.5555/2016985.2016986, arXiv:quant-ph/0701004]
added pointer to:
Dana S. Scott, Outline of a mathematical theory of computation, in: Proceedings of the Fourth Annual Princeton Conference on Information Sciences and Systems (1970) 169–176. [pdf]
Dana S. Scott, Christopher Strachey, Toward a Mathematical Semantics for Computer Languages, Oxford University Computing Laboratory, Technical Monograph PRG-6 (1971) [pdf]
One more reference where (quantum) computation is conceived of as path lifting:
added pointer to:
Hector Zenil (ed.): A Computable Universe – Understanding and Exploring Nature as Computation, World Scientific (2012) [doi:10.1142/8306]
foreword by Roger Penrose [arXiv:1205.5823]
introduction by Hector Zenil [arXiv:1206.0376]
1 to 18 of 18
