计算理论要面对的第一个问题是：什么是计算机？现实的计算机相当复杂，很难直接为它们建立一个容易处理的数学理论，因此采用称为 计算模型 的理想计算机来描述，本篇就从最简单的 有穷自动机 讲起。
通常在对现实问题建立数学模型的初期，最重要的是对问题进行抽象的描述，如下图，采用状态图来描述一个有穷自动机 ：
如图所示被称为 的状态图，它包含3个状态，记作 、 和 。 起始状态 用一个指向它的无出发点的箭头表示， 接收状态 带有双圈。从一个状态指向另一个状态的箭头称为 转移 ；这里需要注意的是处理从 M 1 的起始状态开始，自动机从左至右一个一个字符读取字符串中的所有字符，根据不同的状态转移路径到不同的状态，直到读取到最后一个字符时 产生它的输出。如果 现在处于接受状态，则输出为接收，否则输出为拒绝。
例如，输入的字符串为 1101 ，用上述的有穷自动机 处理步骤如下：
形式化定义把一台有穷自动机描述成一张含有以下5部分的表：状态集、输入字母表、动作规则、起始状态以及接受状态集。用数学语言表达，5个元素的表经常称为5元组；
这里略作解释一下 动作规则 ，在描述中用 转移函数 定义动作规则，常记作 。如果有穷自动机从状态 到状态 标有输入符号 1 的箭头，这就表示它处于状态 时读取到 1，则转移到状态 ，则用转移函数记作 ；
因此可以描述 有穷自动机 是一个5元组 ，其中
此时可以给出 的形式化定义: ，其中
这里需要说明的是若 是机器 接受的全部字符串集，则称 是 机器 的语言 ，记作 。又称 识别 或 接受 。一台机器可能接受若干字符串，但是永远只能识别一个语言。如果机器不接受任何字符串，那么它仍然识别一个语言，即空语言 。
设 是一台有穷自动机， 是一个字符串并且其中任一 是字母表 的成员，如果存在 中的状态序列是 ，满足下述条件：
则称 接受
怎么理解呢？ 状态都是由上一个状态 以及输入的字符 决定的，比如 时， 即为初始状态，那么当输入为 时，输出为 ，以此类推...，当得到 时，则认为 接受 。
如果 接受 ，则称 识别语言 。