I asked Dr. Asaithambi about the operation sequence in a Turing Machine execution cycle. It will read the input symbol under the head, write the output symbol, then move the tape. My initial assumption that the sequence is read, move then write was incorrect.

Here is what I did for Ex. 1.2, #1. This may not be the most efficient way to do this, but it seems to work. This may not make a bit of sense, but I can explain it visually before class if anyone is interested in my babble.

First, I understood the problem that if our input tape looks like this:

Then the output should look like this:

I confirmed this assumption with Dr. Asai today. The other assumption in the problem was that, at a minimum, Gamma = {>, 0, 1, b}.

My strategy was to read a symbol and blank it out immediately. If it was a 0 or 1, scan past the blank in the middle of the input string and its copy until we find the NEXT blank. We write either the 0 or 1 and then scan back to find the original blank. Then we re-write the original 0 or 1 and then start this process over at the symbol on the right. We keep doing this until we start on a blank, which happens to be the blank between the original input string and its copy.

Given this, my states to manage this process, and their "meanings," were:

- Qstart = we're going R to find a 0 or 1; we will then mark it blank and change to a "skip the middle blank" state… either Q1sr or Q0sr
- Q0sr = we're going R looking for a blank marker intending to write 0 in the 2nd blank after we pass the marker; once we hit the middle blank, we change to state Q0wr
- Q1sr = we're going R looking for a blank marker intending to write 1 in the 2nd blank after we pass the marker; once we hit the middle blank, we change to state Q1wr
- Q0wr = we're going R looking for the 2nd blank; once we find it, we'll write a 0 in its place and go left to re-write the 0 in the original space from which we started
- Q1wr = we're going R looking for the 2nd blank; once we find it, we'll write a 1 in its place and go left to re-write the 1 in the original space from which we started
- Q0sl = same concept as Q0sr, only we're going left to pass the middle blank again
- Q1sl = same concept as Q1sr, only we're going left to pass the middle blank again
- Q0wl = same concept as Q0wr, only we're going left to find the location of the symbol that we originally tried to copy
- Q1wl = same concept as Q1wr, only we're going left to find the location of the symbol that we originally tried to copy
- Qh = the halt state

Given these states, we have the following rules. I'm using 'x' to stand in for 0 or 1 because I'm too lazy to type duplicate rules.

(Qstart, >, Qstart, >, +1)

(Qstart, x, Qstart, b, +1)

(Qstart, b, Qh, b, 0)

(Q0sr, b, Q0wr, b, +1)

(Q0sr, x, Q0sr, x, +1)

(Q1sr, b, Q0wr, b, +1)

(Q1sr, x, Q0sr, x, +1)

(Q0wr, x, Q0wr, x, +1)

(Q0wr, b, Q0sl, 0, -1)

(Q1wr, x, Q1wr, x, +1)

(Q1wr, b, Q1sl, 1, -1)

(Q0sl, b, Q0wl, b, -1)

(Q0sl, x, Q0sl, x, -1)

(Q1sl, b, Q1wl, b, -1)

(Q1sl, x, Q1sl, x, -1)

(Q0wl, b, Qstart, 0, +1)

(Q0wl, x, Q0wl, x, -1)

(Q1wl, b, Qstart, 1, +1)

(Q1wl, x, Q1wl, x, -1)

As soon as we are in Qstart and the tape symbol under the head is a blank, we're done!

Very good Jason. Let me see if I understand this, it looks like you have 19 instructions, but 9 have two actual states, for each of zero and one. Does that mean 28 altogether?

I do not see the tape in your description above (…input tape looks like this:). You must be using invisible ink. :-)

Thanks for posting.

The tape would look something like this. For now I'm going to omit each step of marching the "head" on the tape. I'm only showing a step if it changes a symbol on the tape. I'm also showing the tape-start symbol as an 's' (neither the greater-than nor the HTML escape sequence is rendering the right symbol in this comment box… weird).

s101bbbbb

sb01bbbbb

sb01b1bbb

s101b1bbb

s1b1b1bbb

s1b1b10bb

s101b10bb

s10bb10bb

s10bb101b

s101b101b … halt!

I'm "destroying" the input symbol that I'm copying with a blank so that I can "remember" where I left off in copying the input symbols.

Yes, please explain it to me tomorrow. Will you be available before or after class?

Here is EX 1.2, #3. We're computing f(x) = x mod 2 where x is a natural number and is represented in unary (example: if we treat 's' as the start symbol, an input of 5 would show up on the tape as s11111bb…). The output should be "s1bbb…" if 'x' is odd and "s0bbb…" if 'x' is even.

My strategy was move right until we find the first 'b'.

Then, enter a state Qa = "even" and go left. As we go left, we write 'b's and toggle between states Qb = "odd" and Qa = "even."

When we reach the start symbol 's', we enter state Qc = "even" or Qd = "odd."

We then go right and mark the next spot on the tape as 0 if we are in state Qc or 1 if we are in Qd.

Then, we halt.

Here are my rules.

(Q0, s, Q0, s, +1)

(Q0, 1, Q0, 1, +1)

(Q0, b, Qa, b, -1)

(Qa, 1, Qb, b, -1)

(Qb, 1, Qa, b, -1)

(Qa, s, Qc, s, +1)

(Qb, s, Qd, s, +1)

(Qc, b, Qh, 0, 0)

(Qd, b, Qh, 1, 0)

I like it! Nine instructions - I doubt fewer are possible.