3

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

我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态、转换等）的图灵机，即使我知道如何用 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 的语言）。我可以轻松地为他们编写伪代码，但编写图灵机更具挑战性（花了我很长时间），我想知道是否有一些技巧、资源或指南可以帮助我更好地解决此类问题。

4

2 回答 2

10

免责声明：您的问题非常笼统，因此这个答案也是如此。请注意，我不是 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 时，用 s 替换它们and；通过使用删除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_PREVIOUSor 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 n 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部分只是对布尔值（即位域，所以这是您的新状态）、写入命令（如果没有，只需写入已经存在的字母）和移动命令的分配，因此明确地是图灵机转换。

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

于 2010-01-20T09:18:56.927 回答
1

您是否需要一个即用型工具图灵机模拟器？有很多可用的。或者实际上你想自己做？这似乎是 JavaScript 中的有效实现：http: //klickfamily.com/david/school/cis119/TuringSim.html您可以分析代码并将其轻松转换为 C 或 C++。

于 2010-01-20T07:34:03.393 回答