设计一个图灵机状态表

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，暂停}的状态。 {（（Q，1） - >（Q，1，R）），（（Q，0） - >（Q，1，R）），（（Q，＃） - >（停止，0，L） ）}进行转场。

现在这个问题是微不足道的，但也有其他被更涉及（添加一元号码或识别与相等数目的一个的，B的的语言，和C的）。我可以很容易写的伪代码对他们来说，却写的图灵机是更具挑战性的（花了我很长一段时间），我想知道，如果有一些小技巧，资源，或指引，帮助我在解决这样的问题，更好的成为。

Answer 1

声明：您的问题很普遍，因此，所以是这个答案。请注意，我什么，但对记忆库的专家， 这种做法通常不会是非常有效的（我甚至不能保证它永远是有效的）。 我只是在这里记下一些想法。

我会建议尝试这样的方法：把你的伪代码，并减少它，这样 它仅由一个）布尔变量和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条款，使得的每颗之一的你布尔当前信始终检查，复制 块，其中neccessary。例如：

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

现在，如果你的名词的布尔和的米的信件，你应该有米的* 2 ^的名词 ifs。 试想一下，你已经存储在一个位域，布尔值，所以布尔值的每个可能的组合表示 整数。因此上述变

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/学校/ cis119 / TuringSim.html 你可以分析代码，并将其转化为C或C ++很容易。