Thread by @deontologistics

Here's a further attempt at the tricky task of defining computation spurred on by @peligrietzer. Let's begin with the relation between computation and information processing. All computation is information processing, but not all information processing is computation.

The problem is that everything described as 'effective computation' where what this means is indexed to the equivalence class of computable functions picked out by recursive functions, lambda calculus, and Turing machines, is too narrow to capture everything computational.

This is Abramsky's point (arxiv.org/abs/1604.02603). Even something as seemingly mundane as an operating system is not really computing a function from finite input to finite output. It's a well-behaved non-terminating process.

This notion of non-termination appears in the context of Turing machines and lambda calculus, but that doesn't mean that these formalisms effectively capture, let alone exhaust the meaning of the term 'computational process' that can be qualified by 'non-terminating'.

To make progress we need to recognise that the inherently *compositional* character of computational processes is inadequately captured by lambda calculus/TMs. We can build computational processes out of other computational processes, and abstraction is a tool for doing so.

Understanding *what* a computational process computes lets us abstract away from *how* it does so, such that we can use it as a black box component in building a more complicated computational process. This applies to both language (λ) and machine (TM) perspectives.

The natural question is then: can we build computational processes that cannot simply be described as computing functions from finite inputs to finite outputs purely out of computational processes that can be so described?

Furthermore, would such a process be accurately described as an algorithm, even though it was non-terminating?

It seems to me that the answer to both questions is *obviously* yes. What else is an the operating system? The main problem is that we don't have an equivalence result governing frameworks for composing processes comparable to that indexed by the Church-Turing thesis.

We have are a bunch of different term rewriting calculi (comparable to λ: e.g., π Calculus), machine models (comparable to TMs: e.g., Hewitt's Actor Model), and process algebra (e.g., Milner's Calculus of Communicating Systems), but no overriding framework that unites them.

My personal view is that the one true overarching framework would essentially be a fully realised cybernetics, with a unified theory of control and semantic information (deontologistics.wordpress.com/2019/11/01/tfe…). Yet, I think we can still make some imprecise but correct claims in its absence.

Here's an imprecise recursive definition: any process that processes information, and is built entirely out of other computational processes, for some satisfactory definition of 'build', is itself a computational process, even if it doesn't compute a 'computable' function.

The question is then whether we can relax the constraint that a process must be 'entirely' made out of other computational processes in order to qualify as computational. Could it incorporate non-computational information processing subsystems and still be computational?

This brings us back to cybernetic and the theory of control systems. There are plenty of working 'hybrid systems' in which an underlying dynamic process is yoked to a control process that is computational in the strict sense defined by the above recursive definition.

Are these systems, considered as a whole, computational processes or not? Consider a robot that navigates an environment and carries out certain non-computational tasks by applying algorithmic logic to convert sensory information into control signals driving its actuators.

Insofar as we can abstract the functional roles played by its sensors and actuators from the details of their implementation in the same manner we can regular computational subsystems, I see no reason why we can't call this an 'interactive' computational process.

We can already build computational processes out interacting computational processes by composing them into concurrent communicating systems. The only difference with the robot is that it engages in some 'non-communicative' interaction with its environment.

What we have here is a condition under which we can relax the term 'entirely' in the above recursive definition. Some types of functional components that involve *taking* information from and *feeding* information into an environment can be used to build computational processes.

There is still much more to be said. We might want to understand how *feedback loops* created by these forms of input from and output to a non-computational environment enable us to talk about *what* a computational process is computing, or *what* information it is processing.

Crucially, we might want a full blooded theory of semantic information which allowed us to say something like 'the robot is computing a solution to the problem of navigating *this* obstacle', or the 'the AI is mulling over information it has received *about* the stock market'.

I'm not claiming to have such a theory, but I do think you can begin to see how we might get to such a theory by making the imprecise recursive definition of what a computational process is that I've provided by expanding it in the ways I've suggested and making it precise.

So, that's where I currently stand on the fundamental question in the philosophy of computer science. Norbert Wiener did nothing wrong.