In week 2, we looked at how logical circuits could be used to
do simple binary addition. We built an XOR circuit, used it to build
a half-adder, used a half-adder to build a full-adder. This week I'd
like to use a Turing Machine to do simple binary arithmetic. The first
approach might be to simulate XOR, half-adder and full-adder in our
machine. Is this simulation possible? We know the answer is yes: anything
that can be computed, can be computed by a Turing Machine. Do we want
to do this simulation? Probably not. It seems much easier to simulate
binary addition at a higher level. Is there a point I am trying
to make? Yes - Kurzweil argues that we do not have to build an
intelligent machine from neuron simulation (see page 146); we can, instead, model
from higher level brain functions. If you view logic circuits as
the analog to neurons (a bit of a stretch), then we are eschewing
modeling at that level. Instead, we will model at the symbol
manipulation level. Whew - that was a long-winded intro.
Your task is to implement the *function* of a full-adder as a Turing Machine program.
What we will use are the rules that a full-adder is based on:
<![CDATA[
abc => de
000 => 00
001 => 10
010 => 10
011 => 01
100 => 10
101 => 01
110 => 01
111 => 11
]]>
where a and b are the two digits to be summed, c is the carry-in,
d is the resulting digit and e is the carry-out. Your tape will
start with a sequence of three binary digits, i.e., the abc columns from rules
above. You will produce a sequence of two binary digits, i.e., the de columns
above. Leave a space between the original sequence and the new sequence. Assume the
head starts on the left-most digit. For example, assume you start with "101" on the
tape. When your program halts, you should have "101#01" on the tape (where the
# char represents a space). Why 01 as an answer? Because 1+0+1 = 0 with a carry of 1.
Victor introduced another way of viewing pattern matching problems like this in lab.
He presented a way to use a directed, labeled graph to sketch out a solution. Some
of you might find this helpful, some not. I did generate a partial graph. You can
find it here: Graphical view of homework problem.
If it does not make any sense to you, skip it. Or see me or Victor if you want to
understand it better.
Something to ponder: isn't this just the CRA (Chinese Room Argument)
with binary addition instead
of Chinese? Our rule book contains the rules above. Your Turing Machine
replaces Searle as the rule-follower.
