设计一个图灵机状态表
-
21-09-2019 - |
题
他们是来描述,如果你已经拥有了算法的伪代码图灵机所做的任何有用的指引?
我以复杂性理论的一个过程,它需要我一段时间来描述一个图灵机决定,或接受一些语言(状态,转换等),即使我知道我可以在类似于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的)。我可以很容易写的伪代码对他们来说,却写的图灵机是更具挑战性的(花了我很长一段时间),我想知道,如果有一些小技巧,资源,或指引,帮助我在解决这样的问题,更好的成为。
解决方案
声明:您的问题很普遍,因此,所以是这个答案。请注意,我什么,但对记忆库的专家, 这种做法通常不会是非常有效的(我甚至不能保证它永远是有效的)。 我只是在这里记下一些想法。
我会建议尝试这样的方法:把你的伪代码,并减少它,这样
它仅由一个)布尔变量和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
s,与and
s取代它们;通过使用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 的名词 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
部分仅仅是一个分配给布尔值(即位域,所以这是你的新的状态),写入命令(如果有没有,只写一个已经信
存在)和移动命令,从而明确地图灵机的过渡。
我希望上述任何有意义。
其他提示
你需要一个随时可以使用的工具,图灵机模拟器?有相当多的可用。其实还是要自己做呢?这似乎是在JavaScript中的有效实施: http://klickfamily.com/david/学校/ cis119 / TuringSim.html 你可以分析代码,并将其转化为C或C ++很容易。