图灵机设计

Question

我最近遇到了以下问题：

Give a Turing machine diagram for a Turing machine that on input a string x ∈ {0, 1}∗ halts (accepts) with its head on the left end of the tape containing the string x′ ∈ {0, 1}∗ at the left end (and blank otherwise) where x′ is the successor string of x in lexicographic order; i.e. the next string in the sequence ε, 0, 1, 00, 01, 10, 11, 000, . . . in which the strings are listed in order of increasing length with ties broken by their corresponding integer value. (Briefly document your TM.)

我很困惑如何开始为它设计合适的解决方案。我能得到一些关于首先设计这台机器，然后是一般图灵机的指示吗？

Answer 1

图灵机

首先，您需要了解图灵机是什么，关于图灵机，我假设您在谈论 Universal Turing Machine。这是计算机科学教父艾伦·图灵创造的概念机

机器由一些组件组成。首先，包含输入的无限磁带。有点像..

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，我们需要能够知道要输出三个字符。

而在作业帮助方面，我恐怕只能负责任地给你了。充分了解图灵机，并了解您需要它做什么，应该会促使您开始研究解决方案。

图灵机设计

Turing Machine Design

string

turing-machines

lexicographic