Q9 2006

This is an attempt at Question 9b. It took me over an hour, I just hope I don't get stuck like that in the exam. Let me know your thoughts on this question...
prove the function f(n) = n + n n >= 0

is computable, use unary encoding. The remarks in tutorial letter says to use a TM. Is this answer just by drawing the TM enough?

I think you also have to show that what's left behind on the tape can be interpreted as output, too.

So if your adder did 1+1, when this has been through the TM the tape must say 2.

In other words all you must have left on the Tape is 2 and an infinite number of deltas.

Don't have place for the book near this computer so take this suggestion as only "generally right". There will be details I've missed here that might matter.

I think the book covers n + n.

You encode the numbers as strings of aaaaaaaab (terminators are b). Your machine then adds these by "counting on its fingers". Each loop of the machine you can read in detail in the book will add a single "tally mark". Similarly subtraction goes one at a time, too.

Hope that's less unhelpful than my most recent inputs have turned out to be. (Mistakes are GOOD, but carelessness is not).