|
|
Mon Jan 3 11:22:12 CST 2011
memory
--
Memory is a funny thing. The simple fact that a system has it,
gives it a certain amount of computational power.
Finite Automata have their memory encoded in a "read only" and
static way through the transition function. Given the current
state and an input "symbol", the transition function defines un-
ambigiously what state is to be the next current state. Non-de-
terminism can be introducted by offering more than one state on
one symbol, but this doesn't offer any more computational power.
It only allows one to express the finite state machine in a more
compact way.
The mere presence of memory offers no promise of computational
power. What offers the power is how the machine may store and re-
treive information. Pushdown Automata are non-determinstic finite
autmata with the addition of a single stack of memory. Memory op-
erations consist of "push" and "pop". There is no way to randomly
access the information - some information must be consumed and
lost before other information is accessed and able to be consid-
ered. This limits the PDA to a specific class of computational
problems.
Full computational power is realized through the Turing Machine.
A TM is a PDA with at least two stacks. Using both stacks, a PDA
is able to emulate the reading and writing of a formally defined
TM, which consists of a read head and a memory tape. The point
behind this formulation is that the machine is able to randomaly
access information with having to unrecoverably destroy or con-
sume other pieces of information. It allows information to per-
sist throughout the computation. Universal TMs are "universal"
because they can emulate any conceivable Turning Machine - even
themselves. This allows general purpose machines to be built that
can accept a program to run - as long as it's "valid". This valid
program can itself be a special purpose TM or another universal
TM - the encoding of the TM for input into the Universal TM is
what is commonly called a "program". People who write programs
are also writing valid TMs. UTMs that run on UTMs could be con-
sidered system emulators or programming language interpreters.
It doesn't stop here. "Real" computers (whether digital, mechani-
cal, analog, etc) are not trully Universal Turing Machines. UTMs
included an infinite amount of memory. Real computers do not -
therefore, real computers are actually Linear Bounded Automata.
LBAs are TMs with a finite amount of memory.
So far there are several ways to affect memory, and therefore the
computational power of the "model"
* the fact that accessible memory does infact exists
* the methods in which this accessible memory is accessed
A single stack that allows push/pop requires data to be destroyed
while accessing data deeper in the stack. Adding a second stack
to hold that data which would otherwise have been destroyed is
enough to emulate the random access memory capabilities of a
Turning Machine.
So, in reality, the power of a computation system depends on how
long data can persist in a *useful* form.
Modern computer systems store data in explicitly ways. They can
store a lot of memory, it's done so in an explict form. Human
memory can store a lot of information, too - but at many levels,
this information is coelesced into many layers of implicit infor-
mation that may actually form new data and information through
insights gained by "offline" processing. A human mind that may
seem amazing at remembering exact, explicit information is not
really that amazing if it can't use this recall ability to deter-
mine insights that are deeper than those "normal" human brains
can determine through "average" recall ability. What determines
the intelligence of a person is their ability to connect the
dots. What causes others to call a person a "genius" is one's
ability to determine insights that are non-obvious to the normal
ability to connect the dot and learn insightful facts based on a
body of "more" explicit information.
We are dealing with two issues here, so let's get back to the
first. The "shelf life" of data in a computational system for
modern computers is indefinite, but they don't typically give
rise to more insights. The "shelf life" of information in a av-
erage human's brain is not that long (e.g., it degrades over
time) - however, the human brain is very good at extracting in-
sights or intuition from this information (and experiences). The
intuition and insights become internalized and perist; the data
that causes these original insights might be lost forever, howev-
er. A human brain that has amazing recall of exacting information
is limited in its usefulness - however if this long term ability
to recall exact information is coupled with an abover average
ability to connect the dots and build intuition - a great many
insights and discoveries could take place.
Does this abilit of the human brain make it computationally more
powerful than a UTM? No. However, much like there are theoritical
ways around the limitations placed on the ability of anything to
travel faster than the speed of light (e.g., worm holes, warp
drives, etc); there are similarly theoretical ways for one uni-
versal computer to be more powerful than another in some sense.
It comes down to memory and how it is handled. All things consid-
ered equal, a computational system that allows one to explicitly
store and retrieve "first level" (explicit) data without destroy-
ing innocent data in its wake (i.e., like the single stack PDA)
is just as computationally powerful as one that does the same
(thoguht one may be faster than the other). However, if one sys-
tem has the ability to analyze the data for insightful informa-
tion that might make it easier to accomplish the purpose of the
currently running program or other programs, then this resulting
improvement in efficience would result in on machine being better
at another at a particular task - even if, perhaps, the original
explicity data degrades or disappears over time. If the insights
determined from this original explicit data is good enough to
take its place, even if it's is just to provide some heuristics
or hints, then while the explict data is technically "destroyed"
it still lives on and benefits the system in a much more implicit
higher-level way.
The human mind conceived of this hierarchy of computational ma-
chinery to explore the power of computation. The lesson learned
is that, it's all about the memory. It's whether memory can be
stored (as in a stack or tape), how this memory can be accessed
(push/pop or random access even if emulated), how long memory
will persist (forever or fading over time), and if memory is
coellesced through insight. Any system that destroys data either
through access methods (i.e., via push/pop) or through loss over
time will be less powerful than systems that allow random access
memory and persistence. "Offline" processing provides a means to
not only mitigate the effect of data loss over time (as in the
human memory), but also to make the system seemingly more compu-
tationally powerful by providing a means to encode the insights
of past data into improving the functioning of the system itself.
For it is the conversion of explicit data to implicit knowledge
encoded into the functionality of the system (programs, algo-
rithms, etc) that ultimately allow for more computationally "pow-
erful" entities to emerge. And technically it's no more powerful,
just infinitely more efficient since the need to perform "in-
tractable" computations is replaced through higher level data
"insights" and heuristics.
Unitl next time...
--
Powered by vee
Copyright © 2006-2011
|
|