设计图灵机的状态表-Java 学习之路

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

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

edit

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

这是一个简单的例子，我的意思是，我需要编写一个超过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的语言） . 我可以轻松地为他们编写伪代码，但编写图灵机更具挑战性（需要我很长时间），我想知道是否有一些技巧，资源或指导方针可以帮助我更好地解决这类问题 .

2 回答

Disclaimer: 你的问题非常笼统，因此答案也是如此 . 请注意，我甚至承诺它将始终有效） . 我只是在这里记下一些想法 .

我建议尝试这样的方法：取你的伪代码并减少它，使它只包含a）布尔变量和b） if -statements . 例如：

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 时，用 and 替换它们;使用 not 删除 else 块：

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 * 2n 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 部分只是对布尔值的赋值（即位域，所以它是's your new state), a write command (if there' s无，只是写出已经存在的字母）和移动命令，因此明确地表示图灵机转换 .

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

回复于 2024-05-02T10:35:27+08:00

1

您需要一个即用型工具，图灵机模拟器吗？有quite many available . 或者实际上你想制作自己的？这似乎是JavaScript中的有效实现：http://klickfamily.com/david/school/cis119/TuringSim.html您可以很容易地分析代码并将其转换为C或C.

回复于 2024-05-02T10:35:27+08:00

设计图灵机的状态表

2 回答

相关问题