3

The most common definitions of computation I have seen are in terms of "what Turing Machines, Lambda Calculus, etc. do," which is unsatisfying. The definition of computable functions does not seem to be a definition of what computation itself, as a process, is.

I have not been able to find anything like the sort of deep conceptual analysis that exists for similar questions like: "what are numbers," "what are propositions," etc. E.g., if numbers are an "abstract object," would that make computation an "abstract process"? Or is computation just the step-wise enumeration of 'relations' or entailment (which there is a solid literature for)? I know there isn't a definitive answer, I'm just looking for some sort of exploration of the topic so I'm not working in the dark.

We can say 2 + 2 = 4 and 6 - 2 = 4, but these are not computed the same way.

There is a lot in the physics literature and the philosophy of physics literature on "what is a computer," physically speaking. Obviously, the physical instantiation of adding two groups of two things together is different from throwing out two of six things. This would suggest that, vis-á-vis computation, 2 + 2 ≠ 6-2, which is very different from how we think of identity in numbers. That is, the outputs are equivalent, but not the processes by which we get the output.

This seems relevant to issues in the philosophy of information vis-á-vis the "scandal of deduction," that deterministic computation does not produce new information, and the problem of non-constructive rigid designators. It also seems relevant to the philosophy of physics re: pancomputationalism (all the rage in popular science it seems), but I can't find anything really in depth.

