算法有多种表达形式,但大体上可以归结为两类:非形式化的概念性的描述,形式化的精确的描述
其中,非形式化的概念性的描述通常通过自然语言来表达;而形式化的精确的描述则需要借助图灵机来表达,其常常被定义为运行在图灵机上的一组指令集
为什么算法的精确定义需要用到图灵机?
个人理解:精确从某种意义上来说就是恰到好处的简单,一个步骤不多,一个步骤不少
必须承认,算法的直观理解的确不需要使用图灵机的概念,就像我们小学就会的竖式乘法,我们会在纸上按照特定的步骤写下我们的计算过程然后得出答案。尽管看上去很简单直观,但实际上还是太复杂了:手握笔在纸上腾挪的这个事情想要真正描述清楚并不是一件容易的事情
小测试
有兴趣的读者可以尝试:能否在 50 字以内把”如何列竖式来计算两个三位数的乘积”清楚地描述出来
想要获得算法的精确定义就需要大刀阔斧地化简,比如把计算过程的执行者换成电路。
我们可以很容易(可能也不太容易😢)设计出一个乘法电路,然后指着一堆密密麻麻的电线告诉别人这就是乘法算法。这目前看来完全没有任何问题,直到另外一个人也拿来了一堆错综复杂的电线,然后告诉你这是除法算法。
你们会发现一个几乎必然的事实:你们两个的电路并不相互兼容!你的乘法电路在不改变接线的情况下是无法执行除法算法的。
也就是说,过于简单的电路并不能够完全替代人类来进行通用的计算。那么什么东西能够执行通用计算,但是又不存在除了通用计算之外的多余的功能呢?
图灵机。这就是为什么算法的精确定义需要图灵机,因为图灵机是最简单的能够执行所有算法而不需要改变自身结构的东西。