Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf sheaves simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorUrs
    • CommentTimeAug 26th 2022
    • (edited Aug 26th 2022)

    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.

    diff, v12, current

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeAug 27th 2022

    added pointer also to these two items:

    diff, v14, current

    • CommentRowNumber3.
    • CommentAuthorUrs
    • CommentTimeAug 27th 2022
    • (edited Aug 27th 2022)

    added pointer also to

    • Jan van Leeuwen, The Philosophy of Computation, p. xix-xxx in: Proceedings of IIT.SRC 2015 – Student Research Conference Bratislava (2015) [full proceedings: pdf, web; article: pdf; slides: pdf]

    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):

    diff, v14, current

    • CommentRowNumber4.
    • CommentAuthorUrs
    • CommentTimeAug 29th 2022

    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?

    • CommentRowNumber5.
    • CommentAuthorDavid_Corfield
    • CommentTimeAug 29th 2022

    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.

    • CommentRowNumber6.
    • CommentAuthorDavid_Corfield
    • CommentTimeAug 29th 2022

    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.

    • CommentRowNumber7.
    • CommentAuthorUrs
    • CommentTimeAug 29th 2022

    Yes, that observation is what had just made me add pointer to Leibniz’s mechanical computer: here.

    In fact, fundamentally every physical computation is continuous – also switching a transistor is continuous (here).

    But where can one find computer scientists admit/formalize this in citable form?!

    • CommentRowNumber8.
    • CommentAuthorDavid_Corfield
    • CommentTimeAug 29th 2022

    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?

    • CommentRowNumber9.
    • CommentAuthorUrs
    • CommentTimeAug 29th 2022
    • (edited Aug 29th 2022)

    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:

    • Question: How novel is this definition – who deserves to be cited for it?

    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.

    • CommentRowNumber10.
    • CommentAuthormaxsnew
    • CommentTimeAug 29th 2022

    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?

    • CommentRowNumber11.
    • CommentAuthorUrs
    • CommentTimeAug 29th 2022

    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. :-)

    • CommentRowNumber12.
    • CommentAuthorDavid_Corfield
    • CommentTimeAug 30th 2022

    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.

    • CommentRowNumber13.
    • CommentAuthorUrs
    • CommentTimeAug 30th 2022

    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.

    • CommentRowNumber14.
    • CommentAuthorUrs
    • CommentTimeNov 27th 2022

    added pointer to:

    • Michael Sipser, Introduction to the Theory Of Computation, 3rd ed: Cengage Learning (2012) [ISBN:978-1-133-18779-0,pdf, pdf]

    diff, v16, current

    • CommentRowNumber15.
    • CommentAuthorUrs
    • CommentTimeDec 18th 2022

    In the References-subsection on computation as path-lifting, I have added (here) pointer to:

    diff, v17, current

    • CommentRowNumber16.
    • CommentAuthorUrs
    • CommentTimeDec 29th 2022

    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]

    diff, v19, current

    • CommentRowNumber17.
    • CommentAuthorUrs
    • CommentTimeFeb 16th 2023

    One more reference where (quantum) computation is conceived of as path lifting:

    diff, v20, current