问题标签 [computation-theory]

考虑一个类似于 pac-mac 的游戏，我们想用 FSA 图来表示它。我们有一个迷宫（桌子），里面有随机位置的浆果。目标是吃掉迷宫中的所有浆果。我们必须考虑的控制命令如下：
GOAHEAD、LEFT、RIGHT、CHECKBERRY（检查吃豆人前面是否有浆果）、EAT 和 OFF-MAZE。
我们需要最多 10 个阶段......并且请记住，我们不能连续有多个间隙。谢谢

编辑： 替代文字 http://img338.imageshack.us/img338/2479/graphp.jpg

好吧。我创建了图表，但找不到跨越间隙的方法。例如：在迷宫中，经过一排浆果后，突然前面出现了一个缺口，下一个浆果就在缺口的下方。所以我不确定我的图表会是什么样子，即使我向左或向右转 checkberry 命令也不会返回 TRUE 值。所以必须有一种方法让吃豆人在不吃东西的情况下移动到间隙广场，但它如何决定是移动到前面的那个还是其他的？

动机：我希望能够在没有一阶函数的语言中使用玩具函数式编程，方法是使用自然数而不是函数。

通用函数是一个函数 f : N -> (N -> N)，相当于 f : N * N -> N 枚举所有可能的可计算函数。换句话说，有一个数字 k 使得 f(k) 是平方函数，有一个数字 j 使得 f(j) 是第 n 个素数函数等。

要编写这样一个函数，可以采用任何图灵完备的语言（编程语言编译器、lambda 演算、图灵机..​​....）并枚举所有程序。我希望不仅允许评估，还允许对加法、合成、柯里化等功能进行操作。例如，给定两个函数 f,g 的索引，我想知道函数 f+g 或由 g 组成的 f 的索引是什么。这将允许“玩具函数式编程”。

编写这样的代码库的好方法是什么？我不是在寻找难以计算 10 阶乘的简约 Turing tarpit，我也不想编写高级编译器。它应该具有一些基本功能，例如添加和编写循环的可能性，但仅此而已。

欢迎使用所有高级语言的解决方案。伪代码、Haskell 和 Python 是首选。您可以假设任意精度算术。eval不允许使用或类似的。

澄清：枚举函数将由所有部分递归（可计算）函数组成- 这包括不会在某些输入上停止的函数。在这种情况下，通用功能将挂起；当然这是不可避免的。另请参阅：m-recursive 函数 - http://en.wikipedia.org/wiki/Μ-recursive_function。

首先，这不是要求算法将 NFA 转换为 DFA 的问题。

已知（并证明）一个 NFA 的等效 DFA 最多有 2 ⁿ个状态，尽管大多数时候它的状态数与 NFA 或多或少相同。

我如何预测 NFA 等效 DFA 将具有的状态数的估计值？哪种特定类型的 NFA 需要等效的 DFA 才能具有 2 ⁿ个状态？

我提出这个问题的原因是能够“发明”一些 NFA，这些 NFA 肯定会在不考虑最小化的情况下产生 2 ⁿ - 1 个状态加上“死状态”。

出于好奇，我试图确定我使用的系统的计算模型在功能上等效，并证明等效性。我在这个问题上花费的时间越长，我就越怀疑这个系统不是图灵等效的。我对图灵机和递归可枚举语言的理解很好，但我对功能较少的自动机（例如下推自动机）了解不多，所以我不知道如何进行。

首先，任何人都可以推荐一个好的资源来学习不同的计算模型吗？我对语法、语言和自动机，以及如何证明它们之间的等价和差异感兴趣。理想情况下，资源会非常详细地分解每个模型的所有元素并进行比较。

其次，在尝试将系统拟合到任何这些计算模型时，是否应该使用通用方法或框架？

我正在编写一个玩具编译器，如果结果仅取决于参数的值，它可以优化函数调用。所以像 xor 和 concatenate 这样的函数只依赖于它们的输入，用相同的输入调用它们总是给出相同的输出。但是像 time 和 rand 这样的函数依赖于“隐藏”的程序状态，使用相同的输入调用它们可能会产生不同的输出。我只是想弄清楚区分这两种功能的形容词是什么，例如“同构”或“可重入”之类的。有人能告诉我我要找的词吗？

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

我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态、转换等）的图灵机，即使我知道如何用 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 的语言）。我可以轻松地为他们编写伪代码，但编写图灵机更具挑战性（花了我很长时间），我想知道是否有一些技巧、资源或指南可以帮助我更好地解决此类问题。

在大学学习期间，我必须学习很多关于计算理论的知识。我学了三个学期。我很难过，我不得不承认我忘记了很多。

我想知道这是否是个人问题，或者我们只是不得不学习很多（或多或少）无用的东西。

所以我的问题是：您认为计算理论领域的哪些主题最重要，哪些部分值得学习，您在日常工作中使用哪些主题？

就个人而言，我很高兴我听说了语言理论（尤其是正则语言 => 正则表达式 - 什么时候可以应用，什么时候不可以）以及不同的时间（和空间）复杂性，特别是 O(n)符号。

但我们必须学习更多，包括：

• 可计算性理论
  • 停机问题
  • 半可判定问题
• 复杂性理论
  • p=np?
• 逻辑理论
  • 命题演算
  • 谓词逻辑

听到这些话题很有趣，但我不确定深入研究它们的必要性。

我知道这个问题是主观的，答案会根据您的日常工作和个人经历而有很大不同。但我想知道可能比我记得的更有趣的话题。

在进行考试复习时，我无法回答 Sipser 的“计算理论导论”一书中的以下问题。不幸的是，书中没有解决这个问题。

解释为什么以下不是合法的图灵机。

M = {

输入是关于变量 x1, ..., xn 的多项式 p

1. 尝试所有可能的 x1, ..., xn 设置为整数值
2. 在所有这些设置上评估 p
3. 如果这些设置中的任何一个评估为 0，则接受；否则拒绝。}

这真让我抓狂！我怀疑这是因为整数集是无限的？这是否超出了字母表的允许大小？

在 Sipser 的计算理论书中，给出了以下内容：

可能包括小数部分和/或符号的数字常数可以被描述为语言的成员

(+ U - U e) (D+ U D+ . D* UD* . D+)

其中 D = {0,1,2,3,4,5,6,7,8, 9} 是十进制数字的字母表。生成字符串的示例有：72、3.14159、+7 . 和 -.01。

在这里我不明白采取联合 D+ 或 D* 的目的是什么？此外，为什么要添加第三个点？

请有人清除我的疑问。

我们如何使用交集方法组合两个 dfa？