前言

上一篇关于序理论的文章对于偏序关系的介绍不多，于是这一篇我准备重点整理偏序关系的相关知识，内容摘抄自南京大学的课件。这一篇的重点是引出join-semilattice概念，它是CRDT数据结构的核心。

前言

我原本打算翻译一篇跟CRDT相关的文章，但是奈何找到博客都讲得过于精简，而关于CRDT的论文有把我看得一头雾水。那只能先从基础的理论开始了，以后看能不能把这些资料汇总一下。

前言

由于工作需要，最近在学习实时协同编辑相关的知识。我在分享会听大佬讲了两个理论，分别是OT（Operational Transformation）和CDRT。但是听的时候跟不上，无奈只能下来找时间消化吸收了。会后拿到了两篇博客，看完理解之后还是想翻译一遍，留个存档。（偷个懒，图片链接我用的原文博客中的，所以要翻墙才能看）

前言

在上一节课中我们讨论过确定性时间复杂度，以及时间层谱定理，还介绍了两个复杂度类：P和EXP。这节课我们将会介绍另外一个复杂度类，叫做NP，并且学习它于P和EXP的关系。此外，我们将会定义一个改版的多项式时间的映射约化，再加一个NP类的完全性概念。

备注20.1. NP-完全性的概念是目前计算机科学对当今科学界最重要的贡献之一；NP-完全性问题，非常著名，在整个数理科学中随处可见。因此本书有必要提及这个概念。
　　然而在滑铁卢大学中，复杂度类NP和NP完全性概念，包含在一个不同的课程中，CS 341 Algorithm。由于这个原因，我们在本课程中没有着重讲解 — 这里我们只当NP类是一个重要的复杂度类案例。特别是，我们将不会提及证明某个语言是NP-完全性的证明技术，但是那些刚接触这个课题的人可以放心，有成千上万个有趣的案例，包括一些具有重要现实意义的例子，都是已知的。

前言

最后两节课我们将会讨论话题是计算复杂性理论，它涉及计算问题的内在难度和资源约束对计算模型的影响。我们的时间只能够浅尝辄止；复杂度理论是一门内容丰富的学科，世界上很多学者都致力于研究这个领域。不同于形式语言理论和可计算性理论，许多复杂度理论的重要问题至今仍未解决。
　　在这节课中我们将会更关注最重要的资源（从计算复杂性理论角度来看），时间。从某种意义上，这个动机是明显的：为了有用，通常我们期望计算能在一个合理的时间能完成。在极端情况下，如果我们有某个需要执行的计算任务，而且有人提供一个能执行这个任务的计算设备，但是需要在十亿年之后才能得到结果，那么这个设备就没有用处。除了时间，你们可能会考虑到其他资源，比如空间（或者内存占用），在分布式场景中的沟通，或者关于资源使用的各种其他抽象概念。
　　那么我们就从一个DTM的运行时定义开始吧。

定义19.1. 已知$M$是一个DTM，它的输入字母表是$\Sigma$。对于每个字符串$w\in\Sigma^{*}$，用$T(w)$表示$M$执行输入$w$的步数（可能是有限的）。$M$的运行时函数$t:\mathbb{N}\rightarrow\mathbb{N}\cup\{\infty\}$的定义如下

其中每个$n\in\mathbb{N}$。用文字表达，$t(n)$是$M$输入长度为$n$的字符串计算停止所需的最大步数。
　　我们将会把关注点限制对于所有输入长度的运行时都是有限的DTM上。

前言

这节课我们将会讨论一些关于图灵机和可计算性的知识点，内容是超出上节课范围的。我们先谈一谈可判定和半可判定语言的一些基本的封闭性质。然后我们再简短地讨论一下非确定性图灵机，以及它与可判定和半可判定语言的关系。最后我们将会证明半可判定性的一个有趣特征，关于一个非空语言是半可判定的当且仅当它等于一个可计算函数的值域。

前言

在上节课中我们见过了一些不可判定语言的例子：$DIAG$是非半可判定的，并且因此也是不可判定的，而$A_{DTM}$和$HALT$是半可判定的，但却是不可判定的。这节课我们将会看多看一些例子。我们也将引入语言约化（reduction）的概念，它可以用来证明语言的不可判定性。
　　然而在此之前，我们将会花一些时间来观察几个设计图灵的好用的基本技巧。

前言

这节课我们会讲到通用图灵机。这是一个确定性图灵机，当我们已知一个任意DTM编码时，它能够根据一个已知输入来模拟这个DTM。
　　为了描述这样一个通用机器，我们自然而然会想到DTM的编码，这也是我们本节课要做的第一件事。这个DTM编码方案的概念让我们首次见到了非半可判定（因此也就是不可判定）语言的例子。通过这个语言的非半可判定性，就能证明许多其他的语言是不可判定或者非半可判定的。我们先来看两个简单的例子，后面还会有更多。

前言

现在我们已经学习过图灵机模型的基本方面，报错图灵机的变体和在计算上等价的堆栈机模型，现在到了讨论一些可判定语言案例的时候了。在这节课中我们将会着重于讲基于有限自动机和上下文无关语法的例子。这些语言在某种程度上有别于我们在本课程前面讲过的大多数语言；它们的定义已基本的数学概念为中心，而不是简单的句法模式。
　　然而在开始之前我们需要先讨论一下编码（encodings），它允许我们使用已知基于字母表的字符串来表达复杂的数学对象。比如，我们也许希望让一个DTM接受一个数字，一个图，一个DFA，一个CFG，另一个DTM（甚至可能是它自身的描述），或者一个由不同类型的对象组成的列表作为输入。我们将会在本课程的剩余部分用到编码概念。

前言

现在我们将会定义一个新的计算模型，堆栈机模型，并且注意：它的能力是与确定性图灵机模型等价的。本课程在这个时候介绍堆栈机模型主要有两方面的原因：

1. 堆栈机用起来比图灵机更简单，至少在细节层面是这样的。

   然而正式地为最基本的计算指定图灵机是很乏味的，且容易出错，同样的任务相对于堆栈机就比较轻松了。尽管两种模型是等价的，但是人们更愿意相信是图灵机抽象了普通计算机的能力。

2. 堆栈机和图灵机的等价为我们提供了一个非常棒的例子来支持丘奇-图灵论题。

   堆栈机模型是自然且直观的，特别是在本课程中相较于其他我们学习过的模型，你可以明确地想象构造一个 — 或者甚至你可以用纸来实现栈模仿一个。换言之，它就代表着机械过程。正如丘奇-图灵论题所预言的，你能使用这种模型来计算的任意事物也能使用确定性图灵机。

堆栈机模型类似于下推自动机模型，但不同的是堆栈机模型允许使用多个栈。光这一点就造成了天差地别。事实上，正如我们所知道的，仅使用两个栈就能堆栈机模型拥有通用的计算能力。还有一个不同点，我们只会考虑堆栈机的确定性变体（虽然我们能轻松定义一个非确定性堆栈机）。