图灵机设计

Question

我最近遇到了以下问题：

给图灵机图的图灵机上输入一个字符串x ∈ {0, 1}∗暂停（接受）与将头包含磁带的左端字符串x′ ∈ {0, 1}∗位于左端（否则为空），其中x'是字典顺序中x的后继字符串;即序列ε, 0, 1, 00, 01, 10, 11, 000, . . .中的下一个字符串，其中字符串按照增加的长度顺序列出，其中的字符串由相应的整数值分开。 （简要记录您的TM）

我很困惑如何开始为它设计合适的解决方案。我能否首先设计这台机器，然后再选择图灵机？

Answer 1

图灵机

首先，你需要了解图灵机是什么，并通过图灵机，我假设你是在谈论一个Universal Turing Machine。这是由计算机科学教父Alan Turing创建的概念机器。

机器由一些组件组成。首先，一个包含输入的无限磁带。喜欢的东西..

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

然后是一组规则..

if 1 then 0 
if 0 then 1 

所以当机器打1，输出为0，按照该规则。我们将机器定义为在读取头设置为时的值。读头像图灵机中的当前位置。所以它会去..

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。看看这是怎么回事？通过添加状态，你真的打开了你能做的事情。

现在，通用图灵机是所谓的Turing Complete。这意味着它可以计算任何可计算的序列。包括你的任务的规范！

你的任务

因此，让我们看看你的作业在图灵机的情况下。

本机的目的是打印出来..

0 1 00 01 11 000 001 011 111 

因此，我们知道，我们需要保持状态。我们也知道国家需要越来越深入。因此，如果您的用户类型为000，我们需要知道我们有三个字符可以输出。

而在家庭作业帮助方面，这恐怕我应该负责任地给你。对图灵机的很好的理解，加上对你需要做什么的理解，应该会使你的研究成为解决方案的开始。