Tim Brown
  • 39
  • 2
  • 1
    Even the case of 2 + 2 != 6 - 2 is actually complicated. In terms of actual computers, it is very possible that some layer(s) of the software/hardware stack that will calculate this apply various transformations so that what the lower levels do is not immediately understandable. – Frank Apr 28 '23 at 21:22
  • 1
    This book may be relevant: https://www.amazon.com/Computability-Theory-Introduction-Recursion-ebook/dp/B00512Q330/ref=sr_1_5?keywords=Enderton&qid=1682717152&sr=8-5. – Frank Apr 28 '23 at 21:26
  • 1
    https://plato.stanford.edu/entries/computation-physicalsystems/ – J D Apr 28 '23 at 22:02
  • 2
    What part of Turing's work is "unsatisfying?" He defines an abstract computer on the basis of capability to achieve certain operations. Those operation are computation. – Boba Fit Apr 28 '23 at 22:08
  • "This would suggest that, vis-á-vis computation, 2 + 2 ≠ 6-2" -- No it doesn't, it only shows there are two different ways to get to the same place. If I'm in San Francisco I can get to Los Angeles via several different routes, but when I get there it's the same Los Angeles. – user4894 Apr 28 '23 at 23:48
  • 2
    The standard reference on conceptual analysis of computation is [Sieg, Calculations by Man and Machine: Conceptual Analysis](https://www.cmu.edu/dietrich/philosophy/docs/seig/Conceptual%20Analysis.pdf), but I doubt that he will satisfy you. On the classical conception, computation is *not* an abstract process. It is defined functionally, i.e. indifferently to implementation, which can be abstract or concrete, physical or mental. But it is meant to be an idealized model of "mechanistic procedure" for an implementor with human-like limitations, even when it is a machine or an abstraction. – Conifold Apr 29 '23 at 05:55
  • @user4894 right, it is the same Los Angeles. I think few would deny that. The argument would be that driving from San Francisco to LA is different than driving from San Diego to LA, even though they are the same destination. This gets at the nature of equations. Are they names or are they recipes? The recipe analogy is often used for "algorithms," which is an infamously fuzzy word, hence the problem of proving the Church-Turing Thesis in a rigorous way. But some algorithms are essentially equations it seems. – Tim Brown Apr 29 '23 at 11:51
  • @BobaFit I find Turing's work to be absolutely brilliant, and it isn't unsatisfying from a practical perspective. However, when computational neuroscience argues that mental life is "caused by" or "reducible to" computation, and computation is described in terms of instructions to a person, there is some circularity. Some physicists, e.g. Deutsch, Davies, etc. have argued that the universe IS a computer. This seems to beg a better grounding for the concept to me. We also have the scandal of deduction and the inability to define physical computers as a result of the definition. – Tim Brown Apr 29 '23 at 11:59
  • Computational Neuroscience is probably mistaken in generalizing Turing's work in that way. Perhaps there is nothing to understand there? – Scott Rowe Apr 29 '23 at 16:24
  • I'm curious about your motivation for this question. I have tried to glean it from the question and comments. You find something 'unsatisfying', but I am not grasping *what*. What problem are you seeking an answer to? I tried reading about the Scandal of Deduction, but I'm an engineer, I was like, so *fix* it. Don't like cast iron? *Invent Steel* already. So I don't really understand philosophy. Take Action. – Scott Rowe Apr 29 '23 at 20:29
  • @ScottRowe you pretty much nailed my impetus for the question. I have been kicking around ideas for a paper on this as a starting point for finding a solution, but I wanted to make sure I wasn't missing an existing body of research on it by not knowing the terms used for it. 99% of the time I think I have an original idea it turns out it already exists somewhere; now I check around because I once got myself very excited "discovering" the Gibbs Paradox only to learn I was over a century late lol. – Tim Brown Apr 30 '23 at 11:30
  • @ScottRowe and yeah, computational neuroscience and pancomputational information theoretic descriptions of physics might be simply bad ways to model the world. But then we are left with the question: "why did they seem like such good ways to model the world originally?" It seems like the underlying way in which nature works might then be similar to, but not identical with what we call computation, which would require discovering some sort of new formalism. It seems connected to finitism in physics in general, since that is a prerequisite for using computation as your model. – Tim Brown Apr 30 '23 at 11:37
  • When we first discover something, it seems to apply very generally. But then a whole confederacy of onces arise to obviate it. When I was about 7 I was counting up dots in a grid different ways and then excitedly showed my father. He glanced down and said, "That's multiplication." I was like, "*Someone invented it already?*" – Scott Rowe Apr 30 '23 at 12:46

1 Answers1

2

Maybe we can start historically. Turing is attempting to capture the informal notion of effective or mechanistic process. His 1936 highlights the following, where computer denotes an actual agent:

(a): Computation is determinstic

(b): Bounded memory of computer

(c): Bounded observation of computer: the computer can only intake finitely amounts of data at a time.

This list is not exhaustive. Turing was very influential, the Church_turing thesis asserts that the philosophical nature of mechanical process is captured by the formal notion of Turing machine. So your requests for an actual analysis of compoutational process are immediately answered if Church-Turing is true.

So is it true? Well, the standard arguments are as follows (Kleene 1952)

(i): All paradigmatically computable processes have turned out to be recursive ( ie captured bt the notion of a TM)

(ii): All other attempts at an analysis of mechanistic process are equivalent to TMs.

In particular, indeterminsitic systems such as Posts are seen to be equivalent with Determinsitic TMs. Post was originally working with logics, which brings us to another notion of computation, as espoused by Kripke 2013 ( and with precursors in Leibniz): computation is just deduction. The blind manipulation of symbols according to lgocial rules is computation. These observations can be made more formal via the curry howard correspondence. Again, if you accept church turing, we can say even more: these two viewpoints are in fact "philosophically" equivalent.

A further survey of arguments for and against can be seen at SEPs page on Church turing. Typically each different formalism was accompanied ny a (brief) defense of hy it captured the notion of effective procedure. So it may serve you to read say Church, Post, Schonfinkel, Turing, Godel/Heberand on their original motivations.

Lastly, I note that we have now come full circle: whereas Turing based his notion of computation on what human computers could do, proponents of computational theory of mind now use TMs ( and computatiuonal models more generally) to "explain" computational notions in human agents.

emesupap
  • 1,959
  • 1
  • 4
  • 12
  • Thank you! I suppose what I am hung up on is the idea of a formalism based on "how would a human carry out a recipe for symbol manipulation," coming to be the basis for understanding how consciousness emerges from physical systems or how physics/causation works at a fundemental level. It seems almost idealist, which is generally not what these theories have in mind. The formalism of quantum mechanics has many interpretations, as does logic itself, so I'm just surprised. I have read the SEP articles on information and physical computation closely, but will give the CT one a closer look. – Tim Brown Apr 29 '23 at 12:07
  • CTM proponents often endose some form of functionalism, which can go thru in principle for dualism as well. But in practice most are physicalists. – emesupap Apr 29 '23 at 17:29
  • As for your comments about 2+2 != 6 -2, you may wish to look up the conncept of observational equivalence – emesupap Apr 29 '23 at 17:31
  • Doesn't a TM have *unbounded* memory? That's the entire point, else it's a finite state automaton. – user4894 Apr 30 '23 at 01:13
  • @user4894 bounded memory corresponds to finite states in TM. A TM is a "finite state automaton" - it has finitely many states – emesupap Apr 30 '23 at 02:36
  • @Papuseme A TM is a FSA with an UNbounded memory. Perhaps you just made a typo when you said the tape is bounded. The tape is not bounded, think about it. – user4894 Apr 30 '23 at 20:12
  • @user4894 where did I say the tape is bounded? – emesupap Apr 30 '23 at 20:51
  • @Papuseme *(b): Bounded memory of computer*. Was that a typo perhaps? – user4894 Apr 30 '23 at 21:58
  • @user4894 in above, I mention that computer refers to person, not TM. But again, this corresponds to finite mental states, not boundedness of TM tape – emesupap Apr 30 '23 at 23:19