Computing x + y
w(y)
Represent positive integers, x and y in unary notation
x w(x)
1 1
2 11
3 111
Initial tape configuration
w(x)
0
s1
Final tape configuration
w(x + y)
0
s1
All we need to do is to move the separating 0
to the right of w(y)
Previous slide
Next slide
Back to first slide
View graphic version