6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "There is a well understood theory of computational side effects." Does this theory have a specific name I can use to research? $\endgroup$ – dukereg Feb 11 '17 at 1:54
  • 1
    $\begingroup$ Sure, just go here: github.com/yallop/effects-bibliography $\endgroup$ – Andrej Bauer Feb 11 '17 at 9:28
  • $\begingroup$ @AndrejBauer: according to this theory of computational side effects, would one also say that the untyped $\lambda$-calculus has side effects, when we encode numbers and effectively calculable functions in it? If so, what are these side effects? $\endgroup$ – Michael Bächtold Dec 1 '17 at 9:59
  • 1
    $\begingroup$ @MichaelBächtold: sorry for the very late answer. The untyped $\lambda$-calculus has a side effect, in a way, namely non-termination because in it we can write down non-normalizing terms that "run forever". $\endgroup$ – Andrej Bauer Jun 12 '18 at 7:29
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is not quite clear to me. I am seeking a computational model that allows me to reason about e.g. writing to the memory controlling a robot arm, as opposed to just having state because it is incidentally part of computing some numeric function. Are Turing machines such a model on their own, or would I require other models for this? $\endgroup$ – dukereg Feb 11 '17 at 2:05
  • 1
    $\begingroup$ It depends how the robot behaves. If you receive no feedback from the robot (i.e., it just moves itself into whatever position its input describes and the computer trusts it has done that) then the robot is essentially superfluous to the theory, since it's essentially just a display device. If your robot feeds data back to the computer, then you'd need to use a model that includes that. But people don't tend to study computability in that kind of setting because we have no reason to believe that physical systems can compute anything a Turing machine can't. $\endgroup$ – David Richerby Feb 11 '17 at 10:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.