问题标签 [turing-machines]

我不太了解图灵机的整个想法。

我目前的任务是制造一台繁忙的海狸图灵机。但我没有真正得到的是它模拟输入。那么我模拟什么样的输入呢？例如，它问我 3 州忙碌的海狸机器在磁带上写了多少个 1？我确定我需要写一个图灵机，但是一旦我有了它，我该怎么办呢？

我应该用什么字符串来模拟它？

图灵机的定义说禁止读取/修改它的指令表（程序）。确切地说，图灵机无法访问它自己的程序。

如果可以削弱这种限制，可以带来什么好处？如果一台机器可以分析和/或修改它的程序。这会扩展图灵可计算任务的类别吗？

这是我的任务之一。我有一个图灵机模拟，可以模拟一个忙碌的海狸功能。我已经做了一些关于证明这个问题的研究，但仍然没有得到它，所以我想也许你可以在这里帮助我。对我来说，这是一个很好的来源或如何论证这一点的例子。

好的，今天的目标是构建一个图灵机模拟器。对于那些不知道它是什么的人，请参阅Wikipedia 文章。我们今天使用的状态表位于作为该页面一部分的正式定义的末尾。

该代码将采用“0”和“1”字符串字符的序列，一个表示机器开始的字符的整数，以及一个表示程序状态的整数（无特定顺序），并输出最终结果对字符串的操作，以及最终位置。例子：

示例 1：

示例 2：

杂项：

• 您的代码必须通过根据需要扩展字符串来正确处理写入磁带上“空格”的尝试。
• 由于指定的状态机未指定任何类型的“空白磁带”操作，因此将所有空白值视为 0。
• 您必须仅计算处理具有初始状态的字符串的评估的方法，如何输出该数据取决于您。
• 在磁带上向右移动是递增的（字符串位置 0 一直在左侧），状态 0 是 A，状态 1 是 B，状态 2 是 C。

（希望）最终编辑： 我对这个问题造成的混乱和麻烦表示最诚挚的歉意：我误读了我列出的提供的状态表，并将其倒退。我希望你能原谅我浪费你的时间；这完全是无意的！

可以有一个 NFA 决定实数吗？

我如何创建图灵机，它将计算以#分隔的两个二进制数字的总和，例如。111#101B，其中 B 代表空白？结果可以写在磁带的末尾。

如果您已经拥有算法的伪代码，它们是否有助于描述图灵机的功能？

我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态、转换等）的图灵机，即使我知道如何用 C 甚至汇编之类的东西对其进行编码. 我想我只是没有对图灵机进行足够的练习（正在研究它），但我很感激任何建议。

编辑

我不想制作图灵机模拟器，我想在纸上描述图灵机（字母、状态、转换）以决定某种语言。

这是我的意思的一个简单示例，假设我需要编写一个图灵机，它会遍历一串 0 和 1，并将其中的所有 0 更改为 1。例如，如果您从磁带上的 11010（输入）开始，它会以磁带上的 11111（输出）停止。现在在高级语言中你知道它是这样的：

图灵机的描述非正式地类似于：

你有两个状态，q 和 halt。当你处于状态 q 并且你看到一个 1 时，向右走而不改变它。如果您看到 0，请将其更改为 1 并向右走。如果您看到空白符号（磁带结尾），则进入停止状态。

正式地，您将有类似 {q, halt} 的状态。{((q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (halt, 0, L) )} 用于转换。

现在这个问题是微不足道的，但还有其他更复杂的问题（添加一元数或识别具有相同数量的 a、b 和 c 的语言）。我可以轻松地为他们编写伪代码，但编写图灵机更具挑战性（花了我很长时间），我想知道是否有一些技巧、资源或指南可以帮助我更好地解决此类问题。

如果我有一台机器，称之为机器 1，它能够解决一个问题：它只是一台机器，而不是图灵机。它可以解决一个特定的问题。如果这个完全相同的问题可以在通用图灵机上解决，那么我原来的机器 1 也是通用图灵机吗？

这并不适用于所有问题，这已经被解决了。是否有任何具有此描述属性的问题？如果这绝对不是真的，那为什么呢？

有人可以举一个要解决的问题的例子。如果我原来的机器解决了这个问题，1，确定这是一台万能车床吗？还是不存在这样的问题？如果不存在，为什么？

我很感兴趣，但无法弄清楚...谢谢。

编辑：使问题更清楚。

我知道它们不是真实的，只要有 2 个选项，它们似乎就会分支计算，而不是选择一个。但是，例如，如果我这样说：

“非确定性地猜测从图 G 到图 H 的顶点的双射 p”（这里的上下文是图同构）

那应该是什么意思？我理解双射，但它说“非确定性猜测”。如果是猜测，那是一种算法方法吗？它如何保证它会起作用？

有些语言是图灵机可以处理而 LBA 不能处理的，但是否有任何 LBA 无法解决但 TM 可以解决的有用的实际问题？

LBA 只是一个带有有限磁带的图灵机，而实际的计算机具有有限的存储空间，所以在我看来，没有什么是 LBA 做不到的。 除了线性有界自动机不仅有一个有限的磁带，还有一个大小是输入大小的线性函数的磁带。有限性的线性是否以某种方式限制了 LBA？

是否存在 LBA 无法解决的问题，但指数有界自动机可以（如果存在此类问题）？