代码之家 › 专栏 › 技术社区 › Firas Assaad

图灵机状态表的设计

computation-theory turing-machines automata

3

Firas Assaad · 技术社区 · 16 年前

如果您已经有了算法的伪代码,那么它们是否有助于描述图灵机器所做的工作?

我正在上一门关于复杂性理论的课程,我需要一段时间来描述一个图灵机器,它决定或接受某种语言(状态、转换等),即使我知道如何用C或汇编之类的语言对它进行编码。我想我只是对图灵机器没有足够的练习(在上面工作),但是我很欣赏任何建议。

编辑

我不想做一个图灵机器模拟器,我想在纸上描述一个图灵机器(字母表,状态,转换),以决定某种语言。

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

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

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

你有两种状态,q和halt。什么时候? 你在Q状态,你看到1,走向右,不要改变。如果您看到0,将其更改为1并转到右边。如果你看到空白符号 (磁带结束)然后停下来状态。

正式来说,对于州来说,你会有类似于q,halt的东西。((q,1)->(q,1,r))、((q,0)->(q,1,r))、((q,)->(halt,0,l))用于转换。

现在这个问题是微不足道的,但还有其他一些问题更为涉及(加一元数或识别一种语言,其a、b和c的数目相等)。我可以很容易地为它们编写伪代码,但是编写图灵机器要困难得多(需要很长时间),我想知道是否有一些技巧、资源或指导方针可以帮助我更好地解决这样的问题。

2 回复 | 直到 16 年前

1

10

balpha 16 年前

免责声明: 你的问题很一般,所以这个答案也是。请注意,我不是TMS方面的专家,而且这种方法通常不会非常有效(我甚至不能保证它总是有效的)。我只是在这里记下一些想法。

我建议尝试这样的方法:使用伪代码并减少它,以便它只包含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

当你嵌套 如果 s,替换为 and 删除(R) 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

各 如果 然后块应只包含一个 MOVE_TO_PREVIOUS 或 MOVE_TO_NEXT ,可能是 WRITE 命令和任何数字变量赋值。

全部完成 如果 条款如下: 每一个 你的胸部和当前的字母总是被检查,复制必要的街区。例子:

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 布尔代数和米信,你应该有米 * 2 ⁿ 如果 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 部分只是对布尔值的赋值(即位域,所以它是您的新状态),一个写命令(如果没有,只写已经存在的字母以及一个移动命令,因此显式地是一个图灵机转换。

我希望以上任何一条都是合理的。

2

1

naivists 16 年前

你需要一个现成的工具,图灵机模拟器吗?有 quite many available .或者实际上你想自己做?这似乎是javascript中的有效实现: http://klickfamily.com/david/school/cis119/TuringSim.html 您可以很容易地分析代码并将其转换成C或C++。