automata - 设计图灵机的状态表

Question

如果您已经拥有该算法的伪代码，它们是否有任何有用的指南来描述图灵机的功能？

我正在修一门关于复杂性理论的类(class)，我需要花一些时间来描述决定或接受某种语言(状态、转换等)的图灵机，尽管我知道如何用 C 甚至汇编之类的语言对其进行编码.我想我只是没有足够的图灵机练习(正在研究它)，但我感谢任何建议。

编辑

我不想制作图灵机模拟器，我想在纸上描述图灵机(字母、状态、转换)来决定某种语言。

这是我的意思的一个简单示例，假设我需要编写一个图灵机，它遍历一串 0 和 1，并将其中的所有 0 更改为 1。例如，如果您从磁带(输入)上的 11010 开始，它会在磁带(输出)上以 11111 停止。现在在高级语言中你知道它是这样的:

Go over every character on tape
    If character is 0 change it to 1

图灵机的描述非正式地类似于:

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.

正式地，您将拥有诸如 {q,halt} 之类的状态。 {((q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (halt, 0, L) )} 用于过渡。

现在这个问题是微不足道的，但还有其他更复杂的问题(添加一元数或识别具有相同数量的 a、b 和 c 的语言)。我可以轻松地为他们编写伪代码，但编写图灵机更具挑战性(需要我很长时间)，我想知道是否有一些技巧、资源或指南可以帮助我更好地解决此类问题。

Answer 1

免责声明:你的问题很笼统，因此这个答案也是如此。请注意，我绝不是 TM 专家，而且
这种方法通常不是很有效(我什至不能保证它总是有效)。
我只是在这里记下一些想法。

我建议尝试这样的方法:使用你的伪代码并减少它，以便
它只包含 a) bool 变量和 b) if - 声明。
例如:

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

当您嵌套时 if s，将它们替换为 and s;删除 else使用 not 阻止:

if something:
    if something_else:
        do_a
    else:
        do_b

变成

if something and something_else:
    do_a

if something and not something_else:
    do_b

每个 if块应该只包含一个 MOVE_TO_PREVIOUS或 MOVE_TO_NEXT ，可能是 WRITE命令和任何数字
变量赋值。

完成所有 if子句，这样你的每一个 bool 值和当前字母总是被检查，重复
需要的块。例子:

if something and something_else:
    do_a

变成

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

现在，如果你有 n 个 bool 值和 m 个字母，你应该有 m * 2n if s。
试想一下，您已将 bool 值存储在位域中，因此每个可能的 bool 值组合都代表一个
整数。因此上面变成

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

# ...

然后变成

if THIS_LETTER_IS("A") and bitfield == 7:
    do_a

if THIS_LETTER_IS("A") and bitfield == 3:
    do_a

# ...

位域的这个整数值是图灵机状态。 do_a部分只是对 bool 值的赋值(即位域，所以它是你的新状态)，一个写命令(如果没有，只需写下已经存在的字母
那里)和一个移动命令，因此明确地是图灵机转换。

我希望以上任何一条都有意义。