图灵机设计

问题描述 投票：0回答：2

我最近遇到了以下问题：

给出图灵机的图灵机图，该图灵机在输入字符串

x ∈ {0, 1}∗
时停止（接受），其头位于包含字符串
x′ ∈ {0, 1}∗
的磁带左端（否则为空白），其中x′是 x 按字典顺序排列的后继字符串；即序列 
ε, 0, 1, 00, 01, 10, 11, 000, . . .
中的下一个字符串，其中字符串按长度递增的顺序列出，并按相应的整数值断开关系。 （简要记录您的 TM。）

我对如何开始为其设计合适的解决方案感到困惑。我能否获得一些关于首先设计这台机器，然后设计一般图灵机的指导？

string turing-machines lexicographic
2个回答
3
投票

图灵机

首先，您需要了解图灵机是什么，通过图灵机，我假设您正在谈论“通用图灵机”。这是计算机科学教父阿兰·图灵创造的概念机器。 机器由一些部件组成。首先，包含输入的无限磁带。类似的东西..

1-0-1-1-1-1-0-1-0-1-0 

然后是一套规则..

if 1 then 0 if 0 then 1 

因此，根据规则，当机器击中
1

时，输出为

0
。当读头设置到机器上时，我们定义机器
hitting
一个值。读头就像图灵机中的当前位置。所以它会去.. 1-0-1-1 ^------------Current head. 

然后下一次迭代：

1-0-1-1 ^----------Current Head 

这台机器实际上是在模拟按位
NOT

功能。您还可以在图灵机中设置状态，例如：

if 1 then enter state 1
if 0 then enter state 0



有什么大不了的吧？突然举例，现在你可以做这样的事情：


1. if 1 and in state 1 output 1 and enter state 0
2. if 1 and in state 0 output 0 and enter state 1
3. if 0 and in state 0 output 1 and enter state 1
4. if 0 and in state 1 output 0 and enter state 0



我们定义一个状态作为默认状态。在这个例子中，我们称之为 
state 0
。因此，当机器启动时，它会看到 1。好吧，我处于 
state 0
 并且我刚刚得到了 
1
，所以我将执行规则编号 
2
。输出一个
0
并输入
state 1
。下一个数字是
0
。好吧，我在 
state 1
，所以我将规则编号称为 
4
。看看这是怎么回事？通过添加状态，您可以真正发挥自己的能力。
现在，通用图灵机被称为“图灵完备”。这意味着它可以计算任何可计算的序列。包括您的作业规范！


你的作业


那么让我们在图灵机的背景下看看您的作业。
机器的目的是打印出来..


0 1 00 01 11 000 001 011 111



所以我们知道我们需要维持一个状态。我们也知道国家需要越来越深入。因此，如果您用户输入 
000
，我们需要知道要输出三个字符。


就家庭作业帮助而言，这恐怕就是我应该负责任地为您提供的一切。对图灵机的充分了解，再加上对您需要它做什么的了解，应该会导致您开始研究解决方案。
    




您可以使用这个状态图：



    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        






状态阅读开始0 或 1_01_0 或 1_在 start



写
摇头
下一个状态









对
开始


开始



左
公司


公司


1
左
返回


公司


0
左
公司


公司


0
左
返回


返回



左
返回


返回



对
停下来




 状态下，我们首先移动到输入的右侧，然后进入 
inc
 状态，头部位于最后一个输入符号上。该位已切换。如果它切换到 0，我们向左移动并保持在 inc 状态，因此在该位上重复相同的操作，...直到：

一点被切换为1
。然后就可以
    back
  • 回到输入的开头并停止
    我们出现空白：在这种情况下，写一个 0 并停在那里。
    • 

  • 

    这是一个可运行的片段，您可以在其中使用自己的输入：
    





createTuring({
    transitions: [
        { state: "start", read: "01",            move: "R", nextState: "start" },
        { state: "start", read: "_",             move: "L", nextState: "inc"   },
        { state: "inc",   read: "0", write: "1", move: "L", nextState: "back"  },
        { state: "inc",   read: "1", write: "0", move: "L", nextState: "inc"   },
        { state: "inc",   read: "_", write: "0", move: "L", nextState: "back"  },
        { state: "back",  read: "01",            move: "L", nextState: "back"  },
        { state: "back",  read: "_",             move: "R", nextState: "halt"  },
    ],
    initState: "start",
    tape: "0101",
});


<script src="https://trincot.github.io/turing.js"></script>





    

	



    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2025. All rights reserved.