Friday, November 8, 2013
Computation is broader than the Turing Machine
This should be one of those things we learn in school, and yet we learn the opposite.
The notion of computation is not identical with a Turing machine.
First, the notion of computation is a human state of mind, not a technical term.
Second, if you define 'computation' to be 'anything that can be performed on a Turing machine', then you'll never discover any other form of computation.
This is very much like the way the word 'gene', a term coined for discussion of the source of an inherited feature, became 'DNA', due to the influence of the new molecular biology. But of course this is now known to be incorrect: there are many non-DNA factors that enter into inheritance (environment, epigenetics, natural law, et cetera). So, biologists either need to use a different word for the broad notion of 'gene', which is not advisable, or they need to reclaim it from molecular biology, so it can be used again in discussions of inheritance, features, etc.
In computing, let's look at a very simple thing, which computational systems do, but which simply cannot be captured by a Turing machine:
* Determine if two inputs are received simultaneously.
Clearly this is a computational task. It's clearly an automatable task. It's a task often performed by actual computers. But it has nothing to do with a Turing machine. You simply cannot determine simultaneity with a single input, if one construes the tape head as an input (which one shouldn't, see below). The result of a 'simultaneity determination' could be signaled to more than one additional computer at a time, through tapes if preferred, and the ramifications of this are even further from a Turing machine's capacities.
So a 'multiple-head Turing machine' or a 'multi-tape Turing machine' (a slightly different model) can do things that we call computation, which cannot be done on a single-head Turing machine, if we add, for example, time or some other signaling capacity to this form of TM. I thought everyone understood this, but I found this on the wikipedia page on computability:
Here, there may be more than one tape; moreover there may be multiple heads per tape. Surprisingly, any computation that can be performed by this sort of machine can also be performed by an ordinary Turing machine, although the latter may be slower or require a larger total region of its tape.
It's surprising because it is not true, if one were to actually construct usable Turing machines. The point of a gedanken experiment is to inspire such considerations. Doing two things at once, or seeing if two things are happening at once, are clearly not possible with a single-head Turing machine. This is just the beginning of the differences … a brain, for example, is obviously capable of real-world computation that would be impossible to perform with a Turing machine. Millions of calculations by a module of the brain, which are then passed through different routes to different modules simultaneously? How is that a Turing machine?
Now, you could simulate the environment and the multi-head Turing machine together, using a single-thread computation (the is equivalent to a Turing machine). But look at what we've just done. We've defined an operation that takes place in the world as somehow 'computationally-equivalent' to a simulation of the world. They aren't equivalent. The simulation is only a tool for investigating our theory of what goes on in a world intertwined with computing. No one would say that this single-threaded machine is equivalent to a biological world that it might be simulating. Only in computing would we get so confused about the role of theory.
Since at least the 17th-century, the idea of the human brain as a kind of computer or machine has been useful for investigation of what it may be to be human. The problem: we don't know what kind of machine or computer it is. We still do not, to this day. Our technical definitions of computability will definitely need expansion, to include real computational phenomena, before we can begin to understand what biological computers do.
I believe that, at the very start, we need to introduce a de-mechanized version of the Turing machine. In early stages of any science, the notion of intelligibility tends to be 'mechanical'. Pre-Newtownian physics, in early investigations by everyone in the 17th century, tended to make mechanic models the gold standard of a good theory. That disappeared after Newton discovered that there was no mechanical explanation of forces. In fact, his finding expands the notion of 'mechanical' at that point, to include action at a distance.
But the very human concept of mechanics as explanatory science keeps reoccurring, and it has done so in computing. For multi-head and multi-track Turing machines we need to ask "what is the tape mechanism?" because it matters. If we imagine it to be a real, mechanical tape mechanism, then it is a sensor, and "simultaneity" in a "multi-sensor" Turing machine would be a computable question, in a real machine.
Computing is something happens in the real world. So we need to ask ourselves: how can computing move from a confused formal science / engineering hybrid to a natural science?