设计图灵机的状态表

Question

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

我正在学习复杂性理论课程，尽管我知道如何用 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, #) -> (停止, 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

当您嵌套了

if

时，将其替换为

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_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

。 想象一下您已将布尔值存储在位字段中，因此每个可能的布尔值组合都代表一个 整数。因此上面就变成了

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

部分只是对布尔值（即位域，所以它是你的新状态）的赋值，一个写入命令（如果没有，只需写入已经存在的字母） 那里）和一个移动命令，因此明确是图灵机转换。

我希望以上任何一点都是有道理的。

Answer 2

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

Answer 3

以前我做过类似您正在寻找的事情。 解决方案在this repo，UI不太人性化，但你可以检查一下。