可计算性和复杂性/可计算性
此页面需要开发。
可计算性理论是计算机科学的一个分支，它关注确定某个问题是否可解。问题可以被认为是非常基本的情况或问题。
在当今时代，我们被先进的计算机包围着，这些计算机以令人眼花缭乱的速度工作；很容易假设，只要有足够的内存或处理能力，计算机就可以计算任何问题。然而，通过数学，我们可以证明有些问题根本没有明确的解决方案。例如：当给出问题“π的最后一位数字是什么？”时，不可能找到解决方案，因为π是无限长的。
在衡量计算解决方案的“难度”时，“自动机理论”的概念对于计算和理解问题都很有帮助。自动机理论将在本书的后面进一步介绍——它是理解复杂性的核心组成部分。
在发现什么可能是或可能不是可计算的时，构建表达我们计算背后的逻辑的模型是有帮助的——实际上，也许是必要的。模型允许我们精确地规划出问题是如何解决的，并允许我们检查过程的每个步骤。
自动机是一种模型，我们可以将它们视为一种机器，它表示一个问题（例如 2 + 2 是多少），然后在给定一些输入（4）时，运行一系列步骤，并要么接受输入为有效，要么拒绝它。这个想法（输入是否匹配给定的约束？）非常强大——并且当顺序使用时，可以解决所有可计算的问题。
自动机理论受到功能主义哲学运动的影响。功能主义者不是将数学视为利用数字进而表示值，而是更喜欢将数字视为仅仅是通过各种规则进行操作的符号。当我们检查自动机时，你会看到许多字母而不是数字——这是因为我们将字母视为符号，它们本身没有内在的重要性，只是由我们提供的规则进行操作。随着你对自动机的工作越来越熟悉，这个概念将变得更有意义。
*d.png)
右侧显示的图片是一个自动机的例子。如果输入匹配约束 a(bc)*d（一个'a' 后跟任意数量的'bc'，然后是一个'd'），它就会接受——也就是返回'true'。
让我们检查一下这张图片。每个圆圈称为一个状态，每个状态都给定一个名称 qN，其中 n 是识别号。如果我们将自动机想象成代表我们自己的心算，我们可以将每个状态视为我们逻辑思维模式的哪个步骤。指向不同圆圈的箭头称为“转换”，如果满足某些条件，则从一个状态到另一个状态。根据你正在使用的自动机的类型，这些条件可能会有所不同。在给定的示例中，唯一的约束是我们的模型在当前正在检查的输入的点处看到指定的字符。
对于 a(bc)*d，我们首先应该检查输入的开头是否包含一个'a'。如果我们看到一个 a，我们就进入第二个状态。……