Question: are there
computational analogies to the three
simple mechanical machines?
In other words, are there computational machines which are
analogous to the
inclined plane, the
lever and the
wheel?
Before we can answer this question, we should probably take a short look at what makes the simple mechanical machines "special" or "interesting".
Although there is some room for debate, I'm going to claim that what makes them special is:
- they are fundamental (i.e. they aren't made out of even simpler machines)
- they are complete (i.e. they are the building blocks for all other purely mechanical machines)
- they are useful in an abstract sense when discussing mechanical systems (i.e. they provide useful insights into the nature of mechanical systems)
The Turing Machine perspective - version I
A
Turing machine is, by definition, the simplest
construct which is capable of computing (i.e. doing computational work).
A Turing machine is also, by definition, capable of
doing everything which is
computable (i.e. capable of doing any conceivable computational work).
This leads to the inevitable conclusion that the set of simple computational machines consisting of just a Turing machine (i.e. a set with one element) is:
- fundamental (i.e. there are, by definition, no simpler computational machines)
- complete (i.e. everything which is computable can be computed by a machine in the set - i.e. by a Turing machine)
- useful in an abstract sense when discussing computational systems (see the literature surrounding Turing machines if you're not convinced)
i.e. the set of simple computational machines consisting of just a Turing machine really is, according to the criteria specified above, analogous to the set of simple mechanical machines consisting of the inclined plane, the lever and the wheel.
The Turing Machine perspective - version II
Hmmm.
The set of simple computational machines consisting of just a Turing machine might very well be fundamental, complete and useful in some context.
Unfortunately, it isn't very useful when trying to analyze
software development as it is
practiced today since the demand for Turing machine software is, shall we say, rather limited.
Let's try a slightly different perspective . . .
While it is true that a Turing machine is, by definition, the simplest construct capable of computing, it is also true that a Turing machine has component parts and that the fundamental operation that a Turing machine performs consists of a sequence of steps.
Sidebar:
The component parts of a Turing machine are (arguably):
- the tape reader/writer
- the tape movement mechanism
- the state transition table
- the short term memory (i.e. the knowledge of the current state)
- the decision making unit (i.e. that which decides what to write, which direction to move the tape and which state to enter next)
- the tape (see notes below)
The steps performed within each fundamental Turing machine operation are
- Read the symbol on the tape under the head.
- Based on the symbol just read and the current state, overwrite the tape square with a new symbol (possibly the same symbol).
- Based on the symbol just read and the current state, move the tape one position to the left or to the right.
- Based on the symbol just read and the current state, enter a new state (possibly the same state).
Viewed from the
perspective of the individual steps, the following
primitive operations performed by conventional
computers come to mind:
- fetch next instruction
- fetch data
- store data
- conditionally change the definition of "next instruction"
- conditionally change internal processor state
In fact, since a conventional computer doesn't really distinguish between instructions and data in any "fundamental" sense, the above list of primitive operations performed by a conventional computer is almost perfectly analogous to the steps performed within each fundamental Turing machine operation.
Hmmm. Does this imply that the following set of primitive operations
- fetch data
- store data
- conditionally change definition of "next instruction"
- conditionally change internal processor state
are a fundamental, complete and useful set of simple computational "machines"?
Hmmm
(my answer is that I'm not sure although the notion is certainly intriguing).
Questions
- Is my list of primitive operations performed by conventional computers truly a fundamental, complete and useful set of (some useful kind of) simple machines?
i.e.:
- is it fundamental or can the so-called primitive operations be broken down into smaller yet "interesting" operations?
- is it complete or are there primitive operations which aren't constructed using a combination of these primitive operations?
- is it useful?
- Is there a fundamental, complete and useful set of simple computational machines from the high level programming language perspective?
i.e. something along the lines of "assignment statement", "if statement", "while loop", "function call", etc?
- Is a Turing machine truly "the simplest construct which is capable of computing" or is this stretching things a bit much?
Although I was comfortable with this claim when I wrote this writeup, each time I re-read the writeup I wonder about it. (2007/12/25)
Notes
- This writeup is inspired by an article on the topic of simple computational machines which I ran across a few years ago in a computer magazine.
I've been unable to find the article or any equivalent discussion of the topic on the 'net.
I have found an interesting paper titled Foundations of Cognitive Support: Toward Abstract Patterns of Usefulness by Andrew Walenstein of the Department of Computer Science at the University of Victoria in Victoria, B.C., Canada.
This paper describes a set of simple cognitive support machines (i.e. machines which assist us in understanding things).
It does make a passing reference to the notion of simple computational machines but doesn't provide any useful pointers to them (at least, none which I recognized as being useful).
The paper is available on the 'net at
http://www.cs.sfu.ca/~walenste/personal/Research/pubs/2002-sv-dsvis-walenstein.pdf
(last accessed 2002/12/03)
- While it is true that one must use both deterministic and non-deterministic Turing machines if one wishes to be able to compute everything which is computable, it is also true that a non-deterministic Turing machine can be emulated by an appropriately configured deterministic Turing machine (i.e. they are, at least for the purposes of this writeup, equivalent).
- I'm not going to debate whether or not the tape in a Turing machine is part of the Turing machine or not.
Instead, I'm going to hide behind the (arguably flawed) reasoning that a tape is, for all practical purposes, a component of a Turing machine since a Turing machine without a tape is useless (and uninteresting).