Oct 2006 Exam Question 9.

Okay, last one, comments please.

*** Question 9 ***

thx

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

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.

Please elaborate.

thanks

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 ...

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.

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.

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!

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

Ignore all of that, I wasn't seeing the whole question properly and was still thinking of the ADDER in the textbook.

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).