设计图灵机的状态表

Question

如果您已经拥有算法的伪代码,它们是否有助于描述图灵机的功能？

我正在学习复杂性理论课程,我花了一些时间来描述一个决定或接受某种语言(状态,转换等)的图灵机器,即使我知道如何用C或甚至汇编这样的东西来编码它.我想我只是没有足够的图灵机练习(工作),但我很感激任何建议.

编辑

我不想制作图灵机模拟器,我想在纸上描述图灵机(字母,状态,过渡)来决定某种语言.

这是一个简单的例子,我的意思是,我需要编写一个超过0和1的字符串的图灵机,并将其中的所有0更改为1.例如,如果从磁带(输入)上的11010开始,它将在磁带(输出)上以11111停止.现在用高级语言,你知道它是这样的:

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

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

你有两个状态,q和停止.当您处于状态q并且您看到1时,请在不更改的情况下向右转.如果看到0,则将其更改为1并向右移动.如果看到空白符号(磁带末尾),则转到暂停状态.

在形式上你会有类似{q,halt}的状态.{((q,1) - >(q,1,R)),((q,0) - >(q,1,R)),((q,#) - >(halt,0,L) )}用于过渡.

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

Answer 1

免责声明:您的问题很一般,因此答案也是如此.请注意,我不是TM的专家,这种方法通常效率不高(我甚至不能保证它总是有效的).我只是在这里记下一些想法.

我建议尝试这样的方法:取你的伪代码并减少它,使它只包含a)布尔变量和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

当你嵌套ifs时,用ands 替换它们; 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条款,以便始终检查每一个布尔值和当前字母,并在必要时复制块.例:

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个布尔和m个字母,你应该有m*2 ⁿ if s.想象一下你已经将布尔值存储在一个位域中,因此布尔值的每个可能组合都代表一个整数.因此,上述变为

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部分只是布尔值的一个赋值(即位域,所以它是你的新状态),一个写命令(如果没有,只写下已经存在的那个字母)和一个移动命令,因此显然是一个图灵机过渡.

我希望上述任何一点都有道理.