Transcript Document

The Effect of Coding on
Computation
Adina Lederhendler
Topics in Biological Physics 23/12/08
Shannon: A universal Turing machine with two internal states. Automata Studies, 1956
Miller :The magical number seven, plus or minus two: some limits on our capacity for
processing information ,Psychological Review, 1956
Outline
What is a code?
Abstract computation
Different codes for universal Turing machines
Real-world computation
The use of coding in working memory
What is a code?
Code – Set of rules for translation of input into output.
Input 1
Output 1
Input 2
Output 2
Input 3
Output 3
Input NI
Output NO
What is a code?
Examples of codes:
ASCII code
English
alphabet
Binary
digits
Genetic code
Nucleotide
sequences
Amino
acids
Turing machine
Reading/
writing head
Z
Si
Configuration:
Symbol +
Internal state.
X
Y
Information encoded
as symbols on tape.
Turing machine
Si
Z
X
Y
Code
Configuration
Step
symbol + state
symbol + shift + state
complexity of machine (size of code)
m n
Universal Turing Machine
Si
Z
X
Y
Input tape and code of a
Turing machine T
UTM
Z
X
Y
Same output as T.
UTM not related to any specific computation.
Universal Turing machine
Shannon, 1956 – what are the limitations on the code of a UTM?
Minimal number of
states for a UTM?
Minimal number of
symbols for a UTM?
No 1-state UTM
No 1-symbol UTM
Each step depends only on the
letter currently being read.
Cannot carry enough information
Cannot carry any information
Shannon, Automata Studies, 1956
Universal Turing machine
Universal Turing machine A
Symbols
Ai
States
i  1,, m
m
Universal Turing machine B
States
, 
j  1,, n
n
Universal Turing machine C
States
2
Symbols
?
Sj
?
?
Symbols
?
0, 1
2
How do alternative codes affect the computation?
Two-state UTM
Universal Turing machine B
Symbols that
represent
input/output
Symbols that
represent
intermediate
states during
computation
Symbols
Bi
i  1,, m
m
, 
States
2
i  1,  , m
Bi , j , x, y
j  1,  , n 4mn
x  ,
y  L, R
Information about states of A carried by symbols of B
(symbol-state tradeoff)
Two-symbol UTM
Universal Turing machine C
States


n 2 1
Ti

Ti , x1 , x2 ,xs

 2n 2  2
 Li , x1 , x2 , xs

 Ri , x1 , x2 , xs
U i , s

Vi , s
Symbols
i  1,, n
x j  0,1
0,1

 2n  1
s  1,,   1
Information about symbols of A carried by states of C
(symbol-state tradeoff)
2
Two-symbol UTM
Example – Machine A: m = 5, n
A tape: Ai  0,1,2,3,4
C tape: Ci  0,1
0
0
0
0
1
0
0
1
2
0
1
0
3
0
1
1
4
1
0
0
3
Two-symbol UTM
Machine A
0
Si
Sj
2
0
tC  0
1
Ti
0
0
0
0
Machine C
1
0
Two-symbol UTM
0
Si
Sj
2
0
tC  2
1
Ti ,0 Ti ,0,1
0
0
0
0
1
0
Use information about
machine A
Two-symbol UTM
0
Si
Sj
2
0
tC  3
1
L j , 0, 0
0
0
0
0
1
1
Two-symbol UTM
0
Si
Sj
2
0
tC  4
1
L j ,0
0
0
0
0
0
1
Two-symbol UTM
0
Si
Sj
2
0
tC  6
V j ,2
V j ,1
0
0
0
Move to beginning of
the next input
0
0
1
1
Two-symbol UTM
0
tC  7
Si
Sj
2
0
1
Tj
0
Ready to begin
next step.
0
0
0
0
1
Symbol-state product
A
B
C
Symbols
m
4mn  m
2
States
n
mn
2
6mn  8mn
~ 8mn
~ 12 mn  16 mn
Product
Shannon: What is the minimum symbol-state product
required to construct a universal Turing machine?
Minimal Turing machines
Minsky, 1962
7-state, 4-symbol UTM.
Later efforts
Find additional minimal
(size) UTMs.
Find more efficient
minimal UTMs.
Woods, Theoretical Computer Science, 2008
Real world systems
Best code for specific task
Real-world considerations such as:
Efficiency:
Accuracy:
How much time, what resources
can we devote to the computation?
How much noise is present in the
system? How accurate does the
computation need to be?
Biological systems
Evolution/adaptation
to specific task
Working memory
Miller, 1956
Attempt to quantify working
memory capacity
How many items can we recall
immediately after being
presented with a sequence?
AMOUNT OF INFORMATION PER ITEM
Miller, The Psychological Review, 1956
Working memory
Sequences
of items
Recoding into
“chunks” and storage
in short-term memory
Adaptation through learning
New codes = More kinds of “chunks”
Retrieval
Working memory
Baddeley & Hitch, 1974
O
K
B
T
P
V
What
relation
Some
All of
ofBCisis
must
there
included inbe
A
B
between A and C?
Summary
• A code is a set of rules for carrying out a computation.
• Different codes can be used to perform the same
computation.
• The choice of code may affect the efficiency and accuracy
of a computation.
• Biological systems can adapt codes to specific tasks.