设计一个图灵机的状态表

如果你已经有了算法的伪代码，它们是否有用来描述图灵机做什么的有用指导？设计一个图灵机的状态表

我正在学习复杂性理论课程，它花了我一段时间来描述决定或接受某种语言（状态，转换等）的图灵机，即使我知道如何在类似的东西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，halt}的状态。（（q，1） - >（q，1，R）），（（q，0） - > ）}进行转换。

现在这个问题是微不足道的，但也有其他更涉及（增加一元数字或识别语言数量相同的a，b和c的数量）。我可以很容易地为他们编写伪代码，但是编写图灵机要困难得多（需要很长时间），我想知道是否有一些技巧，资源或准则可以帮助我更好地解决这类问题。

来源

2010-01-20 Firas Assaad

你是什么意思“构建语言的图灵机”？ – balpha 2010-01-20 07:28:09

你需要将手放在无限长的磁带上。 – 2010-01-20 07:32:01

@balpha：通常我会遇到像“提出决定语言{w属于{a，b} *：w至少包含一个a}的语言的图灵机”。只是我书中的一个随机例子。我重新提出了我的问题，使其更清楚。 – 2010-01-20 07:33:19

免责声明：您的问题是非常普遍的，因此这个答案也是如此。请注意，我什么都不是TM的专家，而且这种方法通常效率不高（我甚至不能保证它总是有效）。我只是在这里记下一些想法。

我会建议尝试这样的方法：拿你的伪代码，并减少它，使它只包含一个）布尔变量和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小号取代它们;通过使用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条款，使得每一个你的布尔值和当前信的一个始终检查，重复块，其中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 ^ň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部分只是一个布尔值赋值（即位域，所以它是你的新状态），一个写命令（如果没有的话，只写一个已经是的字母）和一个移动命令，因此显式地是一个图灵机过渡。

我希望以上任何一条都有道理。

来源

2010-01-20 09:18:56 balpha

这正是我们所需要的。我在问，谢谢！ – 2010-01-20 09:23:23

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

来源

2010-01-20 07:34:03 naivists

我不想制作一个图灵机模拟器，我如果我没有清楚地说出我的问题，我很抱歉，那些模拟器似乎对实验非常有用 – 2010-01-20 07:38:10

设计一个图灵机的状态表

回答

相关问题