1
$\begingroup$

For example, lets consider the simplest model of cipher: the Caesar cipher. According to the theory I read the Caesar cipher consist in substitute a letter by another in considering a shift in an alphabet given by a certain number.

I know that a Turing machine consist of: a tape, a header that writes or reads information from that tape, and a set of states that consist in moving to the left or right on the tape. Also the initial state and the final state and reject states.

So if I would like to make a TM that accept the Caesar cipher I suppose that the information that would be on the tape, for example, the message "hello", that I want to convert to a cipher text by a shift of n=3 in each character so I will get the word "khoor".

Because I need to put that message on a TM tape I guess that I can convert it into a binary string, would that be necessary or can I work with original characters?

For example if my TM tape look like this (I am supposing that "h" is 0011 and that "k" is 1010 for example):

|0|0|1|1|e|e|e|e|

where e is the empty character and the header is in the leftmost position pointing to 0, so if I want to convert this "h" into "k" I can read one by one each binary digit (from left to right), converting into its corresponding binary digit to the converted letter and writing it in some beginning position at the right. Would that be ok? So I will have something like:

|e|0|1|1|e|1|e|e|

After the first iteration, I have read the leftmost digit, 0, changed into 1 and then copy it after the empty position. I can do the same with all the remaining digits.

Would that approach be good enough, in this case, to simulate the Caesar cipher in a TM, and also if I want to decipher the converted text can I do a similar process?

Bottomline, maybe somebody could show a model for a Caesar cipher using a TM?

Thanks for your help.

$\endgroup$
  • $\begingroup$ I do not understand your encoding of the letters. It looks like at the end there is a missing operation. If you like to perform Rot (Caesar is Rot3, k = 3) on the alphabet A (here it might be just letters a-z, with length n = 26) then using numbers it will perform as (c + k) % n. If this is about usimg substitution, then there are e.g. 26 cases with substitutions (of the form read 'a' write 'd', read 'z' write 'c') going left after each substitution and accepting when the input is over. Reverse will be with -k and symmetric description for substitutions ('d' maps to 'a' and so on). $\endgroup$ – Evil Jan 21 '17 at 4:52
  • $\begingroup$ Now, these are some ideas, do you ask for a transition function of Caesar cipher, want to check your idea or something else? If you insist on using binary numbers then the addition/subtraction and modular division should be implemented. $\endgroup$ – Evil Jan 21 '17 at 4:57
  • 1
    $\begingroup$ $q_0 ~a ~d ~R~q_0\\ q_0 ~b ~e ~R ~q_0\\ q_0 ~c ~f ~R ~q_0\\ q_0 ~d ~g ~R ~q_0\\ q_0 ~e ~h ~R ~q_0\\ q_0 ~f a ~R ~q_0\\ q_0 ~g ~b ~R ~q_0\\ q_0 ~h ~c ~R ~q_0\\ q_0 ~\epsilon ~Accept\\$ something like this for a small alphabet, $q_0$ is initial state, then read, write, move, new state. $\endgroup$ – Evil Jan 21 '17 at 5:10
  • $\begingroup$ thanks @Evil, correct me if I am wrong, but for what I see starting from the initial state you are reading, for example, 'a' and then converting and writing 'd' at the right of the initial state, am I right? In this case the data on the left of the tape is not being delete? $\endgroup$ – Layla Jan 21 '17 at 11:16
  • 1
    $\begingroup$ I think that you mix state and the tape. $q_0$ is the only state used. For input [a, b, c] the head is over 'a', overwrites it to 'd' so [d, b, c], moves the head over 'b'. Next step goes over 'b', changes it to 'e', [d, e, c], moves over 'c', changes it to 'f', moves over next symbol, which is blank and accepts. The state is q_0, the only state present. $\endgroup$ – Evil Jan 21 '17 at 11:25
1
$\begingroup$

Honestly, the answer to "How do I model X using a Turing Machine is:"

  • Implement the algorithm using a programming langauge, probably a simple one like lambda-calculus
  • Translate from that language into a Turing Machine

We could tell you how to write a machine that does a Caesar cipher, but it would just be us doing the above steps for you.

Turing Machines are very un-intuitive to program in, and they're usually not used to model algorithms directly, more as a theoretical baseline of what an algorithm is. But while there are lots of proofs that model Turing Machines in general, usually you don't deal with specific machines.

If you really need to model things directly with TMs, try using a variant of them, such as RAM machines (which would probably be much easier for modelling a Caesar Cipher), and/or multi-tape TMs, then use the known translations to ordinary machines.

$\endgroup$
  • $\begingroup$ thanks @jmite, one question why is it needed to implement it first in a programming language? for example in this particular case I can implement it into an imperative language, which I suppose it would be closer to RAM machine. Is it needed a multitape TM in this case? $\endgroup$ – Layla Jan 21 '17 at 11:19
  • 1
    $\begingroup$ It's not needed, it's just easier. Turing machines are even more low level than assembly in many ways. If you try to program directly in them you'll end up reinventing a lot of the structures that the translation algorithms give you for free. $\endgroup$ – jmite Jan 21 '17 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.