筒单语言
图灵机
图灵机由三部分组成：磁带（存储设备），读/写头（I/O 设备），控制器（控制单元）。
磁带
磁带可以看做是一个无限长的数组，数组的元素只有 1 和空两种。磁带中存储数字是按 1 的个数来存的，例如说数字 4 就是 1 个空再跟 4 个 1 再跟 1 个空。
读/写头
读/写头指向磁带的某个元素，其可以读写指向的元素的值（赋 1、清空）
控制器
控制器控制读写头的读写和移动（左移、右移）控制器的控制逻辑可以使用有限状态自动机来表，其中状态转移路径分三种：
- x/y/R：如果读了 x，就写 y 并右移
- x/y/L：如果读了 x，就写 y 并左移
- x/y/N：如果读了 x，就写 y 并不动
问题复杂度
解决问题所需的时间复杂度； 问题分为不可解问题（例如停机问题）和可解问题（例如 x+y）； 可解问题由分为多项式问题和非多项式问题。； 多项式问题指的是时间复杂度为多项式的，例如 O(logn)，O(n^2)，O(1)等 非多项式问题指的是时间复杂度为非多项式的，例如 O(10^n)，O(n!)等