Does computability according to Church-Turing thesis include side effects?

Question

To my understanding:

• The Church-Turing thesis means that one could theoretically compute anything that can be computed using either a Turing Machine or the Lambda Calculus.
• The Lambda Calculus is based on mathematical functions. This leads to the inability of "pure" functional programming languages based on Lambda Calculus to have side-effects (in the sense that a language like C would have side effects).

To me that would imply that side-effects are not part of computability, but something in addition to it.

e.g. I would say that real-world memory writes that cause physical side-effects are not of the same nature as the imaginary writes to the tape in a Turing Machine. Or put another way: if I'm writing values to memory whose purpose is to serve as a result in a calculation, Turing completeness would be theoretically relevant; but if I'm writing to a region of memory designed to instruct a robot arm to do things, Turing completeness would be theoretically irrelevant.

Is my understanding correct?

Answer 1

The Church-Turing thesis says that Turing machines capture precisely the effectively calculable functions from natural numbers to natural numbers. It says little about what happens when we attach a robotic arm to a computer.

Any kind of machine needs to represent numbers in some way, obviously since numbers are abstract entities. A Turing machine represents them with 0's and 1's written on a tape. In $\lambda$-calculus we represent them with Church numerals. If we attached a robotic arm to an iPhone, we could represent them with a suitable number of up-down movements by the arm. The question of representation is separate from the question of side effects. In particular, the question of what can be computed is separate from how the results can be communicated. Lamenting about the fact that $\lambda$-calculus has no input/output, for instance, would be misguided.

There is a well understood theory of computational side effects. According to this theory, Turing machine have certain side effects. They carry state in their cells, that is a side effect. We can implement quoting on Turing machines, that is the side effect which converts a closure to source code. Turing machines with oracles can be seen as having the "input" side effect (known as a reader monad in functional programming).

In summary, the Church-Turing thesis is largely independent of what computational effects might be present in the computational model. This is so because the Church-Turing thesis is about numer-theoretic functions, not about how computers interact with their environment.

Answer 2

As always in computability, you need to consider the model of computation. If your model of computation is the lambda calculus then, as you say, clearly there are no side-effects. If your model of computation is C programs, then clearly there are side-effects. If your model is Turing machines, then "side-effects" doesn't really make sense because there are no functions: the only thing in town is a spaghetti program writing to a tape.

Turing completeness deals with computations that start with some input and compute some function. If your model of computation includes a robot arm then that's absolutely relevant (the state of the arm and the things it manipulates are part of the computation). But even without that, you can use classical computability to determine what things you can computably tell the robot arm to do by writing to its DMA area.

Answer 3

The question is not totally formalizable, so it's hard to answer it in a definite way.

However, you are correct when you say that Turing completeness does not imply the presence of side effects -- its definition only cares about the input-output behavior. The pure lambda calculus does not have side effects, yet it is Turing complete.

e.g. I would say that real-world memory writes that cause physical side-effects are not of the same nature as the imaginary writes to the tape in a Turing Machine.

I would agree to this.

[...] if I'm writing to a region of memory designed to instruct a robot arm to do things, Turing completeness would be theoretically irrelevant.

Well, it would be still relevant since you need to compute what to write on that memory cell before you can write to it. E.g. assume you have a sensor providing you some reading $x$ (e.g. a webcam image), and you want to move your robotic arm depending on $x$ (grab the ball which is in the image). Then, you need to compute the coordinates at which you want to move the arm. In the example I mentioned, you need image/pattern recognition, so you need to ability to run sophisticated algorithms.

As usual, for any given task, you probably don't need a Turing-complete machine. However, if you want to build a general-purpose robotic arm, it should be equipped with a general-purpose computer.