# Q9 2006

Posted by 35994908
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Q9 2006 May 07, 2011 06:02PM Registered: 12 years ago Posts: 50 Rating: 0
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?

 Re: Q9 2006 May 07, 2011 06:33PM Registered: 10 years ago Posts: 3,496 Rating: 1
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).
Sorry, only registered users may post in this forum.