Welcome! Log In Create A New Profile


Q9 2006

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

avatar Re: Q9 2006
May 07, 2011 06:33PM
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.

Click here to login