Are they any helpful guidelines to describing what a Turing machine does if you already have the pseudo code for the algorithm?
I'm taking a course on complexity theory and it takes me a while to describe a Turing machine that decides or accepts some language (states, transitions, etc.) even though I know how I could code it in something like C or even assembly. I guess I just haven't had enough practice with Turing machines (working on it), but I appreciate any suggestions.
edit
I don't want to make a Turing Machine simulator, I want to describe a Turing Machine on paper (alphabet, states, transitions) for deciding some language.
Here's a trivial example of what I mean, say I need to write a Turing Machine that goes over a string of 0s and 1s and changes all the 0s in it to 1s. For example, if you start with 11010 on the tape (input) it halts with 11111 on the tape (output). Now in a high level language you know it's something like:
Go over every character on tape
If character is 0 change it to 1
The Turing machine description is informally something like:
You have two states, q and halt. When you are on state q and you see a 1, go to the right without changing it. If you see a 0, change it to 1 and go to the right. If you see the blank symbol (end of tape) then go to the halt state.
Formally you will have something like {q, halt} for states. {((q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (halt, 0, L))} for transitions.
Now this problem is trivial, but there are others which are more involving (add unary numbers or recognize a language with equal number of a's, b's, and c's). I could easily write the pseudocode for them, but writing the Turing Machine is far more challenging (takes me a long time) and I was wondering if there were some tips, resources, or guidelines that help me become better at solving problems like that.
Disclaimer: Your question is very general, hence so is this answer. Note that I'm anything but an expert on TMs, and this approach will usually not be very efficient (I can't even promise it will always be effective). I'm just jotting down some thoughts here.
I would suggest trying an approach like this: Take your pseudo-code and reduce it so that
it only consists of a) boolean variables and b) if
-statements.
For example:
if THIS_LETTER_IS("A"):
found_an_even_number_of_A = not found_an_even_number_of_A
if THIS_LETTER_IS("Q") and previous_letter_was_X and found_an_even_number_of_A
and not checking_for_alternative_2:
# can't be a word of alternative 1, so check for alternative 2
going_back_to_start_to_check_for_alternative_2 = True
if going_back_to_start_to_check_for_alternative_2:
MOVE_TO_PREVIOUS
else:
MOVE_TO_NEXT
if going_back_to_start_to_check_for_alternative_2 and THIS_LETTER_IS(EMPTY):
# reached the beginning, so let's check for alternative 2
going_back_to_start_to_check_for_alternative_2 = False
checking_for_alternative_2 = True
When you have nested if
s, replace them with and
s; remove else
blocks by using not
:
if something:
if something_else:
do_a
else:
do_b
becomes
if something and something_else:
do_a
if something and not something_else:
do_b
Each if
block should then only contain one MOVE_TO_PREVIOUS
or MOVE_TO_NEXT
, possibly a WRITE
command and any number
of variable assignments.
Complete all if
clauses such that every single one of your booleans AND the current letter is always checked, duplicating
the blocks where neccessary. Example:
if something and something_else:
do_a
becomes
if THIS_LETTER_IS("A") and something and something_else and something_i_dont_care_about_here:
do_a
if THIS_LETTER_IS("A") and something and something_else and not something_i_dont_care_about_here:
do_a
if THIS_LETTER_IS("Q") and something and something_else and something_i_dont_care_about_here:
do_a
if THIS_LETTER_IS("Q") and something and something_else and not something_i_dont_care_about_here:
do_a
Now, if you have n booleans and m letters, you should have m * 2n if
s.
Just imagine you have stored the booleans in a bitfield, so each possible combination of booleans represents an
integer. Hence the above becomes
if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and bitfield[2]:
do_a
if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and not bitfield[2]:
do_a
# ...
which then becomes
if THIS_LETTER_IS("A") and bitfield == 7:
do_a
if THIS_LETTER_IS("A") and bitfield == 3:
do_a
# ...
This integer value for the bitfield is the Turing machine state. The do_a
part is just an assignment to the booleans (i.e. the bitfield, so it's your new state), a write command (if there's none, just write the letter that was already
there) and a movement command, hence explicitly a Turing Machine transition.
I hope any of the above makes sense.