# Oct 2006 Exam Question 9.

Posted by ian.coetzer
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
 Oct 2006 Exam Question 9. November 02, 2009 08:16PM Registered: 13 years ago Posts: 137 Rating: 0

*** Question 9 ***

thx
 Re: Oct 2006 Exam Question 9. November 03, 2009 12:37PM Registered: 12 years ago Posts: 673 Rating: -1
Here's another definition of computable (from wikistudent) that might be acceptable:
"According to Richard P. Feynmanâ€™s Lectures on Computation, if we start with a variable x, and take a function of that variable, F(x), then F(x) is computable if we can find a Turing machine T which, if fed a tape on which x is written, will eventually halt with F(x) printed on the tape."

For (b), look on page 595 in the textbook. ADDER with an extra edge from START to HALT with (/\, /\, R) should suffice I think.

--
"A man is the less likely to become great the more he is dominated by reason: few can achieve greatness - and none in art - if they are not dominated by illusion." Mr. Doctor
 Re: Oct 2006 Exam Question 9. November 03, 2009 01:23PM Registered: 13 years ago Posts: 137 Rating: 0
Didn't they say use unary encoding? Adder assumes that a 'b' is used to separate two clumps of 'a's
It does so by added the first say n clump of a's to the second m clump of 'a's by overwriting the separating 'b' with an 'a'
then finally it removes the last 'a' on the input tape since the 'b' that was overwritten by an 'a'.

Thus the result is a string consisting of 'a's only.

How will that prove the function f(n) = n + n, which must do a computation by doubling up the number of 'a's in the input string?

I fail to see how "ADDER" solves / proves this function.

thanks
 Re: Oct 2006 Exam Question 9. November 03, 2009 01:25PM Registered: 13 years ago Posts: 137 Rating: 0
Okay, I see one can use two characters but the input string will only have one character and the output string 'should' only have the same character as well.
BUT during execution one can append new charaters or even overwrite existing characters with other characters ...
 Re: Oct 2006 Exam Question 9. November 03, 2009 01:36PM Registered: 14 years ago Posts: 613 Rating: 0
Interesting points, considering that n >= 0 what would the string look like if f(n) = 0 + 0? I see it as containing a singly solitary b and that's all. Beginning at START, the first input character will be b and it will be changed into an a. The machine moves to state 1 where the next character read will be /\ which is left alone and the head is moved left, the machine moves to state 2. At this stage the head is on the solitary character on the tape (the b turned into an a) and is then turned into /\ and the machine moves to HALT. At this point, the tape contains only /\'s so the result is zero, as expected.
 Re: Oct 2006 Exam Question 9. November 03, 2009 02:00PM Registered: 13 years ago Posts: 137 Rating: 0
mmm but with two 'b's in the input string ADDER crashes in state (1).
so I don't really think 'b' are allowed.

In ADDER ONE 'b' is allowed since it MEANS something - it is used as a separator between TWO clumps of 'a's.
If there is more than one 'b' it crashes since adder EXPECTS there to only be one.

also what if the input string is aabaaaa, it will result in the string aaaaaa (2 + 4) and we are not doing an x + y operation but rather an n + n.
Thus the first clump of a's will have to be the same as the second clump of a's.

And this is not the case, we will be given and input string like aaa and have to 'created' the result of aaaaaa, all 6 'a's won't be given on the input string so beware of this question. I honestly don't think ADDER is correct for proving the function f(n) = n + n.

I could be wrong by my gut tells me that i'm not.... at this stage...unless I see the reason in using ADDER which I don't at this stage.
 Re: Oct 2006 Exam Question 9. November 03, 2009 02:03PM Registered: 13 years ago Posts: 137 Rating: 0
Another one, what if the input string was aab? it would result in first convert it to aaa and then remove the last a resulting in aa.
How did this successfully perform the function that we were given to prove? aab to aa? that surely is not doing an n + n, but rather leaving only n on the tape.
the tape should consist of aaaa remember from given example output!
 Re: Oct 2006 Exam Question 9. November 03, 2009 02:16PM Registered: 12 years ago Posts: 673 Rating: -1
Yes, Ian, you are correct. ADDER won't do. I looked at the question too hastily.

Wouldn't this be the shortest?
START --(a,a,R)--> INSERT a ----> START
START --(/\,/\,R)--> HALT

Regarding the encoding, unary means that the number must be encoded using one character only. The input string doesn't have to be one character, although in this question that actually is the case.

--
"A man is the less likely to become great the more he is dominated by reason: few can achieve greatness - and none in art - if they are not dominated by illusion." Mr. Doctor
 Re: Oct 2006 Exam Question 9. November 03, 2009 02:21PM Registered: 14 years ago Posts: 613 Rating: 0
Ignore all of that, I wasn't seeing the whole question properly and was still thinking of the ADDER in the textbook.
 Re: Oct 2006 Exam Question 9. November 03, 2009 02:28PM Registered: 14 years ago Posts: 613 Rating: 0
If you encountere a b in the string but none of your states can read that character the machine should crash because nowhere does it say those are valid characters for the tape (should've been given explicitly specified alphabet).
Sorry, only registered users may post in this forum.