patternMinor
Does computability according to Church-Turing thesis include side effects?
Viewed 0 times
thesisincludesideeffectscomputabilitydoeschurchturingaccording
Problem
To my understanding:
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?
- 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#69967, answer score: 8
Revisions (0)
No revisions yet.