.
Allan Turing proposed a machine, now referred to as the "Turing
Machine". It consists of:
1) A state machine
2) A tape reader that could only do 3 things:
.
Write a "1" or "0" at the current position on the tape
Read the bit at the current position of the tape.
Advance or retard the tape one bit position at a time.
.
Turing used this conceptual model in his work on computability. He
proved that his machine could do anything that a genral purpose
computer could do, given enough time, and a long enough tape.
.
Google "Turing". You'll get lots of hits.
Regards,
Jon
This is correct, and as an extra, cryptology can be
done on for example a 64 bit wide processor as 64 1 bit
operations in parallel (indeed resulting in a huge speedup).
Google for example 'ffdecsa'.
From the ffdecsa FAQ and technical doc:
<start quote>
FFdecsa is a fast implementation of the CSA decryption algorithm for MPEG
TS packets.
Q: What does FF stands for?
A: FFdecsa means "Fucking Fast decsa".
Q: Why would you use such a rude name?
A: Because this code is fucking fast, more than 800% the speed of the best
implementation I'm able to find around at the moment.
TRICK NUMBER 2: parallel bitslice
---------------------------------
Implementing the algorithm as described in tricks 1 and 2 give us about
15% of the speed of a traditional implementation. This happens because
we work on only one bit, even if our CPU is 32 bit wide. But *we can
process 32 different packets at the same time*. This is called
"bitslice" method. It can be done only if the program flow is not
dependent of the data (if, while,...). Luckily this is true.
Things like
if(a){
b=c&d;
}
else{
b=e&f;
}
can be coded as (think of how hardware would implement this)
b1=c&d;
b2=e&f;
b=b2^(a&(b1^b2));
and things like
if(a){
b=c&d
}
can be transformed in the same way, as they may be written as
if(a){
b=c&d
}
else{
b=b;
}
It could look wasteful, but it is not; and destroys data dependency.
Our codes takes the same time as before, but produces 32 results, so
speed is now 480% the speed of a traditional implementation.
</end quote>