图灵机和密码
Turing Machine and Ciphers
我正在研究图灵机，并试图弄清楚如何使用图灵机描述一些基本的密码算法（例如凯撒密码）。
考虑：
F={x#y|x,y∈{a,b,c,d,e,f}∗,y is equal to x with a Caesar shift of 3}.
我如何描述决定 F 的图灵机算法？
免责声明：为了清晰和简洁，以下算法从原始图灵机中提取了一些 simplifications/variations。最值得注意的是，我们隐含地描述了图灵机的状态，例如在第 2 步中，当我们说我们将移位符号跟踪为字符 s，然后将其与我们在步骤中读取的符号相匹配5，我们真正的意思是我们转换到图灵机的一个特定状态，该状态将转换到其他特定状态，如步骤 3-4 所述移动头部，如果我们最终读取的符号不是移位字符 s.
我们可以在输入字符串 x#y 上使用以下算法描述图灵机：
读取当前交易品种。如果它是#（即 x 是一个空字符串），转到第 8 步。
读取当前交易品种。如果不在 {a, b, c, d, e, f} 中，则拒绝。否则，对角色执行 3 的凯撒移位。让这个新的移位字符为s。用 $.
替换当前符号
在纸带上向右移动，直到我们读到# 符号。如果我们在发生这种情况之前读取空白 space，则拒绝。
在磁带上向右移动磁头，直到我们读到一个不是 # 的符号。
读取当前交易品种。如果此 space 为空，则拒绝。如果此符号与步骤 2 中移位的字符 s 不匹配，则拒绝。否则，用 #.
替换当前符号
向左移动头部，直到我们读到一个 $ 字符。然后把头一个space向右移动
读取当前交易品种。如果是#，转第8步，否则转第2步
在磁带上向右移动磁头，直到我们读到一个不是 # 的字符。
如果这个space不是空白，则拒绝。否则，接受。
我正在研究图灵机，并试图弄清楚如何使用图灵机描述一些基本的密码算法（例如凯撒密码）。
考虑：
F={x#y|x,y∈{a,b,c,d,e,f}∗,y is equal to x with a Caesar shift of 3}.
我如何描述决定 F 的图灵机算法？
免责声明：为了清晰和简洁，以下算法从原始图灵机中提取了一些 simplifications/variations。最值得注意的是，我们隐含地描述了图灵机的状态，例如在第 2 步中，当我们说我们将移位符号跟踪为字符 s，然后将其与我们在步骤中读取的符号相匹配5，我们真正的意思是我们转换到图灵机的一个特定状态，该状态将转换到其他特定状态，如步骤 3-4 所述移动头部，如果我们最终读取的符号不是移位字符 s.
我们可以在输入字符串 x#y 上使用以下算法描述图灵机：
读取当前交易品种。如果它是#（即 x 是一个空字符串），转到第 8 步。
读取当前交易品种。如果不在 {a, b, c, d, e, f} 中，则拒绝。否则，对角色执行 3 的凯撒移位。让这个新的移位字符为
替换当前符号s。用 $.在纸带上向右移动，直到我们读到# 符号。如果我们在发生这种情况之前读取空白 space，则拒绝。
在磁带上向右移动磁头，直到我们读到一个不是 # 的符号。
读取当前交易品种。如果此 space 为空，则拒绝。如果此符号与步骤 2 中移位的字符
替换当前符号s不匹配，则拒绝。否则，用 #.向左移动头部，直到我们读到一个 $ 字符。然后把头一个space向右移动
读取当前交易品种。如果是#，转第8步，否则转第2步
在磁带上向右移动磁头，直到我们读到一个不是 # 的字符。
如果这个space不是空白，则拒绝。否则，接受。