Q1 of assignment 4

Isn't the answer in tut204 supposed to be a TM that will accept ODDPALINDROME?
Looks to me more like it's accepting EVENPALINDROME...

Even:


Odd:

aa#
(a, Y, R)
Ya#
(a,a,R)
Ya#
(#,#,L)
Ya#
(a,X,L)
YX#
(Y,Y,R)
YX#

No edge out of q6... crash

I think it may help to make the lines between q1 q2 q5 q6 a rectangle. Then one sees straight away the a edge going down, and the a edge coming back up. Add the one edge you enter by, and there are always 2n + 1 a's. As far as the number goes it doesn't matter if you branch to b for your next one.

I think it does accept ODDPALINDROME then.

Your Odd machine looks right, too (although one could "play Planarity" with it ) Two of the ways to skin this same cat? I suppose that topologically that would mean that in some sense both the graphs are equal. Which is probably too interesting a question to be considering at this hour...

a
A#
A#
halt.

Problem is, if I give the first tm the string aabbbbaa, which is even, it accepts it (even though it rejects abba). It shouldn't accept any even palindrome. It seems that it accepts some even palendromes (so technically I should probably not try say that it "accepts even palendromes" and some odd palendromes, but should only accept odd.

Whoops, found my problem... Between Q3 and Q4, it should read X,X,L and not X,X,R. I think that sorts out the whole problem and there's nothing wrong then with the answer given in tut204

Yes, that would do it! OK I was too lazy to try with b's, so never got stuck there, but a glimpse says the pattern is now the same, so should work "recursively".

Interesting that the machines are somehow equal, eh? Of course there are many TMs per language, in all the theorems, but probably if you do the combinatorics MAT course on Y3 level you'd encounter some of the work done on discovering the families of TMs even?

These TMs remind me of sorting algorithms