“全排列算法”也许需要先定义为语言，这样才能方便讨论。

如果你说的“全排列算法”是指图灵机要输出一个串的全排列（在纸带上留下全排列并停机），那么显然这不会是NP，因为光是存储全排列就需要用n!的复杂度。
至于你说的那个NTM，你大概意思也许是通过分支来生成全排列。但用NTM来考虑这个问题的时候并不方便，因为NTM的"输出"功能似乎没定义，而确定性图灵机的输出可以简单定义为停机时纸带留下的东西（并且这样的定义还是比较普遍的，不少书上也是如此定义）。

如果你说的是“检测某个串是不是某个串的排列”，这似乎只需要比较长度和字符种类与个数就可以了。

inherently ambiguous....这个直观可以

我觉得你可以把你这里的这个U描述一下（中层描述，它的输入是什么？它要做什么，返回什么？），另外就是，通用图灵机(记为$U$)其实是有定义的，粗略描述为：$U(\langle M,w\rangle):$ $U$模拟$M(x)$的计算过程。如果该计算停机，则$U$停机并在纸带上留下计算结果$M(w)$，否则不停机。

U在某种意义上是可以解决任意一台图灵机可以解决的问题，但它并不能解决问题本身，因为我们需要针对问题设计出对应的图灵机M，才能把M作为输入扔给U，然后U"解决"了该问题。

至于U是否复杂，这个无法衡量，因为没有衡量标准。就描述上的复杂性来看，U的描述本身是很简单的（就是模拟嘛），复杂的也许是它的输入$\langle M\rangle$。。。所以需要说明是什么方面的"复杂"。

@bintou 主要是脸皮厚，哈哈哈哈

https://github.com/RunzhiZeng/My-Bachelor-thesis

差不多，其实按照定义：$\{0,1\}^*=\bigcup^{\infty}_{i=1} \{0,1\}^i$
其中，$\{0,1\}^n$是指长度为$n$的比特串集合(等于0则为空串)
也就是说，$\{0,1\}^*$中的任意一个元素都是有限长度的。

而无穷比特序列则不属于$\{0,1\}^*$，因为无穷比特序列的长度是无限大的。

刚开始可能会有这样的误区:　虽然它长度无穷大，但既然是0,1比特序列，那应该是在$\{0,1\}^*$中的。这个违反了我们对$\{0,1\}^*$的定义。而且我们需要注意一下名词的使用，串(string)和序列(sequence)是不一样的，串可以任意长，但必须是有穷长的，而序列并无此需求。

也可以这样类比，自然数集可以写成$\bigcup^\infty_{i=1}\{i\}$，显然自然数集是无穷集合，并且$i$是无限增长的，但是任意一个自然数，都是有限长度（以十进制位数作为长度依据）。而实数的话，以超越数$\pi$为例子，它小数点后面有无穷多位，长度无限。

可能需要仔细体会一下这两种不同的“无穷”。

在对角线法证实数集不可数的证明中，我们也借助了实数（尤其是无理数）长度无穷的特性，这一特性使得我们可以灵巧地构造那个产生矛盾的小数。
而对角线法不适用于证明$\{0,1\}^*$不可数（虽然这本身就是错误的）的一个原因在于$\{0,1\}^*$中每一个比特串都是有限长度的，我们无法构造出一个类似的产生矛盾的比特串。

那希望你还是先多读书多了解更多知识有更深理解的时候再尝试自我解决这个问题吧，我就不再参与了，这问题的讨论对我意义不大，而我的解释能力也确实有限。不过其他同学可以参与进来，促进一下理解。

泽鑫，我个人的建议就是，在我们图灵班讨论的时候(15:30~17:30)，你还是参与进来听一听比较好，我看到你好像都没参与进来而是在埋头不知道干啥。也许你认为你这个问题很有价值，没关系，有价值的问题你可以课后慢慢琢磨，正常的课堂讨论还是参与一下听一听吧。因为我担心这个问题会阻碍你计算理论的学习。

DFA不会死循环，读完输入，达到接受状态就是接受，没到达那就是不接受。
至于什么NFA死循环啥的...DFA等价于NFA好像是已经证明了的吧。。。至于你举出的反例，也许这时候你就得尝试找出自己反例里错误的地方了，像这种错误还是自己找吧别浪费大家时间。

https://runzhizeng.github.io/

载入好像好慢啊。。。优化什么的我后面再弄