how to make a Turing machine of a cipher? 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.
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.